1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010, 2011 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"
36 #include "tree-flow.h"
39 #include "tree-chrec.h"
40 #include "tree-data-ref.h"
41 #include "tree-scalar-evolution.h"
46 #include "graphite-poly.h"
47 #include "graphite-sese-to-poly.h"
50 /* Assigns to RES the value of the INTEGER_CST T. */
53 tree_int_to_gmp (tree t
, mpz_t res
)
55 double_int di
= tree_to_double_int (t
);
56 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
59 /* Returns the index of the PHI argument defined in the outermost
63 phi_arg_in_outermost_loop (gimple phi
)
65 loop_p loop
= gimple_bb (phi
)->loop_father
;
68 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
69 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
71 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
78 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
79 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
82 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
84 gimple phi
= gsi_stmt (*psi
);
85 tree res
= gimple_phi_result (phi
);
86 size_t entry
= phi_arg_in_outermost_loop (phi
);
87 tree init
= gimple_phi_arg_def (phi
, entry
);
88 gimple stmt
= gimple_build_assign (res
, init
);
89 edge e
= gimple_phi_arg_edge (phi
, entry
);
91 remove_phi_node (psi
, false);
92 gsi_insert_on_edge_immediate (e
, stmt
);
93 SSA_NAME_DEF_STMT (res
) = stmt
;
96 /* Removes an invariant phi node at position PSI by inserting on the
97 loop ENTRY edge the assignment RES = INIT. */
100 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
102 gimple phi
= gsi_stmt (*psi
);
103 loop_p loop
= loop_containing_stmt (phi
);
104 tree res
= gimple_phi_result (phi
);
105 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
106 size_t entry
= phi_arg_in_outermost_loop (phi
);
107 edge e
= gimple_phi_arg_edge (phi
, entry
);
110 gimple_seq stmts
= NULL
;
112 if (tree_contains_chrecs (scev
, NULL
))
113 scev
= gimple_phi_arg_def (phi
, entry
);
115 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
116 stmt
= gimple_build_assign (res
, var
);
117 remove_phi_node (psi
, false);
119 gimple_seq_add_stmt (&stmts
, stmt
);
120 gsi_insert_seq_on_edge (e
, stmts
);
121 gsi_commit_edge_inserts ();
122 SSA_NAME_DEF_STMT (res
) = stmt
;
125 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
128 simple_copy_phi_p (gimple phi
)
132 if (gimple_phi_num_args (phi
) != 2)
135 res
= gimple_phi_result (phi
);
136 return (res
== gimple_phi_arg_def (phi
, 0)
137 || res
== gimple_phi_arg_def (phi
, 1));
140 /* Returns true when the phi node at position PSI is a reduction phi
141 node in REGION. Otherwise moves the pointer PSI to the next phi to
145 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
148 gimple phi
= gsi_stmt (*psi
);
149 tree res
= gimple_phi_result (phi
);
151 loop
= loop_containing_stmt (phi
);
153 if (simple_copy_phi_p (phi
))
155 /* PRE introduces phi nodes like these, for an example,
156 see id-5.f in the fortran graphite testsuite:
158 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
160 remove_simple_copy_phi (psi
);
164 if (scev_analyzable_p (res
, region
))
166 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
168 if (evolution_function_is_invariant_p (scev
, loop
->num
))
169 remove_invariant_phi (region
, psi
);
176 /* All the other cases are considered reductions. */
180 /* Store the GRAPHITE representation of BB. */
183 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
185 struct gimple_bb
*gbb
;
187 gbb
= XNEW (struct gimple_bb
);
190 GBB_DATA_REFS (gbb
) = drs
;
191 GBB_CONDITIONS (gbb
) = NULL
;
192 GBB_CONDITION_CASES (gbb
) = NULL
;
198 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
201 struct data_reference
*dr
;
203 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
206 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
208 free (bap
->alias_set
);
217 free_gimple_bb (struct gimple_bb
*gbb
)
219 free_data_refs_aux (GBB_DATA_REFS (gbb
));
220 free_data_refs (GBB_DATA_REFS (gbb
));
222 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
223 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
224 GBB_BB (gbb
)->aux
= 0;
228 /* Deletes all gimple bbs in SCOP. */
231 remove_gbbs_in_scop (scop_p scop
)
236 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
237 free_gimple_bb (PBB_BLACK_BOX (pbb
));
240 /* Deletes all scops in SCOPS. */
243 free_scops (VEC (scop_p
, heap
) *scops
)
248 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
250 remove_gbbs_in_scop (scop
);
251 free_sese (SCOP_REGION (scop
));
255 VEC_free (scop_p
, heap
, scops
);
258 /* Same as outermost_loop_in_sese, returns the outermost loop
259 containing BB in REGION, but makes sure that the returned loop
260 belongs to the REGION, and so this returns the first loop in the
261 REGION when the loop containing BB does not belong to REGION. */
264 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
266 loop_p nest
= outermost_loop_in_sese (region
, bb
);
268 if (loop_in_sese_p (nest
, region
))
271 /* When the basic block BB does not belong to a loop in the region,
272 return the first loop in the region. */
275 if (loop_in_sese_p (nest
, region
))
284 /* Generates a polyhedral black box only if the bb contains interesting
288 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
290 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
291 sese region
= SCOP_REGION (scop
);
292 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
293 gimple_stmt_iterator gsi
;
295 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
297 gimple stmt
= gsi_stmt (gsi
);
300 if (is_gimple_debug (stmt
))
303 loop
= loop_containing_stmt (stmt
);
304 if (!loop_in_sese_p (loop
, region
))
307 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
310 return new_gimple_bb (bb
, drs
);
313 /* Returns true if all predecessors of BB, that are not dominated by BB, are
314 marked in MAP. The predecessors dominated by BB are loop latches and will
315 be handled after BB. */
318 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
323 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
324 if (!TEST_BIT (map
, e
->src
->index
)
325 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
331 /* Compare the depth of two basic_block's P1 and P2. */
334 compare_bb_depths (const void *p1
, const void *p2
)
336 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
337 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
338 int d1
= loop_depth (bb1
->loop_father
);
339 int d2
= loop_depth (bb2
->loop_father
);
350 /* Sort the basic blocks from DOM such that the first are the ones at
351 a deepest loop level. */
354 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
356 VEC_qsort (basic_block
, dom
, compare_bb_depths
);
359 /* Recursive helper function for build_scops_bbs. */
362 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
364 sese region
= SCOP_REGION (scop
);
365 VEC (basic_block
, heap
) *dom
;
368 if (TEST_BIT (visited
, bb
->index
)
369 || !bb_in_sese_p (bb
, region
))
372 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
373 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
374 SET_BIT (visited
, bb
->index
);
376 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
381 graphite_sort_dominated_info (dom
);
383 while (!VEC_empty (basic_block
, dom
))
388 FOR_EACH_VEC_ELT (basic_block
, dom
, i
, dom_bb
)
389 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
391 build_scop_bbs_1 (scop
, visited
, dom_bb
);
392 VEC_unordered_remove (basic_block
, dom
, i
);
397 VEC_free (basic_block
, heap
, dom
);
400 /* Gather the basic blocks belonging to the SCOP. */
403 build_scop_bbs (scop_p scop
)
405 sbitmap visited
= sbitmap_alloc (last_basic_block
);
406 sese region
= SCOP_REGION (scop
);
408 sbitmap_zero (visited
);
409 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
410 sbitmap_free (visited
);
413 /* Return an ISL identifier for the polyhedral basic block PBB. */
416 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
419 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
420 return isl_id_alloc (s
->ctx
, name
, pbb
);
423 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
424 We generate SCATTERING_DIMENSIONS scattering dimensions.
426 CLooG 0.15.0 and previous versions require, that all
427 scattering functions of one CloogProgram have the same number of
428 scattering dimensions, therefore we allow to specify it. This
429 should be removed in future versions of CLooG.
431 The scattering polyhedron consists of these dimensions: scattering,
432 loop_iterators, parameters.
436 | scattering_dimensions = 5
437 | used_scattering_dimensions = 3
445 | Scattering polyhedron:
447 | scattering: {s1, s2, s3, s4, s5}
448 | loop_iterators: {i}
449 | parameters: {p1, p2}
451 | s1 s2 s3 s4 s5 i p1 p2 1
452 | 1 0 0 0 0 0 0 0 -4 = 0
453 | 0 1 0 0 0 -1 0 0 0 = 0
454 | 0 0 1 0 0 0 0 0 -5 = 0 */
457 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
458 poly_bb_p pbb
, int scattering_dimensions
)
461 int nb_iterators
= pbb_dim_iter_domain (pbb
);
462 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
466 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
470 dc
= isl_set_get_space (pbb
->domain
);
471 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
472 isl_dim_out
, scattering_dimensions
);
473 pbb
->schedule
= isl_map_universe (dm
);
475 for (i
= 0; i
< scattering_dimensions
; i
++)
477 /* Textual order inside this loop. */
480 isl_constraint
*c
= isl_equality_alloc
481 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
483 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
487 isl_int_neg (val
, val
);
488 c
= isl_constraint_set_constant (c
, val
);
489 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
490 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
493 /* Iterations of this loop. */
494 else /* if ((i % 2) == 1) */
496 int loop
= (i
- 1) / 2;
497 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
504 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
507 /* Build for BB the static schedule.
509 The static schedule is a Dewey numbering of the abstract syntax
510 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
512 The following example informally defines the static schedule:
531 Static schedules for A to F:
544 build_scop_scattering (scop_p scop
)
548 gimple_bb_p previous_gbb
= NULL
;
549 isl_space
*dc
= isl_set_get_space (scop
->context
);
550 isl_aff
*static_sched
;
552 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops());
553 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
555 /* We have to start schedules at 0 on the first component and
556 because we cannot compare_prefix_loops against a previous loop,
557 prefix will be equal to zero, and that index will be
558 incremented before copying. */
559 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
561 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
563 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
565 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
568 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
574 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
576 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
579 isl_aff_free (static_sched
);
582 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
584 /* Extract an affine expression from the chain of recurrence E. */
587 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
589 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
590 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
591 isl_local_space
*ls
= isl_local_space_from_space (space
);
592 unsigned pos
= sese_loop_depth ((sese
) s
->region
,
593 get_loop (CHREC_VARIABLE (e
))) - 1;
594 isl_aff
*loop
= isl_aff_set_coefficient_si
595 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
596 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
598 /* Before multiplying, make sure that the result is affine. */
599 gcc_assert (isl_pw_aff_is_cst (rhs
)
600 || isl_pw_aff_is_cst (l
));
602 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
605 /* Extract an affine expression from the mult_expr E. */
608 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
610 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
611 isl_space_copy (space
));
612 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
614 if (!isl_pw_aff_is_cst (lhs
)
615 && !isl_pw_aff_is_cst (rhs
))
617 isl_pw_aff_free (lhs
);
618 isl_pw_aff_free (rhs
);
622 return isl_pw_aff_mul (lhs
, rhs
);
625 /* Return an ISL identifier from the name of the ssa_name E. */
628 isl_id_for_ssa_name (scop_p s
, tree e
)
630 const char *name
= get_name (e
);
634 id
= isl_id_alloc (s
->ctx
, name
, e
);
638 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
639 id
= isl_id_alloc (s
->ctx
, name1
, e
);
645 /* Return an ISL identifier for the data reference DR. */
648 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
650 /* Data references all get the same isl_id. They need to be comparable
651 and are distinguished through the first dimension, which contains the
653 return isl_id_alloc (s
->ctx
, "", 0);
656 /* Extract an affine expression from the ssa_name E. */
659 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
666 id
= isl_id_for_ssa_name (s
, e
);
667 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
669 dom
= isl_set_universe (isl_space_copy (space
));
670 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
671 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
672 return isl_pw_aff_alloc (dom
, aff
);
675 /* Extract an affine expression from the gmp constant G. */
678 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
680 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
681 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
682 isl_set
*dom
= isl_set_universe (space
);
686 isl_int_set_gmp (v
, g
);
687 aff
= isl_aff_add_constant (aff
, v
);
690 return isl_pw_aff_alloc (dom
, aff
);
693 /* Extract an affine expression from the integer_cst E. */
696 extract_affine_int (tree e
, __isl_take isl_space
*space
)
702 tree_int_to_gmp (e
, g
);
703 res
= extract_affine_gmp (g
, space
);
709 /* Compute pwaff mod 2^width. */
712 wrap (isl_pw_aff
*pwaff
, unsigned width
)
717 isl_int_set_si (mod
, 1);
718 isl_int_mul_2exp (mod
, mod
, width
);
720 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
727 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
728 Otherwise returns -1. */
731 parameter_index_in_region_1 (tree name
, sese region
)
736 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
738 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (region
), i
, p
)
745 /* When the parameter NAME is in REGION, returns its index in
746 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
747 and returns the index of NAME. */
750 parameter_index_in_region (tree name
, sese region
)
754 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
756 i
= parameter_index_in_region_1 (name
, region
);
760 gcc_assert (SESE_ADD_PARAMS (region
));
762 i
= VEC_length (tree
, SESE_PARAMS (region
));
763 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
767 /* Extract an affine expression from the tree E in the scop S. */
770 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
772 isl_pw_aff
*lhs
, *rhs
, *res
;
775 if (e
== chrec_dont_know
) {
776 isl_space_free (space
);
780 switch (TREE_CODE (e
))
782 case POLYNOMIAL_CHREC
:
783 res
= extract_affine_chrec (s
, e
, space
);
787 res
= extract_affine_mul (s
, e
, space
);
791 case POINTER_PLUS_EXPR
:
792 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
793 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
794 res
= isl_pw_aff_add (lhs
, rhs
);
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_sub (lhs
, rhs
);
805 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
806 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
807 res
= isl_pw_aff_mul (lhs
, rhs
);
811 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
812 res
= extract_affine_name (s
, e
, space
);
816 res
= extract_affine_int (e
, space
);
817 /* No need to wrap a single integer. */
821 case NON_LVALUE_EXPR
:
822 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
830 type
= TREE_TYPE (e
);
831 if (TYPE_UNSIGNED (type
))
832 res
= wrap (res
, TYPE_PRECISION (type
));
837 /* In the context of sese S, scan the expression E and translate it to
838 a linear expression C. When parsing a symbolic multiplication, K
839 represents the constant multiplier of an expression containing
843 scan_tree_for_params (sese s
, tree e
)
845 if (e
== chrec_dont_know
)
848 switch (TREE_CODE (e
))
850 case POLYNOMIAL_CHREC
:
851 scan_tree_for_params (s
, CHREC_LEFT (e
));
855 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
856 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
858 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
862 case POINTER_PLUS_EXPR
:
864 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
865 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
871 case NON_LVALUE_EXPR
:
872 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
876 parameter_index_in_region (e
, s
);
889 /* Find parameters with respect to REGION in BB. We are looking in memory
890 access functions, conditions and loop bounds. */
893 find_params_in_bb (sese region
, gimple_bb_p gbb
)
899 loop_p loop
= GBB_BB (gbb
)->loop_father
;
901 /* Find parameters in the access functions of data references. */
902 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
903 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
904 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
906 /* Find parameters in conditional statements. */
907 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
909 tree lhs
= scalar_evolution_in_region (region
, loop
,
910 gimple_cond_lhs (stmt
));
911 tree rhs
= scalar_evolution_in_region (region
, loop
,
912 gimple_cond_rhs (stmt
));
914 scan_tree_for_params (region
, lhs
);
915 scan_tree_for_params (region
, rhs
);
919 /* Record the parameters used in the SCOP. A variable is a parameter
920 in a scop if it does not vary during the execution of that scop. */
923 find_scop_parameters (scop_p scop
)
927 sese region
= SCOP_REGION (scop
);
931 /* Find the parameters used in the loop bounds. */
932 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
934 tree nb_iters
= number_of_latch_executions (loop
);
936 if (!chrec_contains_symbols (nb_iters
))
939 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
940 scan_tree_for_params (region
, nb_iters
);
943 /* Find the parameters used in data accesses. */
944 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
945 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
947 nbp
= sese_nb_params (region
);
948 scop_set_nb_params (scop
, nbp
);
949 SESE_ADD_PARAMS (region
) = false;
953 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
955 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (region
), i
, e
)
956 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
957 isl_id_for_ssa_name (scop
, e
));
959 scop
->context
= isl_set_universe (space
);
963 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
964 the constraints for the surrounding loops. */
967 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
969 isl_set
*outer
, isl_set
**doms
)
971 tree nb_iters
= number_of_latch_executions (loop
);
972 sese region
= SCOP_REGION (scop
);
974 isl_set
*inner
= isl_set_copy (outer
);
977 int pos
= isl_set_dim (outer
, isl_dim_set
);
984 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
985 space
= isl_set_get_space (inner
);
988 c
= isl_inequality_alloc
989 (isl_local_space_from_space (isl_space_copy (space
)));
990 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
991 inner
= isl_set_add_constraint (inner
, c
);
993 /* loop_i <= cst_nb_iters */
994 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
996 c
= isl_inequality_alloc
997 (isl_local_space_from_space(isl_space_copy (space
)));
998 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
999 tree_int_to_gmp (nb_iters
, g
);
1000 isl_int_set_gmp (v
, g
);
1001 c
= isl_constraint_set_constant (c
, v
);
1002 inner
= isl_set_add_constraint (inner
, c
);
1005 /* loop_i <= expr_nb_iters */
1006 else if (!chrec_contains_undetermined (nb_iters
))
1011 isl_local_space
*ls
;
1015 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1017 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1018 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1019 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1020 isl_set_dim (valid
, isl_dim_set
));
1021 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1023 ls
= isl_local_space_from_space (isl_space_copy (space
));
1024 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1025 isl_dim_in
, pos
, 1);
1026 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1027 isl_pw_aff_copy (aff
));
1028 inner
= isl_set_intersect (inner
, le
);
1030 if (max_stmt_executions (loop
, &nit
))
1032 /* Insert in the context the constraints from the
1033 estimation of the number of iterations NIT and the
1034 symbolic number of iterations (involving parameter
1035 names) NB_ITERS. First, build the affine expression
1036 "NIT - NB_ITERS" and then say that it is positive,
1037 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1044 mpz_set_double_int (g
, nit
, false);
1045 mpz_sub_ui (g
, g
, 1);
1046 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1047 x
= isl_pw_aff_ge_set (approx
, aff
);
1048 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1049 isl_set_dim (x
, isl_dim_set
));
1050 scop
->context
= isl_set_intersect (scop
->context
, x
);
1052 c
= isl_inequality_alloc
1053 (isl_local_space_from_space (isl_space_copy (space
)));
1054 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1055 isl_int_set_gmp (v
, g
);
1057 c
= isl_constraint_set_constant (c
, v
);
1058 inner
= isl_set_add_constraint (inner
, c
);
1064 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1065 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1066 isl_set_copy (inner
), doms
);
1070 && loop_in_sese_p (loop
->next
, region
))
1071 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1072 isl_set_copy (outer
), doms
);
1074 doms
[loop
->num
] = inner
;
1076 isl_set_free (outer
);
1077 isl_space_free (space
);
1082 /* Returns a linear expression for tree T evaluated in PBB. */
1085 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1087 scop_p scop
= PBB_SCOP (pbb
);
1089 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1090 gcc_assert (!automatically_generated_chrec_p (t
));
1092 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1095 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1096 operator. This allows us to invert the condition or to handle
1100 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1102 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1103 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1109 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1113 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1117 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1121 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1125 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1133 isl_pw_aff_free(lhs
);
1134 isl_pw_aff_free(rhs
);
1138 cond
= isl_set_coalesce (cond
);
1139 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1140 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1143 /* Add conditions to the domain of PBB. */
1146 add_conditions_to_domain (poly_bb_p pbb
)
1150 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1152 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1155 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
1156 switch (gimple_code (stmt
))
1160 enum tree_code code
= gimple_cond_code (stmt
);
1162 /* The conditions for ELSE-branches are inverted. */
1163 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1164 code
= invert_tree_comparison (code
, false);
1166 add_condition_to_pbb (pbb
, stmt
, code
);
1171 /* Switch statements are not supported right now - fall through. */
1179 /* Traverses all the GBBs of the SCOP and add their constraints to the
1180 iteration domains. */
1183 add_conditions_to_constraints (scop_p scop
)
1188 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1189 add_conditions_to_domain (pbb
);
1192 /* Structure used to pass data to dom_walk. */
1196 VEC (gimple
, heap
) **conditions
, **cases
;
1200 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1201 edge between BB and its predecessor is not a loop exit edge, and
1202 the last statement of the single predecessor is a COND_EXPR. */
1205 single_pred_cond_non_loop_exit (basic_block bb
)
1207 if (single_pred_p (bb
))
1209 edge e
= single_pred_edge (bb
);
1210 basic_block pred
= e
->src
;
1213 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1216 stmt
= last_stmt (pred
);
1218 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1225 /* Call-back for dom_walk executed before visiting the dominated
1229 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1232 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1233 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1234 VEC (gimple
, heap
) **cases
= data
->cases
;
1238 if (!bb_in_sese_p (bb
, data
->region
))
1241 stmt
= single_pred_cond_non_loop_exit (bb
);
1245 edge e
= single_pred_edge (bb
);
1247 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1249 if (e
->flags
& EDGE_TRUE_VALUE
)
1250 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1252 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1255 gbb
= gbb_from_bb (bb
);
1259 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1260 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1264 /* Call-back for dom_walk executed after visiting the dominated
1268 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1271 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1272 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1273 VEC (gimple
, heap
) **cases
= data
->cases
;
1275 if (!bb_in_sese_p (bb
, data
->region
))
1278 if (single_pred_cond_non_loop_exit (bb
))
1280 VEC_pop (gimple
, *conditions
);
1281 VEC_pop (gimple
, *cases
);
1285 /* Record all conditions in REGION. */
1288 build_sese_conditions (sese region
)
1290 struct dom_walk_data walk_data
;
1291 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1292 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1295 data
.conditions
= &conditions
;
1296 data
.cases
= &cases
;
1297 data
.region
= region
;
1299 walk_data
.dom_direction
= CDI_DOMINATORS
;
1300 walk_data
.initialize_block_local_data
= NULL
;
1301 walk_data
.before_dom_children
= build_sese_conditions_before
;
1302 walk_data
.after_dom_children
= build_sese_conditions_after
;
1303 walk_data
.global_data
= &data
;
1304 walk_data
.block_local_data_size
= 0;
1306 init_walk_dominator_tree (&walk_data
);
1307 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1308 fini_walk_dominator_tree (&walk_data
);
1310 VEC_free (gimple
, heap
, conditions
);
1311 VEC_free (gimple
, heap
, cases
);
1314 /* Add constraints on the possible values of parameter P from the type
1318 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1320 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1321 tree type
= TREE_TYPE (parameter
);
1322 tree lb
= NULL_TREE
;
1323 tree ub
= NULL_TREE
;
1325 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1326 lb
= lower_bound_in_type (type
, type
);
1328 lb
= TYPE_MIN_VALUE (type
);
1330 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1331 ub
= upper_bound_in_type (type
, type
);
1333 ub
= TYPE_MAX_VALUE (type
);
1337 isl_space
*space
= isl_set_get_space (scop
->context
);
1342 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1345 tree_int_to_gmp (lb
, g
);
1346 isl_int_set_gmp (v
, g
);
1349 c
= isl_constraint_set_constant (c
, v
);
1351 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1353 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1358 isl_space
*space
= isl_set_get_space (scop
->context
);
1363 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1367 tree_int_to_gmp (ub
, g
);
1368 isl_int_set_gmp (v
, g
);
1370 c
= isl_constraint_set_constant (c
, v
);
1372 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1374 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1378 /* Build the context of the SCOP. The context usually contains extra
1379 constraints that are added to the iteration domains that constrain
1383 build_scop_context (scop_p scop
)
1385 graphite_dim_t p
, n
= scop_nb_params (scop
);
1387 for (p
= 0; p
< n
; p
++)
1388 add_param_constraints (scop
, p
);
1391 /* Build the iteration domains: the loops belonging to the current
1392 SCOP, and that vary for the execution of the current basic block.
1393 Returns false if there is no loop in SCOP. */
1396 build_scop_iteration_domain (scop_p scop
)
1399 sese region
= SCOP_REGION (scop
);
1402 int nb_loops
= number_of_loops ();
1403 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1405 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
1406 if (!loop_in_sese_p (loop_outer (loop
), region
))
1407 build_loop_iteration_domains (scop
, loop
, 0,
1408 isl_set_copy (scop
->context
), doms
);
1410 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1412 loop
= pbb_loop (pbb
);
1414 if (doms
[loop
->num
])
1415 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1417 pbb
->domain
= isl_set_copy (scop
->context
);
1419 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1420 isl_id_for_pbb (scop
, pbb
));
1423 for (i
= 0; i
< nb_loops
; i
++)
1425 isl_set_free (doms
[i
]);
1430 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1431 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1432 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1436 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1439 int alias_set_num
= 0;
1440 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1442 if (bap
&& bap
->alias_set
)
1443 alias_set_num
= *(bap
->alias_set
);
1445 c
= isl_equality_alloc
1446 (isl_local_space_from_space (isl_map_get_space (acc
)));
1447 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1448 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1450 return isl_map_add_constraint (acc
, c
);
1453 /* Assign the affine expression INDEX to the output dimension POS of
1454 MAP and return the result. */
1457 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1460 int len
= isl_map_dim (map
, isl_dim_out
);
1463 index_map
= isl_map_from_pw_aff (index
);
1464 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1465 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1467 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1468 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1469 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1470 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1472 return isl_map_intersect (map
, index_map
);
1475 /* Add to ACCESSES polyhedron equalities defining the access functions
1476 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1477 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1478 PBB is the poly_bb_p that contains the data reference DR. */
1481 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1483 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1484 scop_p scop
= PBB_SCOP (pbb
);
1486 for (i
= 0; i
< nb_subscripts
; i
++)
1489 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1491 aff
= extract_affine (scop
, afn
,
1492 isl_space_domain (isl_map_get_space (acc
)));
1493 acc
= set_index (acc
, i
+ 1, aff
);
1499 /* Add constrains representing the size of the accessed data to the
1500 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1501 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1505 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1507 tree ref
= DR_REF (dr
);
1508 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1510 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1514 if (TREE_CODE (ref
) != ARRAY_REF
)
1517 low
= array_ref_low_bound (ref
);
1518 high
= array_ref_up_bound (ref
);
1520 /* XXX The PPL code dealt separately with
1521 subscript - low >= 0 and high - subscript >= 0 in case one of
1522 the two bounds isn't known. Do the same here? */
1524 if (host_integerp (low
, 0)
1526 && host_integerp (high
, 0)
1527 /* 1-element arrays at end of structures may extend over
1528 their declared size. */
1529 && !(array_at_struct_end_p (ref
)
1530 && operand_equal_p (low
, high
, 0)))
1534 isl_set
*univ
, *lbs
, *ubs
;
1538 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1539 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1542 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1543 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1544 isl_set_dim (valid
, isl_dim_set
));
1545 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1547 space
= isl_set_get_space (extent
);
1548 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1549 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1550 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1551 index
= isl_pw_aff_alloc (univ
, aff
);
1553 id
= isl_set_get_tuple_id (extent
);
1554 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1555 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1557 /* low <= sub_i <= high */
1558 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1559 ubs
= isl_pw_aff_le_set (index
, ub
);
1560 extent
= isl_set_intersect (extent
, lbs
);
1561 extent
= isl_set_intersect (extent
, ubs
);
1568 /* Build data accesses for DR in PBB. */
1571 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1573 int dr_base_object_set
;
1576 scop_p scop
= PBB_SCOP (pbb
);
1579 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1580 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1581 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1582 isl_dim_out
, nb_out
);
1584 acc
= isl_map_universe (space
);
1585 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1588 acc
= pdr_add_alias_set (acc
, dr
);
1589 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1592 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1593 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1594 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1595 int alias_set_num
= 0;
1596 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1598 if (bap
&& bap
->alias_set
)
1599 alias_set_num
= *(bap
->alias_set
);
1601 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1602 extent
= isl_set_nat_universe (space
);
1603 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1604 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1607 gcc_assert (dr
->aux
);
1608 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1610 new_poly_dr (pbb
, dr_base_object_set
,
1611 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1612 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1615 /* Write to FILE the alias graph of data references in DIMACS format. */
1618 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1619 VEC (data_reference_p
, heap
) *drs
)
1621 int num_vertex
= VEC_length (data_reference_p
, drs
);
1623 data_reference_p dr1
, dr2
;
1626 if (num_vertex
== 0)
1629 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1630 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1631 if (dr_may_alias_p (dr1
, dr2
, true))
1634 fprintf (file
, "$\n");
1637 fprintf (file
, "c %s\n", comment
);
1639 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1641 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1642 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1643 if (dr_may_alias_p (dr1
, dr2
, true))
1644 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1649 /* Write to FILE the alias graph of data references in DOT format. */
1652 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1653 VEC (data_reference_p
, heap
) *drs
)
1655 int num_vertex
= VEC_length (data_reference_p
, drs
);
1656 data_reference_p dr1
, dr2
;
1659 if (num_vertex
== 0)
1662 fprintf (file
, "$\n");
1665 fprintf (file
, "c %s\n", comment
);
1667 /* First print all the vertices. */
1668 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1669 fprintf (file
, "n%d;\n", i
);
1671 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1672 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1673 if (dr_may_alias_p (dr1
, dr2
, true))
1674 fprintf (file
, "n%d n%d\n", i
, j
);
1679 /* Write to FILE the alias graph of data references in ECC format. */
1682 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1683 VEC (data_reference_p
, heap
) *drs
)
1685 int num_vertex
= VEC_length (data_reference_p
, drs
);
1686 data_reference_p dr1
, dr2
;
1689 if (num_vertex
== 0)
1692 fprintf (file
, "$\n");
1695 fprintf (file
, "c %s\n", comment
);
1697 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1698 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1699 if (dr_may_alias_p (dr1
, dr2
, true))
1700 fprintf (file
, "%d %d\n", i
, j
);
1705 /* Check if DR1 and DR2 are in the same object set. */
1708 dr_same_base_object_p (const struct data_reference
*dr1
,
1709 const struct data_reference
*dr2
)
1711 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1714 /* Uses DFS component number as representative of alias-sets. Also tests for
1715 optimality by verifying if every connected component is a clique. Returns
1716 true (1) if the above test is true, and false (0) otherwise. */
1719 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1721 int num_vertices
= VEC_length (data_reference_p
, drs
);
1722 struct graph
*g
= new_graph (num_vertices
);
1723 data_reference_p dr1
, dr2
;
1725 int num_connected_components
;
1726 int v_indx1
, v_indx2
, num_vertices_in_component
;
1729 struct graph_edge
*e
;
1730 int this_component_is_clique
;
1731 int all_components_are_cliques
= 1;
1733 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1734 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1735 if (dr_may_alias_p (dr1
, dr2
, true))
1741 all_vertices
= XNEWVEC (int, num_vertices
);
1742 vertices
= XNEWVEC (int, num_vertices
);
1743 for (i
= 0; i
< num_vertices
; i
++)
1744 all_vertices
[i
] = i
;
1746 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1748 for (i
= 0; i
< g
->n_vertices
; i
++)
1750 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1751 base_alias_pair
*bap
;
1753 gcc_assert (dr
->aux
);
1754 bap
= (base_alias_pair
*)(dr
->aux
);
1756 bap
->alias_set
= XNEW (int);
1757 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1760 /* Verify if the DFS numbering results in optimal solution. */
1761 for (i
= 0; i
< num_connected_components
; i
++)
1763 num_vertices_in_component
= 0;
1764 /* Get all vertices whose DFS component number is the same as i. */
1765 for (j
= 0; j
< num_vertices
; j
++)
1766 if (g
->vertices
[j
].component
== i
)
1767 vertices
[num_vertices_in_component
++] = j
;
1769 /* Now test if the vertices in 'vertices' form a clique, by testing
1770 for edges among each pair. */
1771 this_component_is_clique
= 1;
1772 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1774 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1776 /* Check if the two vertices are connected by iterating
1777 through all the edges which have one of these are source. */
1778 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1781 if (e
->src
== vertices
[v_indx1
])
1787 this_component_is_clique
= 0;
1791 if (!this_component_is_clique
)
1792 all_components_are_cliques
= 0;
1796 free (all_vertices
);
1799 return all_components_are_cliques
;
1802 /* Group each data reference in DRS with its base object set num. */
1805 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1807 int num_vertex
= VEC_length (data_reference_p
, drs
);
1808 struct graph
*g
= new_graph (num_vertex
);
1809 data_reference_p dr1
, dr2
;
1813 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1814 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1815 if (dr_same_base_object_p (dr1
, dr2
))
1821 queue
= XNEWVEC (int, num_vertex
);
1822 for (i
= 0; i
< num_vertex
; i
++)
1825 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1827 for (i
= 0; i
< g
->n_vertices
; i
++)
1829 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1830 base_alias_pair
*bap
;
1832 gcc_assert (dr
->aux
);
1833 bap
= (base_alias_pair
*)(dr
->aux
);
1835 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1842 /* Build the data references for PBB. */
1845 build_pbb_drs (poly_bb_p pbb
)
1848 data_reference_p dr
;
1849 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1851 FOR_EACH_VEC_ELT (data_reference_p
, gbb_drs
, j
, dr
)
1852 build_poly_dr (dr
, pbb
);
1855 /* Dump to file the alias graphs for the data references in DRS. */
1858 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
1861 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1863 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1866 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1867 current_function_name ());
1868 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1869 fclose (file_dimacs
);
1872 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1875 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1876 current_function_name ());
1877 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1881 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1884 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1885 current_function_name ());
1886 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1891 /* Build data references in SCOP. */
1894 build_scop_drs (scop_p scop
)
1898 data_reference_p dr
;
1899 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1901 /* Remove all the PBBs that do not have data references: these basic
1902 blocks are not handled in the polyhedral representation. */
1903 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1904 if (VEC_empty (data_reference_p
, GBB_DATA_REFS (PBB_BLACK_BOX (pbb
))))
1906 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1908 VEC_ordered_remove (poly_bb_p
, SCOP_BBS (scop
), i
);
1912 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1913 for (j
= 0; VEC_iterate (data_reference_p
,
1914 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
1915 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1917 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr
)
1918 dr
->aux
= XNEW (base_alias_pair
);
1920 if (!build_alias_set_optimal_p (drs
))
1922 /* TODO: Add support when building alias set is not optimal. */
1926 build_base_obj_set_for_drs (drs
);
1928 /* When debugging, enable the following code. This cannot be used
1929 in production compilers. */
1931 dump_alias_graphs (drs
);
1933 VEC_free (data_reference_p
, heap
, drs
);
1935 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1936 build_pbb_drs (pbb
);
1939 /* Return a gsi at the position of the phi node STMT. */
1941 static gimple_stmt_iterator
1942 gsi_for_phi_node (gimple stmt
)
1944 gimple_stmt_iterator psi
;
1945 basic_block bb
= gimple_bb (stmt
);
1947 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1948 if (stmt
== gsi_stmt (psi
))
1955 /* Analyze all the data references of STMTS and add them to the
1956 GBB_DATA_REFS vector of BB. */
1959 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, VEC (gimple
, heap
) *stmts
)
1965 sese region
= SCOP_REGION (scop
);
1967 if (!bb_in_sese_p (bb
, region
))
1970 nest
= outermost_loop_in_sese_1 (region
, bb
);
1971 gbb
= gbb_from_bb (bb
);
1973 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
1977 if (is_gimple_debug (stmt
))
1980 loop
= loop_containing_stmt (stmt
);
1981 if (!loop_in_sese_p (loop
, region
))
1984 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1985 &GBB_DATA_REFS (gbb
));
1989 /* Insert STMT at the end of the STMTS sequence and then insert the
1990 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1994 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1995 gimple_stmt_iterator insert_gsi
)
1997 gimple_stmt_iterator gsi
;
1998 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2000 gimple_seq_add_stmt (&stmts
, stmt
);
2001 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2002 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2004 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2005 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2006 VEC_free (gimple
, heap
, x
);
2009 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2012 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2015 gimple_stmt_iterator gsi
;
2016 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2017 gimple stmt
= gimple_build_assign (res
, var
);
2018 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2020 gimple_seq_add_stmt (&stmts
, stmt
);
2021 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2022 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2024 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2026 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2027 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2031 gsi
= gsi_for_stmt (after_stmt
);
2032 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2035 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2036 VEC_free (gimple
, heap
, x
);
2039 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2042 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2044 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2045 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2046 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2047 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2048 int index
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
2050 /* The INDEX of PBB in SCOP_BBS. */
2051 for (index
= 0; index
< n
; index
++)
2052 if (VEC_index (poly_bb_p
, SCOP_BBS (scop
), index
) == pbb
)
2055 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2057 GBB_PBB (gbb1
) = pbb1
;
2058 GBB_CONDITIONS (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITIONS (gbb
));
2059 GBB_CONDITION_CASES (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
2060 VEC_safe_insert (poly_bb_p
, heap
, SCOP_BBS (scop
), index
+ 1, pbb1
);
2063 /* Insert on edge E the assignment "RES := EXPR". */
2066 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2068 gimple_stmt_iterator gsi
;
2069 gimple_seq stmts
= NULL
;
2070 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2071 gimple stmt
= gimple_build_assign (res
, var
);
2073 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2075 gimple_seq_add_stmt (&stmts
, stmt
);
2076 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2077 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2079 gsi_insert_seq_on_edge (e
, stmts
);
2080 gsi_commit_edge_inserts ();
2081 bb
= gimple_bb (stmt
);
2083 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2086 if (!gbb_from_bb (bb
))
2087 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2089 analyze_drs_in_stmts (scop
, bb
, x
);
2090 VEC_free (gimple
, heap
, x
);
2093 /* Creates a zero dimension array of the same type as VAR. */
2096 create_zero_dim_array (tree var
, const char *base_name
)
2098 tree index_type
= build_index_type (integer_zero_node
);
2099 tree elt_type
= TREE_TYPE (var
);
2100 tree array_type
= build_array_type (elt_type
, index_type
);
2101 tree base
= create_tmp_var (array_type
, base_name
);
2103 add_referenced_var (base
);
2105 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2109 /* Returns true when PHI is a loop close phi node. */
2112 scalar_close_phi_node_p (gimple phi
)
2114 if (gimple_code (phi
) != GIMPLE_PHI
2115 || !is_gimple_reg (gimple_phi_result (phi
)))
2118 /* Note that loop close phi nodes should have a single argument
2119 because we translated the representation into a canonical form
2120 before Graphite: see canonicalize_loop_closed_ssa_form. */
2121 return (gimple_phi_num_args (phi
) == 1);
2124 /* For a definition DEF in REGION, propagates the expression EXPR in
2125 all the uses of DEF outside REGION. */
2128 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2130 imm_use_iterator imm_iter
;
2133 bool replaced_once
= false;
2135 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2137 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2140 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2141 if (!is_gimple_debug (use_stmt
)
2142 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2145 use_operand_p use_p
;
2147 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2148 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2149 && (replaced_once
= true))
2150 replace_exp (use_p
, expr
);
2152 update_stmt (use_stmt
);
2157 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2158 gsi_commit_edge_inserts ();
2162 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2163 dimension array for it. */
2166 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2168 sese region
= SCOP_REGION (scop
);
2169 gimple phi
= gsi_stmt (*psi
);
2170 tree res
= gimple_phi_result (phi
);
2171 tree var
= SSA_NAME_VAR (res
);
2172 basic_block bb
= gimple_bb (phi
);
2173 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2174 tree arg
= gimple_phi_arg_def (phi
, 0);
2177 /* Note that loop close phi nodes should have a single argument
2178 because we translated the representation into a canonical form
2179 before Graphite: see canonicalize_loop_closed_ssa_form. */
2180 gcc_assert (gimple_phi_num_args (phi
) == 1);
2182 /* The phi node can be a non close phi node, when its argument is
2183 invariant, or a default definition. */
2184 if (is_gimple_min_invariant (arg
)
2185 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2187 propagate_expr_outside_region (res
, arg
, region
);
2192 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2194 propagate_expr_outside_region (res
, arg
, region
);
2195 stmt
= gimple_build_assign (res
, arg
);
2196 remove_phi_node (psi
, false);
2197 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2198 SSA_NAME_DEF_STMT (res
) = stmt
;
2202 /* If res is scev analyzable and is not a scalar value, it is safe
2203 to ignore the close phi node: it will be code generated in the
2204 out of Graphite pass. */
2205 else if (scev_analyzable_p (res
, region
))
2207 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2210 if (!loop_in_sese_p (loop
, region
))
2212 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2213 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2214 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2217 scev
= scalar_evolution_in_region (region
, loop
, res
);
2219 if (tree_does_not_contain_chrecs (scev
))
2220 propagate_expr_outside_region (res
, scev
, region
);
2227 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2229 stmt
= gimple_build_assign (res
, zero_dim_array
);
2231 if (TREE_CODE (arg
) == SSA_NAME
)
2232 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2233 SSA_NAME_DEF_STMT (arg
));
2235 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2236 zero_dim_array
, arg
);
2239 remove_phi_node (psi
, false);
2240 SSA_NAME_DEF_STMT (res
) = stmt
;
2242 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2245 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2246 dimension array for it. */
2249 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2252 gimple phi
= gsi_stmt (*psi
);
2253 basic_block bb
= gimple_bb (phi
);
2254 tree res
= gimple_phi_result (phi
);
2255 tree var
= SSA_NAME_VAR (res
);
2256 tree zero_dim_array
= create_zero_dim_array (var
, "phi_out_of_ssa");
2260 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2262 tree arg
= gimple_phi_arg_def (phi
, i
);
2263 edge e
= gimple_phi_arg_edge (phi
, i
);
2265 /* Avoid the insertion of code in the loop latch to please the
2266 pattern matching of the vectorizer. */
2267 if (TREE_CODE (arg
) == SSA_NAME
2268 && e
->src
== bb
->loop_father
->latch
)
2269 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2270 SSA_NAME_DEF_STMT (arg
));
2272 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2275 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2277 stmt
= gimple_build_assign (res
, var
);
2278 remove_phi_node (psi
, false);
2279 SSA_NAME_DEF_STMT (res
) = stmt
;
2281 insert_stmts (scop
, stmt
, stmts
, gsi_after_labels (bb
));
2284 /* Rewrite the degenerate phi node at position PSI from the degenerate
2285 form "x = phi (y, y, ..., y)" to "x = y". */
2288 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2292 gimple_stmt_iterator gsi
;
2293 gimple phi
= gsi_stmt (*psi
);
2294 tree res
= gimple_phi_result (phi
);
2297 bb
= gimple_bb (phi
);
2298 rhs
= degenerate_phi_result (phi
);
2301 stmt
= gimple_build_assign (res
, rhs
);
2302 remove_phi_node (psi
, false);
2303 SSA_NAME_DEF_STMT (res
) = stmt
;
2305 gsi
= gsi_after_labels (bb
);
2306 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2309 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2312 rewrite_reductions_out_of_ssa (scop_p scop
)
2315 gimple_stmt_iterator psi
;
2316 sese region
= SCOP_REGION (scop
);
2319 if (bb_in_sese_p (bb
, region
))
2320 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2322 gimple phi
= gsi_stmt (psi
);
2324 if (!is_gimple_reg (gimple_phi_result (phi
)))
2330 if (gimple_phi_num_args (phi
) > 1
2331 && degenerate_phi_result (phi
))
2332 rewrite_degenerate_phi (&psi
);
2334 else if (scalar_close_phi_node_p (phi
))
2335 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2337 else if (reduction_phi_p (region
, &psi
))
2338 rewrite_phi_out_of_ssa (scop
, &psi
);
2341 update_ssa (TODO_update_ssa
);
2342 #ifdef ENABLE_CHECKING
2343 verify_loop_closed_ssa (true);
2347 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2348 read from ZERO_DIM_ARRAY. */
2351 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2352 tree def
, gimple use_stmt
)
2354 tree var
= SSA_NAME_VAR (def
);
2355 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2356 tree name
= make_ssa_name (var
, name_stmt
);
2358 use_operand_p use_p
;
2360 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2362 gimple_assign_set_lhs (name_stmt
, name
);
2363 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2365 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2366 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2367 replace_exp (use_p
, name
);
2369 update_stmt (use_stmt
);
2372 /* For every definition DEF in the SCOP that is used outside the scop,
2373 insert a closing-scop definition in the basic block just after this
2377 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2379 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2380 tree new_name
= make_ssa_name (var
, stmt
);
2381 bool needs_copy
= false;
2382 use_operand_p use_p
;
2383 imm_use_iterator imm_iter
;
2385 sese region
= SCOP_REGION (scop
);
2387 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2389 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2391 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2393 SET_USE (use_p
, new_name
);
2395 update_stmt (use_stmt
);
2400 /* Insert in the empty BB just after the scop a use of DEF such
2401 that the rewrite of cross_bb_scalar_dependences won't insert
2402 arrays everywhere else. */
2405 gimple assign
= gimple_build_assign (new_name
, def
);
2406 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2408 add_referenced_var (var
);
2409 SSA_NAME_DEF_STMT (new_name
) = assign
;
2410 update_stmt (assign
);
2411 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2415 /* Rewrite the scalar dependences crossing the boundary of the BB
2416 containing STMT with an array. Return true when something has been
2420 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2422 sese region
= SCOP_REGION (scop
);
2423 gimple stmt
= gsi_stmt (*gsi
);
2424 imm_use_iterator imm_iter
;
2427 tree zero_dim_array
= NULL_TREE
;
2431 switch (gimple_code (stmt
))
2434 def
= gimple_assign_lhs (stmt
);
2438 def
= gimple_call_lhs (stmt
);
2446 || !is_gimple_reg (def
))
2449 if (scev_analyzable_p (def
, region
))
2451 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2452 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2454 if (tree_contains_chrecs (scev
, NULL
))
2457 propagate_expr_outside_region (def
, scev
, region
);
2461 def_bb
= gimple_bb (stmt
);
2463 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2465 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2466 if (gimple_code (use_stmt
) == GIMPLE_PHI
2469 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2471 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2472 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2474 rewrite_phi_out_of_ssa (scop
, &psi
);
2477 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2478 if (gimple_code (use_stmt
) != GIMPLE_PHI
2479 && def_bb
!= gimple_bb (use_stmt
)
2480 && !is_gimple_debug (use_stmt
)
2483 if (!zero_dim_array
)
2485 zero_dim_array
= create_zero_dim_array
2486 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2487 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2488 SSA_NAME_DEF_STMT (def
));
2492 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2499 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2502 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2505 gimple_stmt_iterator psi
;
2506 sese region
= SCOP_REGION (scop
);
2507 bool changed
= false;
2509 /* Create an extra empty BB after the scop. */
2510 split_edge (SESE_EXIT (region
));
2513 if (bb_in_sese_p (bb
, region
))
2514 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2515 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2520 update_ssa (TODO_update_ssa
);
2521 #ifdef ENABLE_CHECKING
2522 verify_loop_closed_ssa (true);
2527 /* Returns the number of pbbs that are in loops contained in SCOP. */
2530 nb_pbbs_in_loops (scop_p scop
)
2536 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2537 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2543 /* Return the number of data references in BB that write in
2547 nb_data_writes_in_bb (basic_block bb
)
2550 gimple_stmt_iterator gsi
;
2552 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2553 if (gimple_vdef (gsi_stmt (gsi
)))
2559 /* Splits at STMT the basic block BB represented as PBB in the
2563 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2565 edge e1
= split_block (bb
, stmt
);
2566 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2570 /* Splits STMT out of its current BB. This is done for reduction
2571 statements for which we want to ignore data dependences. */
2574 split_reduction_stmt (scop_p scop
, gimple stmt
)
2576 basic_block bb
= gimple_bb (stmt
);
2577 poly_bb_p pbb
= pbb_from_bb (bb
);
2578 gimple_bb_p gbb
= gbb_from_bb (bb
);
2581 data_reference_p dr
;
2583 /* Do not split basic blocks with no writes to memory: the reduction
2584 will be the only write to memory. */
2585 if (nb_data_writes_in_bb (bb
) == 0
2586 /* Or if we have already marked BB as a reduction. */
2587 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2590 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2592 /* Split once more only when the reduction stmt is not the only one
2593 left in the original BB. */
2594 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2596 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2598 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2601 /* A part of the data references will end in a different basic block
2602 after the split: move the DRs from the original GBB to the newly
2604 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
2606 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2610 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2611 VEC_safe_push (data_reference_p
, heap
, GBB_DATA_REFS (gbb1
), dr
);
2612 VEC_ordered_remove (data_reference_p
, GBB_DATA_REFS (gbb
), i
);
2620 /* Return true when stmt is a reduction operation. */
2623 is_reduction_operation_p (gimple stmt
)
2625 enum tree_code code
;
2627 gcc_assert (is_gimple_assign (stmt
));
2628 code
= gimple_assign_rhs_code (stmt
);
2630 return flag_associative_math
2631 && commutative_tree_code (code
)
2632 && associative_tree_code (code
);
2635 /* Returns true when PHI contains an argument ARG. */
2638 phi_contains_arg (gimple phi
, tree arg
)
2642 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2643 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2649 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2652 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2656 if (TREE_CODE (arg
) != SSA_NAME
)
2659 stmt
= SSA_NAME_DEF_STMT (arg
);
2661 if (gimple_code (stmt
) == GIMPLE_NOP
2662 || gimple_code (stmt
) == GIMPLE_CALL
)
2665 if (gimple_code (stmt
) == GIMPLE_PHI
)
2667 if (phi_contains_arg (stmt
, lhs
))
2672 if (!is_gimple_assign (stmt
))
2675 if (gimple_num_ops (stmt
) == 2)
2676 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2678 if (is_reduction_operation_p (stmt
))
2680 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2683 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2689 /* Detect commutative and associative scalar reductions starting at
2690 the STMT. Return the phi node of the reduction cycle, or NULL. */
2693 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2694 VEC (gimple
, heap
) **in
,
2695 VEC (gimple
, heap
) **out
)
2697 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2702 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2703 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2707 /* Detect commutative and associative scalar reductions starting at
2708 STMT. Return the phi node of the reduction cycle, or NULL. */
2711 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2712 VEC (gimple
, heap
) **out
)
2714 tree lhs
= gimple_assign_lhs (stmt
);
2716 if (gimple_num_ops (stmt
) == 2)
2717 return detect_commutative_reduction_arg (lhs
, stmt
,
2718 gimple_assign_rhs1 (stmt
),
2721 if (is_reduction_operation_p (stmt
))
2723 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2724 gimple_assign_rhs1 (stmt
),
2727 : detect_commutative_reduction_arg (lhs
, stmt
,
2728 gimple_assign_rhs2 (stmt
),
2735 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2738 follow_inital_value_to_phi (tree arg
, tree lhs
)
2742 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2745 stmt
= SSA_NAME_DEF_STMT (arg
);
2747 if (gimple_code (stmt
) == GIMPLE_PHI
2748 && phi_contains_arg (stmt
, lhs
))
2755 /* Return the argument of the loop PHI that is the initial value coming
2756 from outside the loop. */
2759 edge_initial_value_for_loop_phi (gimple phi
)
2763 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2765 edge e
= gimple_phi_arg_edge (phi
, i
);
2767 if (loop_depth (e
->src
->loop_father
)
2768 < loop_depth (e
->dest
->loop_father
))
2775 /* Return the argument of the loop PHI that is the initial value coming
2776 from outside the loop. */
2779 initial_value_for_loop_phi (gimple phi
)
2783 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2785 edge e
= gimple_phi_arg_edge (phi
, i
);
2787 if (loop_depth (e
->src
->loop_father
)
2788 < loop_depth (e
->dest
->loop_father
))
2789 return gimple_phi_arg_def (phi
, i
);
2795 /* Returns true when DEF is used outside the reduction cycle of
2799 used_outside_reduction (tree def
, gimple loop_phi
)
2801 use_operand_p use_p
;
2802 imm_use_iterator imm_iter
;
2803 loop_p loop
= loop_containing_stmt (loop_phi
);
2805 /* In LOOP, DEF should be used only in LOOP_PHI. */
2806 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2808 gimple stmt
= USE_STMT (use_p
);
2810 if (stmt
!= loop_phi
2811 && !is_gimple_debug (stmt
)
2812 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2819 /* Detect commutative and associative scalar reductions belonging to
2820 the SCOP starting at the loop closed phi node STMT. Return the phi
2821 node of the reduction cycle, or NULL. */
2824 detect_commutative_reduction (scop_p scop
, gimple stmt
, VEC (gimple
, heap
) **in
,
2825 VEC (gimple
, heap
) **out
)
2827 if (scalar_close_phi_node_p (stmt
))
2829 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2830 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2832 if (TREE_CODE (arg
) != SSA_NAME
)
2835 /* Note that loop close phi nodes should have a single argument
2836 because we translated the representation into a canonical form
2837 before Graphite: see canonicalize_loop_closed_ssa_form. */
2838 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2840 def
= SSA_NAME_DEF_STMT (arg
);
2841 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2842 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2845 lhs
= gimple_phi_result (close_phi
);
2846 init
= initial_value_for_loop_phi (loop_phi
);
2847 phi
= follow_inital_value_to_phi (init
, lhs
);
2849 if (phi
&& (used_outside_reduction (lhs
, phi
)
2850 || !has_single_use (gimple_phi_result (phi
))))
2853 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2854 VEC_safe_push (gimple
, heap
, *out
, close_phi
);
2858 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2859 return detect_commutative_reduction_assign (stmt
, in
, out
);
2864 /* Translate the scalar reduction statement STMT to an array RED
2865 knowing that its recursive phi node is LOOP_PHI. */
2868 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2869 gimple stmt
, gimple loop_phi
)
2871 tree res
= gimple_phi_result (loop_phi
);
2872 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2873 gimple_stmt_iterator gsi
;
2875 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2877 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2878 gsi
= gsi_for_stmt (stmt
);
2880 insert_stmts (scop
, assign
, NULL
, gsi
);
2883 /* Removes the PHI node and resets all the debug stmts that are using
2887 remove_phi (gimple phi
)
2889 imm_use_iterator imm_iter
;
2891 use_operand_p use_p
;
2892 gimple_stmt_iterator gsi
;
2893 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2897 def
= PHI_RESULT (phi
);
2898 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2900 stmt
= USE_STMT (use_p
);
2902 if (is_gimple_debug (stmt
))
2904 gimple_debug_bind_reset_value (stmt
);
2905 VEC_safe_push (gimple
, heap
, update
, stmt
);
2909 FOR_EACH_VEC_ELT (gimple
, update
, i
, stmt
)
2912 VEC_free (gimple
, heap
, update
);
2914 gsi
= gsi_for_phi_node (phi
);
2915 remove_phi_node (&gsi
, false);
2918 /* Helper function for for_each_index. For each INDEX of the data
2919 reference REF, returns true when its indices are valid in the loop
2920 nest LOOP passed in as DATA. */
2923 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2926 basic_block header
, def_bb
;
2929 if (TREE_CODE (*index
) != SSA_NAME
)
2932 loop
= *((loop_p
*) data
);
2933 header
= loop
->header
;
2934 stmt
= SSA_NAME_DEF_STMT (*index
);
2939 def_bb
= gimple_bb (stmt
);
2944 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2947 /* When the result of a CLOSE_PHI is written to a memory location,
2948 return a pointer to that memory reference, otherwise return
2952 close_phi_written_to_memory (gimple close_phi
)
2954 imm_use_iterator imm_iter
;
2955 use_operand_p use_p
;
2957 tree res
, def
= gimple_phi_result (close_phi
);
2959 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2960 if ((stmt
= USE_STMT (use_p
))
2961 && gimple_code (stmt
) == GIMPLE_ASSIGN
2962 && (res
= gimple_assign_lhs (stmt
)))
2964 switch (TREE_CODE (res
))
2974 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2975 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2977 /* FIXME: this restriction is for id-{24,25}.f and
2978 could be handled by duplicating the computation of
2979 array indices before the loop of the close_phi. */
2980 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2992 /* Rewrite out of SSA the reduction described by the loop phi nodes
2993 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2996 IN: stmt, loop_n, ..., loop_0
2997 OUT: stmt, close_n, ..., close_0
2999 the first element is the reduction statement, and the next elements
3000 are the loop and close phi nodes of each of the outer loops. */
3003 translate_scalar_reduction_to_array (scop_p scop
,
3004 VEC (gimple
, heap
) *in
,
3005 VEC (gimple
, heap
) *out
)
3008 unsigned int i
= VEC_length (gimple
, out
) - 1;
3009 tree red
= close_phi_written_to_memory (VEC_index (gimple
, out
, i
));
3011 FOR_EACH_VEC_ELT (gimple
, in
, i
, loop_phi
)
3013 gimple close_phi
= VEC_index (gimple
, out
, i
);
3017 gimple stmt
= loop_phi
;
3018 basic_block bb
= split_reduction_stmt (scop
, stmt
);
3019 poly_bb_p pbb
= pbb_from_bb (bb
);
3020 PBB_IS_REDUCTION (pbb
) = true;
3021 gcc_assert (close_phi
== loop_phi
);
3024 red
= create_zero_dim_array
3025 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3027 translate_scalar_reduction_to_array_for_stmt
3028 (scop
, red
, stmt
, VEC_index (gimple
, in
, 1));
3032 if (i
== VEC_length (gimple
, in
) - 1)
3034 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3035 unshare_expr (red
), close_phi
);
3036 insert_out_of_ssa_copy_on_edge
3037 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3038 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3041 remove_phi (loop_phi
);
3042 remove_phi (close_phi
);
3046 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3047 true when something has been changed. */
3050 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3054 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
3055 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
3057 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3058 res
= VEC_length (gimple
, in
) > 1;
3060 translate_scalar_reduction_to_array (scop
, in
, out
);
3062 VEC_free (gimple
, heap
, in
);
3063 VEC_free (gimple
, heap
, out
);
3067 /* Rewrites all the commutative reductions from LOOP out of SSA.
3068 Returns true when something has been changed. */
3071 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3074 gimple_stmt_iterator gsi
;
3075 edge exit
= single_exit (loop
);
3077 bool changed
= false;
3082 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3083 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3084 && is_gimple_reg (res
)
3085 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3086 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3087 (scop
, gsi_stmt (gsi
));
3092 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3095 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3099 bool changed
= false;
3100 sese region
= SCOP_REGION (scop
);
3102 FOR_EACH_LOOP (li
, loop
, 0)
3103 if (loop_in_sese_p (loop
, region
))
3104 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3109 gsi_commit_edge_inserts ();
3110 update_ssa (TODO_update_ssa
);
3111 #ifdef ENABLE_CHECKING
3112 verify_loop_closed_ssa (true);
3117 /* Can all ivs be represented by a signed integer?
3118 As CLooG might generate negative values in its expressions, signed loop ivs
3119 are required in the backend. */
3122 scop_ivs_can_be_represented (scop_p scop
)
3126 gimple_stmt_iterator psi
;
3128 FOR_EACH_LOOP (li
, loop
, 0)
3130 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3133 for (psi
= gsi_start_phis (loop
->header
);
3134 !gsi_end_p (psi
); gsi_next (&psi
))
3136 gimple phi
= gsi_stmt (psi
);
3137 tree res
= PHI_RESULT (phi
);
3138 tree type
= TREE_TYPE (res
);
3140 if (TYPE_UNSIGNED (type
)
3141 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3149 /* Builds the polyhedral representation for a SESE region. */
3152 build_poly_scop (scop_p scop
)
3154 sese region
= SCOP_REGION (scop
);
3155 graphite_dim_t max_dim
;
3157 build_scop_bbs (scop
);
3159 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3160 Once CLooG is fixed, remove this guard. Anyways, it makes no
3161 sense to optimize a scop containing only PBBs that do not belong
3163 if (nb_pbbs_in_loops (scop
) == 0)
3166 if (!scop_ivs_can_be_represented (scop
))
3169 if (flag_associative_math
)
3170 rewrite_commutative_reductions_out_of_ssa (scop
);
3172 build_sese_loop_nests (region
);
3173 build_sese_conditions (region
);
3174 find_scop_parameters (scop
);
3176 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3177 if (scop_nb_params (scop
) > max_dim
)
3180 build_scop_iteration_domain (scop
);
3181 build_scop_context (scop
);
3182 add_conditions_to_constraints (scop
);
3184 /* Rewrite out of SSA only after having translated the
3185 representation to the polyhedral representation to avoid scev
3186 analysis failures. That means that these functions will insert
3187 new data references that they create in the right place. */
3188 rewrite_reductions_out_of_ssa (scop
);
3189 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3191 build_scop_drs (scop
);
3193 build_scop_scattering (scop
);
3195 /* This SCoP has been translated to the polyhedral
3197 POLY_SCOP_P (scop
) = true;