1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
46 /* Print to stderr the element ELT. */
49 debug_rename_elt (rename_map_elt elt
)
51 fprintf (stderr
, "(");
52 print_generic_expr (stderr
, elt
->old_name
, 0);
53 fprintf (stderr
, ", ");
54 print_generic_expr (stderr
, elt
->expr
, 0);
55 fprintf (stderr
, ")\n");
58 /* Helper function for debug_rename_map. */
61 debug_rename_map_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
63 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
64 debug_rename_elt (entry
);
68 /* Print to stderr all the elements of MAP. */
71 debug_rename_map (htab_t map
)
73 htab_traverse (map
, debug_rename_map_1
, NULL
);
76 /* Computes a hash function for database element ELT. */
79 rename_map_elt_info (const void *elt
)
81 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
84 /* Compares database elements E1 and E2. */
87 eq_rename_map_elts (const void *e1
, const void *e2
)
89 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
90 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
92 return (elt1
->old_name
== elt2
->old_name
);
97 /* Print to stderr the element ELT. */
100 debug_ivtype_elt (ivtype_map_elt elt
)
102 fprintf (stderr
, "(%s, ", elt
->cloog_iv
);
103 print_generic_expr (stderr
, elt
->type
, 0);
104 fprintf (stderr
, ")\n");
107 /* Helper function for debug_ivtype_map. */
110 debug_ivtype_map_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
112 struct ivtype_map_elt_s
*entry
= (struct ivtype_map_elt_s
*) *slot
;
113 debug_ivtype_elt (entry
);
117 /* Print to stderr all the elements of MAP. */
120 debug_ivtype_map (htab_t map
)
122 htab_traverse (map
, debug_ivtype_map_1
, NULL
);
125 /* Computes a hash function for database element ELT. */
128 ivtype_map_elt_info (const void *elt
)
130 return htab_hash_pointer (((const struct ivtype_map_elt_s
*) elt
)->cloog_iv
);
133 /* Compares database elements E1 and E2. */
136 eq_ivtype_map_elts (const void *e1
, const void *e2
)
138 const struct ivtype_map_elt_s
*elt1
= (const struct ivtype_map_elt_s
*) e1
;
139 const struct ivtype_map_elt_s
*elt2
= (const struct ivtype_map_elt_s
*) e2
;
141 return (elt1
->cloog_iv
== elt2
->cloog_iv
);
146 /* Record LOOP as occuring in REGION. */
149 sese_record_loop (sese region
, loop_p loop
)
151 if (sese_contains_loop (region
, loop
))
154 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
155 VEC_safe_push (loop_p
, heap
, SESE_LOOP_NEST (region
), loop
);
158 /* Build the loop nests contained in REGION. Returns true when the
159 operation was successful. */
162 build_sese_loop_nests (sese region
)
166 struct loop
*loop0
, *loop1
;
169 if (bb_in_sese_p (bb
, region
))
171 struct loop
*loop
= bb
->loop_father
;
173 /* Only add loops if they are completely contained in the SCoP. */
174 if (loop
->header
== bb
175 && bb_in_sese_p (loop
->latch
, region
))
176 sese_record_loop (region
, loop
);
179 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
180 can be the case that an inner loop is inserted before an outer
181 loop. To avoid this, semi-sort once. */
182 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop0
); i
++)
184 if (VEC_length (loop_p
, SESE_LOOP_NEST (region
)) == i
+ 1)
187 loop1
= VEC_index (loop_p
, SESE_LOOP_NEST (region
), i
+ 1);
188 if (loop0
->num
> loop1
->num
)
190 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
, loop1
);
191 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
+ 1, loop0
);
196 /* For a USE in BB, if BB is outside REGION, mark the USE in the
200 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
206 if (TREE_CODE (use
) != SSA_NAME
)
209 ver
= SSA_NAME_VERSION (use
);
210 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
213 || !bb_in_sese_p (def_bb
, region
)
214 || bb_in_sese_p (bb
, region
))
217 bitmap_set_bit (liveouts
, ver
);
220 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
221 used in BB that is outside of the REGION. */
224 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
226 gimple_stmt_iterator bsi
;
232 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
233 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
234 sese_build_liveouts_use (region
, liveouts
, bb
,
235 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
237 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
239 gimple stmt
= gsi_stmt (bsi
);
241 if (is_gimple_debug (stmt
))
244 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
245 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
249 /* For a USE in BB, return true if BB is outside REGION and it's not
250 in the LIVEOUTS set. */
253 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
259 if (TREE_CODE (use
) != SSA_NAME
)
262 ver
= SSA_NAME_VERSION (use
);
264 /* If it's in liveouts, the variable will get a new PHI node, and
265 the debug use will be properly adjusted. */
266 if (bitmap_bit_p (liveouts
, ver
))
269 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
272 || !bb_in_sese_p (def_bb
, region
)
273 || bb_in_sese_p (bb
, region
))
279 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
280 are not marked as liveouts. */
283 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
285 gimple_stmt_iterator bsi
;
289 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
291 gimple stmt
= gsi_stmt (bsi
);
293 if (!is_gimple_debug (stmt
))
296 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
297 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
298 USE_FROM_PTR (use_p
)))
300 gimple_debug_bind_reset_value (stmt
);
307 /* Build the LIVEOUTS of REGION: the set of variables defined inside
308 and used outside the REGION. */
311 sese_build_liveouts (sese region
, bitmap liveouts
)
316 sese_build_liveouts_bb (region
, liveouts
, bb
);
317 if (MAY_HAVE_DEBUG_INSNS
)
319 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
322 /* Builds a new SESE region from edges ENTRY and EXIT. */
325 new_sese (edge entry
, edge exit
)
327 sese region
= XNEW (struct sese_s
);
329 SESE_ENTRY (region
) = entry
;
330 SESE_EXIT (region
) = exit
;
331 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
332 SESE_LOOP_NEST (region
) = VEC_alloc (loop_p
, heap
, 3);
333 SESE_ADD_PARAMS (region
) = true;
334 SESE_PARAMS (region
) = VEC_alloc (tree
, heap
, 3);
339 /* Deletes REGION. */
342 free_sese (sese region
)
344 if (SESE_LOOPS (region
))
345 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
347 VEC_free (tree
, heap
, SESE_PARAMS (region
));
348 VEC_free (loop_p
, heap
, SESE_LOOP_NEST (region
));
353 /* Add exit phis for USE on EXIT. */
356 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
358 gimple phi
= create_phi_node (use
, exit
);
360 create_new_def_for (gimple_phi_result (phi
), phi
,
361 gimple_phi_result_ptr (phi
));
362 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
363 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
366 /* Insert in the block BB phi nodes for variables defined in REGION
367 and used outside the REGION. The code generation moves REGION in
368 the else clause of an "if (1)" and generates code in the then
369 clause that is at this point empty:
378 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
379 edge false_e
, edge true_e
)
383 bitmap liveouts
= BITMAP_ALLOC (NULL
);
385 update_ssa (TODO_update_ssa
);
387 sese_build_liveouts (region
, liveouts
);
388 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
389 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
390 BITMAP_FREE (liveouts
);
392 update_ssa (TODO_update_ssa
);
395 /* Get the definition of NAME before the SESE. Keep track of the
396 basic blocks that have been VISITED in a bitmap. */
399 get_vdef_before_sese (sese region
, tree name
, sbitmap visited
)
402 gimple stmt
= SSA_NAME_DEF_STMT (name
);
403 basic_block def_bb
= gimple_bb (stmt
);
405 if (!def_bb
|| !bb_in_sese_p (def_bb
, region
))
408 if (TEST_BIT (visited
, def_bb
->index
))
411 SET_BIT (visited
, def_bb
->index
);
413 switch (gimple_code (stmt
))
416 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
418 tree arg
= gimple_phi_arg_def (stmt
, i
);
421 if (gimple_bb (SSA_NAME_DEF_STMT (arg
))
422 && def_bb
->index
== gimple_bb (SSA_NAME_DEF_STMT (arg
))->index
)
425 res
= get_vdef_before_sese (region
, arg
, visited
);
434 use_operand_p use_p
= gimple_vuse_op (stmt
);
435 tree use
= USE_FROM_PTR (use_p
);
437 if (def_bb
->index
== gimple_bb (SSA_NAME_DEF_STMT (use
))->index
)
438 RESET_BIT (visited
, def_bb
->index
);
440 return get_vdef_before_sese (region
, use
, visited
);
448 /* Adjust a virtual phi node PHI that is placed at the end of the
449 generated code for SCOP:
452 | generated code from REGION;
456 The FALSE_E edge comes from the original code, TRUE_E edge comes
457 from the code generated for the SCOP. */
460 sese_adjust_vphi (sese region
, gimple phi
, edge true_e
)
464 gcc_assert (gimple_phi_num_args (phi
) == 2);
466 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
467 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
469 tree true_arg
, false_arg
, before_scop_arg
;
472 true_arg
= gimple_phi_arg_def (phi
, i
);
473 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg
))
476 false_arg
= gimple_phi_arg_def (phi
, i
== 0 ? 1 : 0);
477 if (SSA_NAME_IS_DEFAULT_DEF (false_arg
))
480 visited
= sbitmap_alloc (last_basic_block
);
481 sbitmap_zero (visited
);
482 before_scop_arg
= get_vdef_before_sese (region
, false_arg
, visited
);
483 gcc_assert (before_scop_arg
!= NULL_TREE
);
484 SET_PHI_ARG_DEF (phi
, i
, before_scop_arg
);
485 sbitmap_free (visited
);
489 /* Returns the expression associated to OLD_NAME in MAP. */
492 get_rename (htab_t map
, tree old_name
)
494 struct rename_map_elt_s tmp
;
497 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
498 tmp
.old_name
= old_name
;
499 slot
= htab_find_slot (map
, &tmp
, NO_INSERT
);
502 return ((rename_map_elt
) *slot
)->expr
;
507 /* Register in MAP the rename tuple (OLD_NAME, EXPR). */
510 set_rename (htab_t map
, tree old_name
, tree expr
)
512 struct rename_map_elt_s tmp
;
515 if (old_name
== expr
)
518 tmp
.old_name
= old_name
;
519 slot
= htab_find_slot (map
, &tmp
, INSERT
);
527 *slot
= new_rename_map_elt (old_name
, expr
);
530 /* Renames the expression T following the tuples (OLD_NAME, EXPR) in
531 the rename map M. Returns the expression T after renaming. */
534 rename_variables_in_expr (htab_t m
, tree t
)
539 if (TREE_CODE (t
) == SSA_NAME
)
540 return get_rename (m
, t
);
542 switch (TREE_CODE_LENGTH (TREE_CODE (t
)))
545 TREE_OPERAND (t
, 2) = rename_variables_in_expr (m
, TREE_OPERAND (t
, 2));
548 TREE_OPERAND (t
, 1) = rename_variables_in_expr (m
, TREE_OPERAND (t
, 1));
551 TREE_OPERAND (t
, 0) = rename_variables_in_expr (m
, TREE_OPERAND (t
, 0));
558 /* Renames all the loop->nb_iterations expressions following the
559 tuples (OLD_NAME, EXPR) in RENAME_MAP. */
562 rename_nb_iterations (htab_t rename_map
)
567 FOR_EACH_LOOP (li
, loop
, 0)
568 loop
->nb_iterations
= rename_variables_in_expr (rename_map
,
569 loop
->nb_iterations
);
572 /* Renames all the parameters of SESE following the tuples (OLD_NAME,
573 EXPR) in RENAME_MAP. */
576 rename_sese_parameters (htab_t rename_map
, sese region
)
581 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
582 VEC_replace (tree
, SESE_PARAMS (region
), i
,
583 rename_variables_in_expr (rename_map
, p
));
586 /* Adjusts the phi nodes in the block BB for variables defined in
587 SCOP_REGION and used outside the SCOP_REGION. The code generation
588 moves SCOP_REGION in the else clause of an "if (1)" and generates
589 code in the then clause:
592 | generated code from REGION;
596 To adjust the phi nodes after the condition, the RENAME_MAP is
600 sese_adjust_liveout_phis (sese region
, htab_t rename_map
, basic_block bb
,
601 edge false_e
, edge true_e
)
603 gimple_stmt_iterator si
;
605 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
608 unsigned false_i
= 0;
609 gimple phi
= gsi_stmt (si
);
610 tree res
= gimple_phi_result (phi
);
612 if (!is_gimple_reg (res
))
614 sese_adjust_vphi (region
, phi
, true_e
);
618 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
619 if (gimple_phi_arg_edge (phi
, i
) == false_e
)
625 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
626 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
628 tree old_name
= gimple_phi_arg_def (phi
, false_i
);
629 tree expr
= get_rename (rename_map
, old_name
);
632 gcc_assert (old_name
!= expr
);
634 if (TREE_CODE (expr
) != SSA_NAME
635 && is_gimple_reg (old_name
))
637 tree type
= TREE_TYPE (old_name
);
638 tree var
= create_tmp_var (type
, "var");
640 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
641 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
642 gsi_insert_seq_on_edge_immediate (true_e
, stmts
);
645 SET_PHI_ARG_DEF (phi
, i
, expr
);
646 set_rename (rename_map
, old_name
, res
);
651 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
654 rename_variables_in_stmt (gimple stmt
, htab_t map
, gimple_stmt_iterator
*insert_gsi
)
659 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
661 tree use
= USE_FROM_PTR (use_p
);
662 tree expr
, type_use
, type_expr
;
665 if (TREE_CODE (use
) != SSA_NAME
)
668 expr
= get_rename (map
, use
);
672 type_use
= TREE_TYPE (use
);
673 type_expr
= TREE_TYPE (expr
);
675 if (type_use
!= type_expr
676 || (TREE_CODE (expr
) != SSA_NAME
677 && is_gimple_reg (use
)))
681 if (is_gimple_debug (stmt
))
683 if (gimple_debug_bind_p (stmt
))
684 gimple_debug_bind_reset_value (stmt
);
691 var
= create_tmp_var (type_use
, "var");
693 if (type_use
!= type_expr
)
694 expr
= fold_convert (type_use
, expr
);
696 expr
= build2 (MODIFY_EXPR
, type_use
, var
, expr
);
697 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
698 gsi_insert_seq_before (insert_gsi
, stmts
, GSI_SAME_STMT
);
701 replace_exp (use_p
, expr
);
707 /* Returns true if NAME is a parameter of SESE. */
710 is_parameter (sese region
, tree name
)
715 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
722 /* Returns true if NAME is an induction variable. */
727 return gimple_code (SSA_NAME_DEF_STMT (name
)) == GIMPLE_PHI
;
730 static void expand_scalar_variables_stmt (gimple
, basic_block
, sese
,
731 htab_t
, gimple_stmt_iterator
*);
733 expand_scalar_variables_expr (tree
, tree
, enum tree_code
, tree
, basic_block
,
734 sese
, htab_t
, gimple_stmt_iterator
*);
737 expand_scalar_variables_call (gimple stmt
, basic_block bb
, sese region
,
738 htab_t map
, gimple_stmt_iterator
*gsi
)
740 int i
, nargs
= gimple_call_num_args (stmt
);
741 VEC (tree
, gc
) *args
= VEC_alloc (tree
, gc
, nargs
);
742 tree fn_type
= TREE_TYPE (gimple_call_fn (stmt
));
743 tree fn
= gimple_call_fndecl (stmt
);
744 tree call_expr
, var
, lhs
;
747 for (i
= 0; i
< nargs
; i
++)
749 tree arg
= gimple_call_arg (stmt
, i
);
750 tree t
= TREE_TYPE (arg
);
752 var
= create_tmp_var (t
, "var");
753 arg
= expand_scalar_variables_expr (t
, arg
, TREE_CODE (arg
), NULL
,
754 bb
, region
, map
, gsi
);
755 arg
= build2 (MODIFY_EXPR
, t
, var
, arg
);
756 arg
= force_gimple_operand_gsi (gsi
, arg
, true, NULL
,
757 true, GSI_SAME_STMT
);
758 VEC_quick_push (tree
, args
, arg
);
761 lhs
= gimple_call_lhs (stmt
);
762 var
= create_tmp_var (TREE_TYPE (lhs
), "var");
763 call_expr
= build_call_vec (fn_type
, fn
, args
);
764 call
= gimple_build_call_from_tree (call_expr
);
765 var
= make_ssa_name (var
, call
);
766 gimple_call_set_lhs (call
, var
);
767 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
772 /* Copies at GSI all the scalar computations on which the ssa_name OP0
773 depends on in the SESE: these are all the scalar variables used in
774 the definition of OP0, that are defined outside BB and still in the
775 SESE, i.e. not a parameter of the SESE. The expression that is
776 returned contains only induction variables from the generated code:
777 MAP contains the induction variables renaming mapping, and is used
778 to translate the names of induction variables. */
781 expand_scalar_variables_ssa_name (tree type
, tree op0
, basic_block bb
,
782 sese region
, htab_t map
,
783 gimple_stmt_iterator
*gsi
)
788 if (is_parameter (region
, op0
)
790 return fold_convert (type
, get_rename (map
, op0
));
792 def_stmt
= SSA_NAME_DEF_STMT (op0
);
794 /* Check whether we already have a rename for OP0. */
795 new_op
= get_rename (map
, op0
);
798 && gimple_bb (SSA_NAME_DEF_STMT (new_op
)) == bb
)
799 return fold_convert (type
, new_op
);
801 if (gimple_bb (def_stmt
) == bb
)
803 /* If the defining statement is in the basic block already
804 we do not need to create a new expression for it, we
805 only need to ensure its operands are expanded. */
806 expand_scalar_variables_stmt (def_stmt
, bb
, region
, map
, gsi
);
807 return fold_convert (type
, new_op
);
811 if (!gimple_bb (def_stmt
)
812 || !bb_in_sese_p (gimple_bb (def_stmt
), region
))
813 return fold_convert (type
, new_op
);
815 switch (gimple_code (def_stmt
))
819 tree var0
= gimple_assign_rhs1 (def_stmt
);
820 enum tree_code subcode
= gimple_assign_rhs_code (def_stmt
);
821 tree var1
= gimple_assign_rhs2 (def_stmt
);
822 tree type
= gimple_expr_type (def_stmt
);
824 return expand_scalar_variables_expr (type
, var0
, subcode
, var1
, bb
,
829 return expand_scalar_variables_call (def_stmt
, bb
, region
, map
, gsi
);
838 /* Copies at GSI all the scalar computations on which the expression
839 OP0 CODE OP1 depends on in the SESE: these are all the scalar
840 variables used in OP0 and OP1, defined outside BB and still defined
841 in the SESE, i.e. not a parameter of the SESE. The expression that
842 is returned contains only induction variables from the generated
843 code: MAP contains the induction variables renaming mapping, and is
844 used to translate the names of induction variables. */
847 expand_scalar_variables_expr (tree type
, tree op0
, enum tree_code code
,
848 tree op1
, basic_block bb
, sese region
,
849 htab_t map
, gimple_stmt_iterator
*gsi
)
851 if (TREE_CODE_CLASS (code
) == tcc_constant
852 || TREE_CODE_CLASS (code
) == tcc_declaration
)
855 /* For data references we have to duplicate also its memory
857 if (TREE_CODE_CLASS (code
) == tcc_reference
)
864 tree op
= TREE_OPERAND (op0
, 0);
865 tree res
= expand_scalar_variables_expr
866 (type
, op
, TREE_CODE (op
), NULL
, bb
, region
, map
, gsi
);
867 return build1 (code
, type
, res
);
872 tree old_name
= TREE_OPERAND (op0
, 0);
873 tree expr
= expand_scalar_variables_ssa_name
874 (type
, old_name
, bb
, region
, map
, gsi
);
876 if (TREE_CODE (expr
) != SSA_NAME
877 && is_gimple_reg (old_name
))
879 tree type
= TREE_TYPE (old_name
);
880 tree var
= create_tmp_var (type
, "var");
882 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
883 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL
,
884 true, GSI_SAME_STMT
);
887 return fold_build1 (code
, type
, expr
);
892 tree op00
= TREE_OPERAND (op0
, 0);
893 tree op01
= TREE_OPERAND (op0
, 1);
894 tree op02
= TREE_OPERAND (op0
, 2);
895 tree op03
= TREE_OPERAND (op0
, 3);
896 tree base
= expand_scalar_variables_expr
897 (TREE_TYPE (op00
), op00
, TREE_CODE (op00
), NULL
, bb
, region
,
899 tree subscript
= expand_scalar_variables_expr
900 (TREE_TYPE (op01
), op01
, TREE_CODE (op01
), NULL
, bb
, region
,
903 return build4 (ARRAY_REF
, type
, base
, subscript
, op02
, op03
);
910 /* The above cases should catch everything. */
915 if (TREE_CODE_CLASS (code
) == tcc_unary
)
917 tree op0_type
= TREE_TYPE (op0
);
918 enum tree_code op0_code
= TREE_CODE (op0
);
919 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
920 NULL
, bb
, region
, map
, gsi
);
922 return fold_build1 (code
, type
, op0_expr
);
925 if (TREE_CODE_CLASS (code
) == tcc_binary
926 || TREE_CODE_CLASS (code
) == tcc_comparison
)
928 tree op0_type
= TREE_TYPE (op0
);
929 enum tree_code op0_code
= TREE_CODE (op0
);
930 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
931 NULL
, bb
, region
, map
, gsi
);
932 tree op1_type
= TREE_TYPE (op1
);
933 enum tree_code op1_code
= TREE_CODE (op1
);
934 tree op1_expr
= expand_scalar_variables_expr (op1_type
, op1
, op1_code
,
935 NULL
, bb
, region
, map
, gsi
);
937 return fold_build2 (code
, type
, op0_expr
, op1_expr
);
940 if (code
== SSA_NAME
)
941 return expand_scalar_variables_ssa_name (type
, op0
, bb
, region
, map
, gsi
);
943 if (code
== ADDR_EXPR
)
945 tree op00
= TREE_OPERAND (op0
, 0);
947 if (handled_component_p (op00
)
948 && TREE_CODE (op00
) == ARRAY_REF
)
950 tree e
= expand_scalar_variables_expr (TREE_TYPE (op00
), op00
,
952 NULL
, bb
, region
, map
, gsi
);
953 return fold_build1 (code
, TREE_TYPE (op0
), e
);
963 /* Copies at the beginning of BB all the scalar computations on which
964 STMT depends on in the SESE: these are all the scalar variables used
965 in STMT, defined outside BB and still defined in the SESE, i.e. not a
966 parameter of the SESE. The expression that is returned contains
967 only induction variables from the generated code: MAP contains the
968 induction variables renaming mapping, and is used to translate the
969 names of induction variables. */
972 expand_scalar_variables_stmt (gimple stmt
, basic_block bb
, sese region
,
973 htab_t map
, gimple_stmt_iterator
*gsi
)
978 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
980 tree use
= USE_FROM_PTR (use_p
);
981 tree type
= TREE_TYPE (use
);
982 enum tree_code code
= TREE_CODE (use
);
985 if (!is_gimple_reg (use
))
988 /* Don't expand USE if we already have a rename for it. */
989 use_expr
= get_rename (map
, use
);
993 use_expr
= expand_scalar_variables_expr (type
, use
, code
, NULL
, bb
,
995 use_expr
= fold_convert (type
, use_expr
);
1000 if (is_gimple_debug (stmt
))
1002 if (gimple_debug_bind_p (stmt
))
1003 gimple_debug_bind_reset_value (stmt
);
1010 if (TREE_CODE (use_expr
) != SSA_NAME
)
1012 tree var
= create_tmp_var (type
, "var");
1014 use_expr
= build2 (MODIFY_EXPR
, type
, var
, use_expr
);
1015 use_expr
= force_gimple_operand_gsi (gsi
, use_expr
, true, NULL
,
1016 true, GSI_SAME_STMT
);
1019 replace_exp (use_p
, use_expr
);
1025 /* Copies at the beginning of BB all the scalar computations on which
1026 BB depends on in the SESE: these are all the scalar variables used
1027 in BB, defined outside BB and still defined in the SESE, i.e. not a
1028 parameter of the SESE. The expression that is returned contains
1029 only induction variables from the generated code: MAP contains the
1030 induction variables renaming mapping, and is used to translate the
1031 names of induction variables. */
1034 expand_scalar_variables (basic_block bb
, sese region
, htab_t map
)
1036 gimple_stmt_iterator gsi
;
1038 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
1040 gimple stmt
= gsi_stmt (gsi
);
1041 expand_scalar_variables_stmt (stmt
, bb
, region
, map
, &gsi
);
1046 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
1049 rename_variables (basic_block bb
, htab_t map
)
1051 gimple_stmt_iterator gsi
;
1052 gimple_stmt_iterator insert_gsi
= gsi_start_bb (bb
);
1054 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1055 rename_variables_in_stmt (gsi_stmt (gsi
), map
, &insert_gsi
);
1058 /* Remove condition from BB. */
1061 remove_condition (basic_block bb
)
1063 gimple last
= last_stmt (bb
);
1065 if (last
&& gimple_code (last
) == GIMPLE_COND
)
1067 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1068 gsi_remove (&gsi
, true);
1072 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
1075 get_true_edge_from_guard_bb (basic_block bb
)
1080 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1081 if (e
->flags
& EDGE_TRUE_VALUE
)
1088 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
1091 get_false_edge_from_guard_bb (basic_block bb
)
1096 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1097 if (!(e
->flags
& EDGE_TRUE_VALUE
))
1104 /* Returns true when NAME is defined in LOOP. */
1107 name_defined_in_loop_p (tree name
, loop_p loop
)
1109 return !SSA_NAME_IS_DEFAULT_DEF (name
)
1110 && gimple_bb (SSA_NAME_DEF_STMT (name
))->loop_father
== loop
;
1113 /* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */
1116 expr_defined_in_loop_p (tree expr
, loop_p loop
)
1118 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
1121 return expr_defined_in_loop_p (TREE_OPERAND (expr
, 0), loop
)
1122 || expr_defined_in_loop_p (TREE_OPERAND (expr
, 1), loop
)
1123 || expr_defined_in_loop_p (TREE_OPERAND (expr
, 2), loop
);
1126 return expr_defined_in_loop_p (TREE_OPERAND (expr
, 0), loop
)
1127 || expr_defined_in_loop_p (TREE_OPERAND (expr
, 1), loop
);
1130 return expr_defined_in_loop_p (TREE_OPERAND (expr
, 0), loop
);
1133 return TREE_CODE (expr
) == SSA_NAME
1134 && name_defined_in_loop_p (expr
, loop
);
1141 /* Returns the gimple statement that uses NAME outside the loop it is
1142 defined in, returns NULL if there is no such loop close phi node.
1143 An invariant of the loop closed SSA form is that the only use of a
1144 variable, outside the loop it is defined in, is in the loop close
1145 phi node that just follows the loop. */
1148 alive_after_loop (tree name
)
1150 use_operand_p use_p
;
1151 imm_use_iterator imm_iter
;
1152 loop_p loop
= gimple_bb (SSA_NAME_DEF_STMT (name
))->loop_father
;
1154 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
1156 gimple stmt
= USE_STMT (use_p
);
1158 if (gimple_code (stmt
) == GIMPLE_PHI
1159 && gimple_bb (stmt
)->loop_father
!= loop
)
1166 /* Return true if a close phi has not yet been inserted for the use of
1167 variable NAME on the single exit of LOOP. */
1170 close_phi_not_yet_inserted_p (loop_p loop
, tree name
)
1172 gimple_stmt_iterator psi
;
1173 basic_block bb
= single_exit (loop
)->dest
;
1175 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1176 if (gimple_phi_arg_def (gsi_stmt (psi
), 0) == name
)
1182 /* A structure for passing parameters to add_loop_exit_phis. */
1184 typedef struct alep
{
1186 VEC (rename_map_elt
, heap
) *new_renames
;
1189 /* Helper function for htab_traverse in insert_loop_close_phis. */
1192 add_loop_exit_phis (void **slot
, void *data
)
1194 struct rename_map_elt_s
*entry
;
1197 tree expr
, new_name
, old_name
;
1198 bool def_in_loop_p
, used_outside_p
, need_close_phi_p
;
1199 gimple old_close_phi
;
1201 if (!slot
|| !*slot
|| !data
)
1204 entry
= (struct rename_map_elt_s
*) *slot
;
1207 new_name
= expr
= entry
->expr
;
1208 old_name
= entry
->old_name
;
1210 def_in_loop_p
= expr_defined_in_loop_p (expr
, loop
);
1214 /* Remove the old rename from the map when the expression is defined
1215 in the loop that we're closing. */
1219 if (TREE_CODE (expr
) != SSA_NAME
)
1222 old_close_phi
= alive_after_loop (old_name
);
1223 used_outside_p
= (old_close_phi
!= NULL
);
1224 need_close_phi_p
= (used_outside_p
1225 && close_phi_not_yet_inserted_p (loop
, new_name
));
1227 /* Insert a loop close phi node. */
1228 if (need_close_phi_p
)
1230 basic_block bb
= single_exit (loop
)->dest
;
1231 gimple phi
= create_phi_node (new_name
, bb
);
1232 tree new_res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1233 gimple_phi_result_ptr (phi
));
1235 add_phi_arg (phi
, new_name
, single_pred_edge (bb
), UNKNOWN_LOCATION
);
1236 VEC_safe_push (rename_map_elt
, heap
, a
->new_renames
,
1237 new_rename_map_elt (gimple_phi_result (old_close_phi
),
1244 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1245 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1246 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1247 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1250 insert_loop_close_phis (htab_t map
, loop_p loop
)
1257 a
.new_renames
= VEC_alloc (rename_map_elt
, heap
, 3);
1258 update_ssa (TODO_update_ssa
);
1259 htab_traverse (map
, add_loop_exit_phis
, &a
);
1260 update_ssa (TODO_update_ssa
);
1262 for (i
= 0; VEC_iterate (rename_map_elt
, a
.new_renames
, i
, elt
); i
++)
1264 set_rename (map
, elt
->old_name
, elt
->expr
);
1268 VEC_free (rename_map_elt
, heap
, a
.new_renames
);
1271 /* Helper structure for htab_traverse in insert_guard_phis. */
1275 edge true_edge
, false_edge
;
1276 htab_t before_guard
;
1279 /* Return the default name that is before the guard. */
1282 default_before_guard (htab_t before_guard
, tree old_name
)
1284 tree res
= get_rename (before_guard
, old_name
);
1286 if (res
== old_name
)
1288 if (is_gimple_reg (res
))
1289 return fold_convert (TREE_TYPE (res
), integer_zero_node
);
1290 return gimple_default_def (cfun
, SSA_NAME_VAR (res
));
1296 /* Prepares EXPR to be a good phi argument when the phi result is
1297 RES. Insert needed statements on edge E. */
1300 convert_for_phi_arg (tree expr
, tree res
, edge e
)
1302 tree type
= TREE_TYPE (res
);
1304 if (TREE_TYPE (expr
) != type
)
1305 expr
= fold_convert (type
, expr
);
1307 if (TREE_CODE (expr
) != SSA_NAME
1308 && !is_gimple_min_invariant (expr
))
1310 tree var
= create_tmp_var (type
, "var");
1313 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
1314 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
1315 gsi_insert_seq_on_edge_immediate (e
, stmts
);
1321 /* Helper function for htab_traverse in insert_guard_phis. */
1324 add_guard_exit_phis (void **slot
, void *s
)
1326 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
1327 struct igp
*i
= (struct igp
*) s
;
1328 basic_block bb
= i
->bb
;
1329 edge true_edge
= i
->true_edge
;
1330 edge false_edge
= i
->false_edge
;
1331 tree res
= entry
->old_name
;
1332 tree name1
= entry
->expr
;
1333 tree name2
= default_before_guard (i
->before_guard
, res
);
1336 /* Nothing to be merged if the name before the guard is the same as
1341 name1
= convert_for_phi_arg (name1
, res
, true_edge
);
1342 name2
= convert_for_phi_arg (name2
, res
, false_edge
);
1344 phi
= create_phi_node (res
, bb
);
1345 res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1346 gimple_phi_result_ptr (phi
));
1348 add_phi_arg (phi
, name1
, true_edge
, UNKNOWN_LOCATION
);
1349 add_phi_arg (phi
, name2
, false_edge
, UNKNOWN_LOCATION
);
1356 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1357 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1358 with NAME1 different than NAME2, then insert in BB the phi node:
1360 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1362 if there is no tuple for OLD in BEFORE_GUARD, insert
1364 | RES = phi (NAME1 (on TRUE_EDGE),
1365 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1367 Finally register in RENAME_MAP the tuple (OLD, RES). */
1370 insert_guard_phis (basic_block bb
, edge true_edge
, edge false_edge
,
1371 htab_t before_guard
, htab_t rename_map
)
1375 i
.true_edge
= true_edge
;
1376 i
.false_edge
= false_edge
;
1377 i
.before_guard
= before_guard
;
1379 update_ssa (TODO_update_ssa
);
1380 htab_traverse (rename_map
, add_guard_exit_phis
, &i
);
1381 update_ssa (TODO_update_ssa
);
1384 /* Create a duplicate of the basic block BB. NOTE: This does not
1385 preserve SSA form. */
1388 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
, htab_t map
)
1390 gimple_stmt_iterator gsi
, gsi_tgt
;
1392 gsi_tgt
= gsi_start_bb (new_bb
);
1393 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1395 def_operand_p def_p
;
1396 ssa_op_iter op_iter
;
1397 gimple stmt
= gsi_stmt (gsi
);
1400 if (gimple_code (stmt
) == GIMPLE_LABEL
)
1403 /* Create a new copy of STMT and duplicate STMT's virtual
1405 copy
= gimple_copy (stmt
);
1406 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1407 mark_sym_for_renaming (gimple_vop (cfun
));
1409 maybe_duplicate_eh_stmt (copy
, stmt
);
1410 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1412 /* Create new names for all the definitions created by COPY and
1413 add replacement mappings for each new name. */
1414 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1416 tree old_name
= DEF_FROM_PTR (def_p
);
1417 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1418 set_rename (map
, old_name
, new_name
);
1423 /* Copies BB and includes in the copied BB all the statements that can
1424 be reached following the use-def chains from the memory accesses,
1425 and returns the next edge following this new block. */
1428 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
1429 edge next_e
, htab_t map
)
1431 basic_block new_bb
= split_edge (next_e
);
1433 next_e
= single_succ_edge (new_bb
);
1434 graphite_copy_stmts_from_block (bb
, new_bb
, map
);
1435 remove_condition (new_bb
);
1436 remove_phi_nodes (new_bb
);
1437 expand_scalar_variables (new_bb
, region
, map
);
1438 rename_variables (new_bb
, map
);
1443 /* Returns the outermost loop in SCOP that contains BB. */
1446 outermost_loop_in_sese (sese region
, basic_block bb
)
1450 nest
= bb
->loop_father
;
1451 while (loop_outer (nest
)
1452 && loop_in_sese_p (loop_outer (nest
), region
))
1453 nest
= loop_outer (nest
);
1458 /* Sets the false region of an IF_REGION to REGION. */
1461 if_region_set_false_region (ifsese if_region
, sese region
)
1463 basic_block condition
= if_region_get_condition_block (if_region
);
1464 edge false_edge
= get_false_edge_from_guard_bb (condition
);
1465 basic_block dummy
= false_edge
->dest
;
1466 edge entry_region
= SESE_ENTRY (region
);
1467 edge exit_region
= SESE_EXIT (region
);
1468 basic_block before_region
= entry_region
->src
;
1469 basic_block last_in_region
= exit_region
->src
;
1470 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
1471 htab_hash_pointer (exit_region
),
1474 entry_region
->flags
= false_edge
->flags
;
1475 false_edge
->flags
= exit_region
->flags
;
1477 redirect_edge_pred (entry_region
, condition
);
1478 redirect_edge_pred (exit_region
, before_region
);
1479 redirect_edge_pred (false_edge
, last_in_region
);
1480 redirect_edge_succ (false_edge
, single_succ (dummy
));
1481 delete_basic_block (dummy
);
1483 exit_region
->flags
= EDGE_FALLTHRU
;
1484 recompute_all_dominators ();
1486 SESE_EXIT (region
) = false_edge
;
1488 if (if_region
->false_region
)
1489 free (if_region
->false_region
);
1490 if_region
->false_region
= region
;
1494 struct loop_exit
*loop_exit
= GGC_CNEW (struct loop_exit
);
1496 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
1497 htab_clear_slot (current_loops
->exits
, slot
);
1499 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
1500 htab_hash_pointer (false_edge
),
1502 loop_exit
->e
= false_edge
;
1504 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
1508 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1511 create_if_region_on_edge (edge entry
, tree condition
)
1515 sese sese_region
= XNEW (struct sese_s
);
1516 sese true_region
= XNEW (struct sese_s
);
1517 sese false_region
= XNEW (struct sese_s
);
1518 ifsese if_region
= XNEW (struct ifsese_s
);
1519 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
1521 if_region
->region
= sese_region
;
1522 if_region
->region
->entry
= entry
;
1523 if_region
->region
->exit
= exit
;
1525 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
1527 if (e
->flags
& EDGE_TRUE_VALUE
)
1529 true_region
->entry
= e
;
1530 true_region
->exit
= single_succ_edge (e
->dest
);
1531 if_region
->true_region
= true_region
;
1533 else if (e
->flags
& EDGE_FALSE_VALUE
)
1535 false_region
->entry
= e
;
1536 false_region
->exit
= single_succ_edge (e
->dest
);
1537 if_region
->false_region
= false_region
;
1544 /* Moves REGION in a condition expression:
1552 move_sese_in_condition (sese region
)
1554 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
1557 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
1558 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
1559 if_region_set_false_region (if_region
, region
);
1564 /* Replaces the condition of the IF_REGION with CONDITION:
1572 set_ifsese_condition (ifsese if_region
, tree condition
)
1574 sese region
= if_region
->region
;
1575 edge entry
= region
->entry
;
1576 basic_block bb
= entry
->dest
;
1577 gimple last
= last_stmt (bb
);
1578 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1581 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
1583 gsi_remove (&gsi
, true);
1584 gsi
= gsi_last_bb (bb
);
1585 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
1586 false, GSI_NEW_STMT
);
1587 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
1588 gsi
= gsi_last_bb (bb
);
1589 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
1592 /* Returns the scalar evolution of T in REGION. Every variable that
1593 is not defined in the REGION is considered a parameter. */
1596 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
1599 struct loop
*def_loop
;
1600 basic_block before
= block_before_sese (region
);
1602 if (TREE_CODE (t
) != SSA_NAME
1603 || loop_in_sese_p (loop
, region
))
1604 return instantiate_scev (before
, loop
,
1605 analyze_scalar_evolution (loop
, t
));
1607 if (!defined_in_sese_p (t
, region
))
1610 def
= SSA_NAME_DEF_STMT (t
);
1611 def_loop
= loop_containing_stmt (def
);
1613 if (loop_in_sese_p (def_loop
, region
))
1615 t
= analyze_scalar_evolution (def_loop
, t
);
1616 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
1617 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
1621 return instantiate_scev (before
, loop
, t
);