1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
5 Sebastian Pop <sebastian.pop@amd.com>.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-pretty-print.h"
33 #include "tree-flow.h"
35 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
48 /* Print to stderr the element ELT. */
51 debug_rename_elt (rename_map_elt elt
)
53 fprintf (stderr
, "(");
54 print_generic_expr (stderr
, elt
->old_name
, 0);
55 fprintf (stderr
, ", ");
56 print_generic_expr (stderr
, elt
->expr
, 0);
57 fprintf (stderr
, ")\n");
60 /* Helper function for debug_rename_map. */
63 debug_rename_map_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
65 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
66 debug_rename_elt (entry
);
70 /* Print to stderr all the elements of RENAME_MAP. */
73 debug_rename_map (htab_t rename_map
)
75 htab_traverse (rename_map
, debug_rename_map_1
, NULL
);
78 /* Computes a hash function for database element ELT. */
81 rename_map_elt_info (const void *elt
)
83 return SSA_NAME_VERSION (((const struct rename_map_elt_s
*) elt
)->old_name
);
86 /* Compares database elements E1 and E2. */
89 eq_rename_map_elts (const void *e1
, const void *e2
)
91 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
92 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
94 return (elt1
->old_name
== elt2
->old_name
);
99 /* Print to stderr the element ELT. */
102 debug_ivtype_elt (ivtype_map_elt elt
)
104 fprintf (stderr
, "(%s, ", elt
->cloog_iv
);
105 print_generic_expr (stderr
, elt
->type
, 0);
106 fprintf (stderr
, ")\n");
109 /* Helper function for debug_ivtype_map. */
112 debug_ivtype_map_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
114 struct ivtype_map_elt_s
*entry
= (struct ivtype_map_elt_s
*) *slot
;
115 debug_ivtype_elt (entry
);
119 /* Print to stderr all the elements of MAP. */
122 debug_ivtype_map (htab_t map
)
124 htab_traverse (map
, debug_ivtype_map_1
, NULL
);
127 /* Computes a hash function for database element ELT. */
130 ivtype_map_elt_info (const void *elt
)
132 return htab_hash_pointer (((const struct ivtype_map_elt_s
*) elt
)->cloog_iv
);
135 /* Compares database elements E1 and E2. */
138 eq_ivtype_map_elts (const void *e1
, const void *e2
)
140 const struct ivtype_map_elt_s
*elt1
= (const struct ivtype_map_elt_s
*) e1
;
141 const struct ivtype_map_elt_s
*elt2
= (const struct ivtype_map_elt_s
*) e2
;
143 return (elt1
->cloog_iv
== elt2
->cloog_iv
);
148 /* Record LOOP as occuring in REGION. */
151 sese_record_loop (sese region
, loop_p loop
)
153 if (sese_contains_loop (region
, loop
))
156 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
157 VEC_safe_push (loop_p
, heap
, SESE_LOOP_NEST (region
), loop
);
160 /* Build the loop nests contained in REGION. Returns true when the
161 operation was successful. */
164 build_sese_loop_nests (sese region
)
168 struct loop
*loop0
, *loop1
;
171 if (bb_in_sese_p (bb
, region
))
173 struct loop
*loop
= bb
->loop_father
;
175 /* Only add loops if they are completely contained in the SCoP. */
176 if (loop
->header
== bb
177 && bb_in_sese_p (loop
->latch
, region
))
178 sese_record_loop (region
, loop
);
181 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
182 can be the case that an inner loop is inserted before an outer
183 loop. To avoid this, semi-sort once. */
184 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop0
); i
++)
186 if (VEC_length (loop_p
, SESE_LOOP_NEST (region
)) == i
+ 1)
189 loop1
= VEC_index (loop_p
, SESE_LOOP_NEST (region
), i
+ 1);
190 if (loop0
->num
> loop1
->num
)
192 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
, loop1
);
193 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
+ 1, loop0
);
198 /* For a USE in BB, if BB is outside REGION, mark the USE in the
202 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
208 if (TREE_CODE (use
) != SSA_NAME
)
211 ver
= SSA_NAME_VERSION (use
);
212 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
215 || !bb_in_sese_p (def_bb
, region
)
216 || bb_in_sese_p (bb
, region
))
219 bitmap_set_bit (liveouts
, ver
);
222 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
223 used in BB that is outside of the REGION. */
226 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
228 gimple_stmt_iterator bsi
;
234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
235 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
236 sese_build_liveouts_use (region
, liveouts
, bb
,
237 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
239 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
241 gimple stmt
= gsi_stmt (bsi
);
243 if (is_gimple_debug (stmt
))
246 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
247 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
251 /* For a USE in BB, return true if BB is outside REGION and it's not
252 in the LIVEOUTS set. */
255 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
261 if (TREE_CODE (use
) != SSA_NAME
)
264 ver
= SSA_NAME_VERSION (use
);
266 /* If it's in liveouts, the variable will get a new PHI node, and
267 the debug use will be properly adjusted. */
268 if (bitmap_bit_p (liveouts
, ver
))
271 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
274 || !bb_in_sese_p (def_bb
, region
)
275 || bb_in_sese_p (bb
, region
))
281 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
282 are not marked as liveouts. */
285 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
287 gimple_stmt_iterator bsi
;
291 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
293 gimple stmt
= gsi_stmt (bsi
);
295 if (!is_gimple_debug (stmt
))
298 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
299 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
300 USE_FROM_PTR (use_p
)))
302 gimple_debug_bind_reset_value (stmt
);
309 /* Build the LIVEOUTS of REGION: the set of variables defined inside
310 and used outside the REGION. */
313 sese_build_liveouts (sese region
, bitmap liveouts
)
318 sese_build_liveouts_bb (region
, liveouts
, bb
);
319 if (MAY_HAVE_DEBUG_INSNS
)
321 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
324 /* Builds a new SESE region from edges ENTRY and EXIT. */
327 new_sese (edge entry
, edge exit
)
329 sese region
= XNEW (struct sese_s
);
331 SESE_ENTRY (region
) = entry
;
332 SESE_EXIT (region
) = exit
;
333 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
334 SESE_LOOP_NEST (region
) = VEC_alloc (loop_p
, heap
, 3);
335 SESE_ADD_PARAMS (region
) = true;
336 SESE_PARAMS (region
) = VEC_alloc (tree
, heap
, 3);
341 /* Deletes REGION. */
344 free_sese (sese region
)
346 if (SESE_LOOPS (region
))
347 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
349 VEC_free (tree
, heap
, SESE_PARAMS (region
));
350 VEC_free (loop_p
, heap
, SESE_LOOP_NEST (region
));
355 /* Add exit phis for USE on EXIT. */
358 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
360 gimple phi
= create_phi_node (use
, exit
);
362 create_new_def_for (gimple_phi_result (phi
), phi
,
363 gimple_phi_result_ptr (phi
));
364 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
365 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
368 /* Insert in the block BB phi nodes for variables defined in REGION
369 and used outside the REGION. The code generation moves REGION in
370 the else clause of an "if (1)" and generates code in the then
371 clause that is at this point empty:
380 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
381 edge false_e
, edge true_e
)
385 bitmap liveouts
= BITMAP_ALLOC (NULL
);
387 update_ssa (TODO_update_ssa
);
389 sese_build_liveouts (region
, liveouts
);
390 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
391 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
392 BITMAP_FREE (liveouts
);
394 update_ssa (TODO_update_ssa
);
397 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
400 get_rename (htab_t rename_map
, tree old_name
)
402 struct rename_map_elt_s tmp
;
405 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
406 tmp
.old_name
= old_name
;
407 slot
= htab_find_slot (rename_map
, &tmp
, NO_INSERT
);
410 return ((rename_map_elt
) *slot
)->expr
;
415 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
418 set_rename (htab_t rename_map
, tree old_name
, tree expr
)
420 struct rename_map_elt_s tmp
;
423 if (old_name
== expr
)
426 tmp
.old_name
= old_name
;
427 slot
= htab_find_slot (rename_map
, &tmp
, INSERT
);
435 *slot
= new_rename_map_elt (old_name
, expr
);
438 /* Rename the SSA_NAMEs used in STMT and that appear in RENAME_MAP. */
441 rename_variables_in_stmt (gimple stmt
, htab_t rename_map
, gimple_stmt_iterator
*insert_gsi
)
446 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
448 tree use
= USE_FROM_PTR (use_p
);
449 tree expr
, type_use
, type_expr
;
452 if (TREE_CODE (use
) != SSA_NAME
)
455 expr
= get_rename (rename_map
, use
);
459 type_use
= TREE_TYPE (use
);
460 type_expr
= TREE_TYPE (expr
);
462 if (type_use
!= type_expr
463 || (TREE_CODE (expr
) != SSA_NAME
464 && is_gimple_reg (use
)))
468 if (is_gimple_debug (stmt
))
470 if (gimple_debug_bind_p (stmt
))
471 gimple_debug_bind_reset_value (stmt
);
478 var
= create_tmp_var (type_use
, "var");
480 if (type_use
!= type_expr
)
481 expr
= fold_convert (type_use
, expr
);
483 expr
= build2 (MODIFY_EXPR
, type_use
, var
, expr
);
484 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
485 gsi_insert_seq_before (insert_gsi
, stmts
, GSI_SAME_STMT
);
488 replace_exp (use_p
, expr
);
494 /* Returns true if NAME is a parameter of SESE. */
497 is_parameter (sese region
, tree name
)
502 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
509 /* Returns true if NAME is an induction variable. */
514 return gimple_code (SSA_NAME_DEF_STMT (name
)) == GIMPLE_PHI
;
517 static void expand_scalar_variables_stmt (gimple
, basic_block
, sese
,
518 htab_t
, gimple_stmt_iterator
*);
520 expand_scalar_variables_expr (tree
, tree
, enum tree_code
, tree
, basic_block
,
521 sese
, htab_t
, gimple_stmt_iterator
*);
524 expand_scalar_variables_call (gimple stmt
, basic_block bb
, sese region
,
525 htab_t rename_map
, gimple_stmt_iterator
*gsi
)
527 int i
, nargs
= gimple_call_num_args (stmt
);
528 VEC (tree
, gc
) *args
= VEC_alloc (tree
, gc
, nargs
);
529 tree fn_type
= TREE_TYPE (gimple_call_fn (stmt
));
530 tree fn
= gimple_call_fndecl (stmt
);
531 tree call_expr
, var
, lhs
;
534 for (i
= 0; i
< nargs
; i
++)
536 tree arg
= gimple_call_arg (stmt
, i
);
537 tree t
= TREE_TYPE (arg
);
539 var
= create_tmp_var (t
, "var");
540 arg
= expand_scalar_variables_expr (t
, arg
, TREE_CODE (arg
), NULL
,
541 bb
, region
, rename_map
, gsi
);
542 arg
= build2 (MODIFY_EXPR
, t
, var
, arg
);
543 arg
= force_gimple_operand_gsi (gsi
, arg
, true, NULL
,
544 true, GSI_SAME_STMT
);
545 VEC_quick_push (tree
, args
, arg
);
548 lhs
= gimple_call_lhs (stmt
);
549 var
= create_tmp_var (TREE_TYPE (lhs
), "var");
550 call_expr
= build_call_vec (fn_type
, fn
, args
);
551 call
= gimple_build_call_from_tree (call_expr
);
552 var
= make_ssa_name (var
, call
);
553 gimple_call_set_lhs (call
, var
);
554 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
559 /* Copies at GSI all the scalar computations on which the ssa_name OP0
560 depends on in the SESE: these are all the scalar variables used in
561 the definition of OP0, that are defined outside BB and still in the
562 SESE, i.e. not a parameter of the SESE. The expression that is
563 returned contains only induction variables from the generated code:
564 RENAME_MAP contains the induction variables renaming mapping, and is used
565 to translate the names of induction variables. */
568 expand_scalar_variables_ssa_name (tree type
, tree op0
, basic_block bb
,
569 sese region
, htab_t rename_map
,
570 gimple_stmt_iterator
*gsi
)
575 if (is_parameter (region
, op0
)
577 return fold_convert (type
, get_rename (rename_map
, op0
));
579 def_stmt
= SSA_NAME_DEF_STMT (op0
);
581 /* Check whether we already have a rename for OP0. */
582 new_op
= get_rename (rename_map
, op0
);
585 && gimple_bb (SSA_NAME_DEF_STMT (new_op
)) == bb
)
586 return fold_convert (type
, new_op
);
588 if (gimple_bb (def_stmt
) == bb
)
590 /* If the defining statement is in the basic block already
591 we do not need to create a new expression for it, we
592 only need to ensure its operands are expanded. */
593 expand_scalar_variables_stmt (def_stmt
, bb
, region
, rename_map
, gsi
);
594 return fold_convert (type
, new_op
);
598 if (!gimple_bb (def_stmt
)
599 || !bb_in_sese_p (gimple_bb (def_stmt
), region
))
600 return fold_convert (type
, new_op
);
602 switch (gimple_code (def_stmt
))
606 tree var0
= gimple_assign_rhs1 (def_stmt
);
607 enum tree_code subcode
= gimple_assign_rhs_code (def_stmt
);
608 tree var1
= gimple_assign_rhs2 (def_stmt
);
609 tree type
= gimple_expr_type (def_stmt
);
611 return expand_scalar_variables_expr (type
, var0
, subcode
, var1
, bb
,
612 region
, rename_map
, gsi
);
616 return expand_scalar_variables_call (def_stmt
, bb
, region
, rename_map
, gsi
);
625 /* Copies at GSI all the scalar computations on which the expression
626 OP0 CODE OP1 depends on in the SESE: these are all the scalar
627 variables used in OP0 and OP1, defined outside BB and still defined
628 in the SESE, i.e. not a parameter of the SESE. The expression that
629 is returned contains only induction variables from the generated
630 code: RENAME_MAP contains the induction variables renaming mapping, and is
631 used to translate the names of induction variables. */
634 expand_scalar_variables_expr (tree type
, tree op0
, enum tree_code code
,
635 tree op1
, basic_block bb
, sese region
,
636 htab_t rename_map
, gimple_stmt_iterator
*gsi
)
638 if (TREE_CODE_CLASS (code
) == tcc_constant
639 || TREE_CODE_CLASS (code
) == tcc_declaration
)
642 /* For data references we have to duplicate also its memory
644 if (TREE_CODE_CLASS (code
) == tcc_reference
)
651 tree op
= TREE_OPERAND (op0
, 0);
652 tree res
= expand_scalar_variables_expr
653 (type
, op
, TREE_CODE (op
), NULL
, bb
, region
, rename_map
, gsi
);
654 return build1 (code
, type
, res
);
659 tree old_name
= TREE_OPERAND (op0
, 0);
660 tree expr
= expand_scalar_variables_ssa_name
661 (type
, old_name
, bb
, region
, rename_map
, gsi
);
663 if (TREE_CODE (expr
) != SSA_NAME
664 && is_gimple_reg (old_name
))
666 tree type
= TREE_TYPE (old_name
);
667 tree var
= create_tmp_var (type
, "var");
669 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
670 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL
,
671 true, GSI_SAME_STMT
);
674 return fold_build1 (code
, type
, expr
);
679 tree op00
= TREE_OPERAND (op0
, 0);
680 tree op01
= TREE_OPERAND (op0
, 1);
681 tree op02
= TREE_OPERAND (op0
, 2);
682 tree op03
= TREE_OPERAND (op0
, 3);
683 tree base
= expand_scalar_variables_expr
684 (TREE_TYPE (op00
), op00
, TREE_CODE (op00
), NULL
, bb
, region
,
686 tree subscript
= expand_scalar_variables_expr
687 (TREE_TYPE (op01
), op01
, TREE_CODE (op01
), NULL
, bb
, region
,
690 return build4 (ARRAY_REF
, type
, base
, subscript
, op02
, op03
);
697 /* The above cases should catch everything. */
702 if (TREE_CODE_CLASS (code
) == tcc_unary
)
704 tree op0_type
= TREE_TYPE (op0
);
705 enum tree_code op0_code
= TREE_CODE (op0
);
706 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
707 NULL
, bb
, region
, rename_map
, gsi
);
709 return fold_build1 (code
, type
, op0_expr
);
712 if (TREE_CODE_CLASS (code
) == tcc_binary
713 || TREE_CODE_CLASS (code
) == tcc_comparison
)
715 tree op0_type
= TREE_TYPE (op0
);
716 enum tree_code op0_code
= TREE_CODE (op0
);
717 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
718 NULL
, bb
, region
, rename_map
, gsi
);
719 tree op1_type
= TREE_TYPE (op1
);
720 enum tree_code op1_code
= TREE_CODE (op1
);
721 tree op1_expr
= expand_scalar_variables_expr (op1_type
, op1
, op1_code
,
722 NULL
, bb
, region
, rename_map
, gsi
);
724 return fold_build2 (code
, type
, op0_expr
, op1_expr
);
727 if (code
== SSA_NAME
)
728 return expand_scalar_variables_ssa_name (type
, op0
, bb
, region
, rename_map
, gsi
);
730 if (code
== ADDR_EXPR
)
732 tree op00
= TREE_OPERAND (op0
, 0);
734 if (handled_component_p (op00
)
735 && TREE_CODE (op00
) == ARRAY_REF
)
737 tree e
= expand_scalar_variables_expr (TREE_TYPE (op00
), op00
,
739 NULL
, bb
, region
, rename_map
, gsi
);
740 return fold_build1 (code
, TREE_TYPE (op0
), e
);
750 /* Copies at the beginning of BB all the scalar computations on which
751 STMT depends on in the SESE: these are all the scalar variables used
752 in STMT, defined outside BB and still defined in the SESE, i.e. not a
753 parameter of the SESE. The expression that is returned contains
754 only induction variables from the generated code: RENAME_MAP contains the
755 induction variables renaming mapping, and is used to translate the
756 names of induction variables. */
759 expand_scalar_variables_stmt (gimple stmt
, basic_block bb
, sese region
,
760 htab_t rename_map
, gimple_stmt_iterator
*gsi
)
765 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
767 tree use
= USE_FROM_PTR (use_p
);
768 tree type
= TREE_TYPE (use
);
769 enum tree_code code
= TREE_CODE (use
);
772 if (!is_gimple_reg (use
))
775 /* Don't expand USE if we already have a rename for it. */
776 use_expr
= get_rename (rename_map
, use
);
780 use_expr
= expand_scalar_variables_expr (type
, use
, code
, NULL
, bb
,
781 region
, rename_map
, gsi
);
782 use_expr
= fold_convert (type
, use_expr
);
787 if (is_gimple_debug (stmt
))
789 if (gimple_debug_bind_p (stmt
))
790 gimple_debug_bind_reset_value (stmt
);
797 if (TREE_CODE (use_expr
) != SSA_NAME
)
799 tree var
= create_tmp_var (type
, "var");
801 use_expr
= build2 (MODIFY_EXPR
, type
, var
, use_expr
);
802 use_expr
= force_gimple_operand_gsi (gsi
, use_expr
, true, NULL
,
803 true, GSI_SAME_STMT
);
806 replace_exp (use_p
, use_expr
);
812 /* Copies at the beginning of BB all the scalar computations on which
813 BB depends on in the SESE: these are all the scalar variables used
814 in BB, defined outside BB and still defined in the SESE, i.e. not a
815 parameter of the SESE. The expression that is returned contains
816 only induction variables from the generated code: RENAME_MAP contains the
817 induction variables renaming mapping, and is used to translate the
818 names of induction variables. */
821 expand_scalar_variables (basic_block bb
, sese region
, htab_t rename_map
)
823 gimple_stmt_iterator gsi
;
825 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
827 gimple stmt
= gsi_stmt (gsi
);
828 expand_scalar_variables_stmt (stmt
, bb
, region
, rename_map
, &gsi
);
833 /* Rename all the SSA_NAMEs from block BB according to the RENAME_MAP. */
836 rename_variables (basic_block bb
, htab_t rename_map
)
838 gimple_stmt_iterator gsi
;
839 gimple_stmt_iterator insert_gsi
= gsi_start_bb (bb
);
841 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
842 rename_variables_in_stmt (gsi_stmt (gsi
), rename_map
, &insert_gsi
);
845 /* Remove condition from BB. */
848 remove_condition (basic_block bb
)
850 gimple last
= last_stmt (bb
);
852 if (last
&& gimple_code (last
) == GIMPLE_COND
)
854 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
855 gsi_remove (&gsi
, true);
859 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
862 get_true_edge_from_guard_bb (basic_block bb
)
867 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
868 if (e
->flags
& EDGE_TRUE_VALUE
)
875 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
878 get_false_edge_from_guard_bb (basic_block bb
)
883 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
884 if (!(e
->flags
& EDGE_TRUE_VALUE
))
891 /* Helper structure for htab_traverse in insert_guard_phis. */
895 edge true_edge
, false_edge
;
899 /* Return the default name that is before the guard. */
902 default_before_guard (htab_t before_guard
, tree old_name
)
904 tree res
= get_rename (before_guard
, old_name
);
908 if (is_gimple_reg (res
))
909 return fold_convert (TREE_TYPE (res
), integer_zero_node
);
910 return gimple_default_def (cfun
, SSA_NAME_VAR (res
));
916 /* Prepares EXPR to be a good phi argument when the phi result is
917 RES. Insert needed statements on edge E. */
920 convert_for_phi_arg (tree expr
, tree res
, edge e
)
922 tree type
= TREE_TYPE (res
);
924 if (TREE_TYPE (expr
) != type
)
925 expr
= fold_convert (type
, expr
);
927 if (TREE_CODE (expr
) != SSA_NAME
928 && !is_gimple_min_invariant (expr
))
930 tree var
= create_tmp_var (type
, "var");
933 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
934 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
935 gsi_insert_seq_on_edge_immediate (e
, stmts
);
941 /* Helper function for htab_traverse in insert_guard_phis. */
944 add_guard_exit_phis (void **slot
, void *s
)
946 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
947 struct igp
*i
= (struct igp
*) s
;
948 basic_block bb
= i
->bb
;
949 edge true_edge
= i
->true_edge
;
950 edge false_edge
= i
->false_edge
;
951 tree res
= entry
->old_name
;
952 tree name1
= entry
->expr
;
953 tree name2
= default_before_guard (i
->before_guard
, res
);
956 /* Nothing to be merged if the name before the guard is the same as
961 name1
= convert_for_phi_arg (name1
, res
, true_edge
);
962 name2
= convert_for_phi_arg (name2
, res
, false_edge
);
964 phi
= create_phi_node (res
, bb
);
965 res
= create_new_def_for (gimple_phi_result (phi
), phi
,
966 gimple_phi_result_ptr (phi
));
968 add_phi_arg (phi
, name1
, true_edge
, UNKNOWN_LOCATION
);
969 add_phi_arg (phi
, name2
, false_edge
, UNKNOWN_LOCATION
);
976 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
977 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
978 with NAME1 different than NAME2, then insert in BB the phi node:
980 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
982 if there is no tuple for OLD in BEFORE_GUARD, insert
984 | RES = phi (NAME1 (on TRUE_EDGE),
985 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
987 Finally register in RENAME_MAP the tuple (OLD, RES). */
990 insert_guard_phis (basic_block bb
, edge true_edge
, edge false_edge
,
991 htab_t before_guard
, htab_t rename_map
)
995 i
.true_edge
= true_edge
;
996 i
.false_edge
= false_edge
;
997 i
.before_guard
= before_guard
;
999 update_ssa (TODO_update_ssa
);
1000 htab_traverse (rename_map
, add_guard_exit_phis
, &i
);
1001 update_ssa (TODO_update_ssa
);
1004 /* Create a duplicate of the basic block BB. NOTE: This does not
1005 preserve SSA form. */
1008 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
, htab_t rename_map
)
1010 gimple_stmt_iterator gsi
, gsi_tgt
;
1012 gsi_tgt
= gsi_start_bb (new_bb
);
1013 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1015 def_operand_p def_p
;
1016 ssa_op_iter op_iter
;
1017 gimple stmt
= gsi_stmt (gsi
);
1020 if (gimple_code (stmt
) == GIMPLE_LABEL
)
1023 /* Create a new copy of STMT and duplicate STMT's virtual
1025 copy
= gimple_copy (stmt
);
1026 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1027 mark_sym_for_renaming (gimple_vop (cfun
));
1029 maybe_duplicate_eh_stmt (copy
, stmt
);
1030 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1032 /* Create new names for all the definitions created by COPY and
1033 add replacement mappings for each new name. */
1034 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1036 tree old_name
= DEF_FROM_PTR (def_p
);
1037 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1038 set_rename (rename_map
, old_name
, new_name
);
1043 /* Copies BB and includes in the copied BB all the statements that can
1044 be reached following the use-def chains from the memory accesses,
1045 and returns the next edge following this new block. */
1048 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
1049 edge next_e
, htab_t rename_map
)
1051 basic_block new_bb
= split_edge (next_e
);
1053 next_e
= single_succ_edge (new_bb
);
1054 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
);
1055 remove_condition (new_bb
);
1056 remove_phi_nodes (new_bb
);
1057 expand_scalar_variables (new_bb
, region
, rename_map
);
1058 rename_variables (new_bb
, rename_map
);
1063 /* Returns the outermost loop in SCOP that contains BB. */
1066 outermost_loop_in_sese (sese region
, basic_block bb
)
1070 nest
= bb
->loop_father
;
1071 while (loop_outer (nest
)
1072 && loop_in_sese_p (loop_outer (nest
), region
))
1073 nest
= loop_outer (nest
);
1078 /* Sets the false region of an IF_REGION to REGION. */
1081 if_region_set_false_region (ifsese if_region
, sese region
)
1083 basic_block condition
= if_region_get_condition_block (if_region
);
1084 edge false_edge
= get_false_edge_from_guard_bb (condition
);
1085 basic_block dummy
= false_edge
->dest
;
1086 edge entry_region
= SESE_ENTRY (region
);
1087 edge exit_region
= SESE_EXIT (region
);
1088 basic_block before_region
= entry_region
->src
;
1089 basic_block last_in_region
= exit_region
->src
;
1090 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
1091 htab_hash_pointer (exit_region
),
1094 entry_region
->flags
= false_edge
->flags
;
1095 false_edge
->flags
= exit_region
->flags
;
1097 redirect_edge_pred (entry_region
, condition
);
1098 redirect_edge_pred (exit_region
, before_region
);
1099 redirect_edge_pred (false_edge
, last_in_region
);
1100 redirect_edge_succ (false_edge
, single_succ (dummy
));
1101 delete_basic_block (dummy
);
1103 exit_region
->flags
= EDGE_FALLTHRU
;
1104 recompute_all_dominators ();
1106 SESE_EXIT (region
) = false_edge
;
1108 if (if_region
->false_region
)
1109 free (if_region
->false_region
);
1110 if_region
->false_region
= region
;
1114 struct loop_exit
*loop_exit
= GGC_CNEW (struct loop_exit
);
1116 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
1117 htab_clear_slot (current_loops
->exits
, slot
);
1119 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
1120 htab_hash_pointer (false_edge
),
1122 loop_exit
->e
= false_edge
;
1124 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
1128 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1131 create_if_region_on_edge (edge entry
, tree condition
)
1135 sese sese_region
= XNEW (struct sese_s
);
1136 sese true_region
= XNEW (struct sese_s
);
1137 sese false_region
= XNEW (struct sese_s
);
1138 ifsese if_region
= XNEW (struct ifsese_s
);
1139 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
1141 if_region
->region
= sese_region
;
1142 if_region
->region
->entry
= entry
;
1143 if_region
->region
->exit
= exit
;
1145 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
1147 if (e
->flags
& EDGE_TRUE_VALUE
)
1149 true_region
->entry
= e
;
1150 true_region
->exit
= single_succ_edge (e
->dest
);
1151 if_region
->true_region
= true_region
;
1153 else if (e
->flags
& EDGE_FALSE_VALUE
)
1155 false_region
->entry
= e
;
1156 false_region
->exit
= single_succ_edge (e
->dest
);
1157 if_region
->false_region
= false_region
;
1164 /* Moves REGION in a condition expression:
1172 move_sese_in_condition (sese region
)
1174 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
1177 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
1178 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
1179 if_region_set_false_region (if_region
, region
);
1184 /* Replaces the condition of the IF_REGION with CONDITION:
1192 set_ifsese_condition (ifsese if_region
, tree condition
)
1194 sese region
= if_region
->region
;
1195 edge entry
= region
->entry
;
1196 basic_block bb
= entry
->dest
;
1197 gimple last
= last_stmt (bb
);
1198 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1201 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
1203 gsi_remove (&gsi
, true);
1204 gsi
= gsi_last_bb (bb
);
1205 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
1206 false, GSI_NEW_STMT
);
1207 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
1208 gsi
= gsi_last_bb (bb
);
1209 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
1212 /* Returns the scalar evolution of T in REGION. Every variable that
1213 is not defined in the REGION is considered a parameter. */
1216 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
1219 struct loop
*def_loop
;
1220 basic_block before
= block_before_sese (region
);
1222 if (TREE_CODE (t
) != SSA_NAME
1223 || loop_in_sese_p (loop
, region
))
1224 return instantiate_scev (before
, loop
,
1225 analyze_scalar_evolution (loop
, t
));
1227 if (!defined_in_sese_p (t
, region
))
1230 def
= SSA_NAME_DEF_STMT (t
);
1231 def_loop
= loop_containing_stmt (def
);
1233 if (loop_in_sese_p (def_loop
, region
))
1235 t
= analyze_scalar_evolution (def_loop
, t
);
1236 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
1237 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
1241 return instantiate_scev (before
, loop
, t
);