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 first successor edge of BB with EDGE_TRUE_VALUE flag set. */
400 get_true_edge_from_guard_bb (basic_block bb
)
405 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
406 if (e
->flags
& EDGE_TRUE_VALUE
)
413 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
416 get_false_edge_from_guard_bb (basic_block bb
)
421 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
422 if (!(e
->flags
& EDGE_TRUE_VALUE
))
429 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
432 get_rename (htab_t rename_map
, tree old_name
)
434 struct rename_map_elt_s tmp
;
437 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
438 tmp
.old_name
= old_name
;
439 slot
= htab_find_slot (rename_map
, &tmp
, NO_INSERT
);
442 return ((rename_map_elt
) *slot
)->expr
;
447 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
450 set_rename (htab_t rename_map
, tree old_name
, tree expr
)
452 struct rename_map_elt_s tmp
;
455 if (old_name
== expr
)
458 tmp
.old_name
= old_name
;
459 slot
= htab_find_slot (rename_map
, &tmp
, INSERT
);
467 *slot
= new_rename_map_elt (old_name
, expr
);
470 /* Renames the scalar uses of the statement COPY, using the
471 substitution map RENAME_MAP, inserting the gimplification code at
472 GSI_TGT, for the translation REGION, with the original copied
473 statement in LOOP, and using the induction variable renaming map
477 rename_uses (gimple copy
, htab_t rename_map
, gimple_stmt_iterator
*gsi_tgt
,
478 sese region
, loop_p loop
, VEC (tree
, heap
) *iv_map
)
483 if (is_gimple_debug (copy
))
485 if (gimple_debug_bind_p (copy
))
486 gimple_debug_bind_reset_value (copy
);
493 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_ALL_USES
)
495 tree old_name
= USE_FROM_PTR (use_p
);
499 if (TREE_CODE (old_name
) != SSA_NAME
500 || !is_gimple_reg (old_name
)
501 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
504 new_expr
= get_rename (rename_map
, old_name
);
507 tree type_old_name
= TREE_TYPE (old_name
);
508 tree type_new_expr
= TREE_TYPE (new_expr
);
510 if (type_old_name
!= type_new_expr
511 || (TREE_CODE (new_expr
) != SSA_NAME
512 && is_gimple_reg (old_name
)))
514 tree var
= create_tmp_var (type_old_name
, "var");
516 if (type_old_name
!= type_new_expr
)
517 new_expr
= fold_convert (type_old_name
, new_expr
);
519 new_expr
= build2 (MODIFY_EXPR
, type_old_name
, var
, new_expr
);
520 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, NULL
);
521 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
524 replace_exp (use_p
, new_expr
);
528 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
530 /* At this point we should know the exact scev for each
531 scalar SSA_NAME used in the scop: all the other scalar
532 SSA_NAMEs should have been translated out of SSA using
533 arrays with one element. */
534 gcc_assert (!chrec_contains_undetermined (scev
));
536 new_expr
= chrec_apply_map (scev
, iv_map
);
538 /* The apply should produce an expression tree containing
539 the uses of the new induction variables. We should be
540 able to use new_expr instead of the old_name in the newly
541 generated loop nest. */
542 gcc_assert (!chrec_contains_undetermined (new_expr
)
543 && !tree_contains_chrecs (new_expr
, NULL
));
545 /* Replace the old_name with the new_expr. */
546 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
548 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
549 replace_exp (use_p
, new_expr
);
550 set_rename (rename_map
, old_name
, new_expr
);
554 /* Duplicates the statements of basic block BB into basic block NEW_BB
555 and compute the new induction variables according to the IV_MAP. */
558 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
560 VEC (tree
, heap
) *iv_map
, sese region
)
562 gimple_stmt_iterator gsi
, gsi_tgt
;
563 loop_p loop
= bb
->loop_father
;
565 gsi_tgt
= gsi_start_bb (new_bb
);
566 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
570 gimple stmt
= gsi_stmt (gsi
);
574 /* Do not copy labels or conditions. */
575 if (gimple_code (stmt
) == GIMPLE_LABEL
576 || gimple_code (stmt
) == GIMPLE_COND
)
579 /* Do not copy induction variables. */
580 if (is_gimple_assign (stmt
)
581 && (lhs
= gimple_assign_lhs (stmt
))
582 && TREE_CODE (lhs
) == SSA_NAME
583 && is_gimple_reg (lhs
)
584 && scev_analyzable_p (lhs
, region
))
587 /* Create a new copy of STMT and duplicate STMT's virtual
589 copy
= gimple_copy (stmt
);
590 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
591 mark_sym_for_renaming (gimple_vop (cfun
));
593 maybe_duplicate_eh_stmt (copy
, stmt
);
594 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
596 /* Create new names for all the definitions created by COPY and
597 add replacement mappings for each new name. */
598 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
600 tree old_name
= DEF_FROM_PTR (def_p
);
601 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
602 set_rename (rename_map
, old_name
, new_name
);
605 rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
);
611 /* Copies BB and includes in the copied BB all the statements that can
612 be reached following the use-def chains from the memory accesses,
613 and returns the next edge following this new block. */
616 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
617 edge next_e
, VEC (tree
, heap
) *iv_map
)
619 basic_block new_bb
= split_edge (next_e
);
620 htab_t rename_map
= htab_create (10, rename_map_elt_info
,
621 eq_rename_map_elts
, free
);
623 next_e
= single_succ_edge (new_bb
);
624 graphite_copy_stmts_from_block (bb
, new_bb
, rename_map
, iv_map
, region
);
625 remove_phi_nodes (new_bb
);
626 htab_delete (rename_map
);
631 /* Returns the outermost loop in SCOP that contains BB. */
634 outermost_loop_in_sese (sese region
, basic_block bb
)
638 nest
= bb
->loop_father
;
639 while (loop_outer (nest
)
640 && loop_in_sese_p (loop_outer (nest
), region
))
641 nest
= loop_outer (nest
);
646 /* Sets the false region of an IF_REGION to REGION. */
649 if_region_set_false_region (ifsese if_region
, sese region
)
651 basic_block condition
= if_region_get_condition_block (if_region
);
652 edge false_edge
= get_false_edge_from_guard_bb (condition
);
653 basic_block dummy
= false_edge
->dest
;
654 edge entry_region
= SESE_ENTRY (region
);
655 edge exit_region
= SESE_EXIT (region
);
656 basic_block before_region
= entry_region
->src
;
657 basic_block last_in_region
= exit_region
->src
;
658 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
659 htab_hash_pointer (exit_region
),
662 entry_region
->flags
= false_edge
->flags
;
663 false_edge
->flags
= exit_region
->flags
;
665 redirect_edge_pred (entry_region
, condition
);
666 redirect_edge_pred (exit_region
, before_region
);
667 redirect_edge_pred (false_edge
, last_in_region
);
668 redirect_edge_succ (false_edge
, single_succ (dummy
));
669 delete_basic_block (dummy
);
671 exit_region
->flags
= EDGE_FALLTHRU
;
672 recompute_all_dominators ();
674 SESE_EXIT (region
) = false_edge
;
676 if (if_region
->false_region
)
677 free (if_region
->false_region
);
678 if_region
->false_region
= region
;
682 struct loop_exit
*loop_exit
= GGC_CNEW (struct loop_exit
);
684 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
685 htab_clear_slot (current_loops
->exits
, slot
);
687 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
688 htab_hash_pointer (false_edge
),
690 loop_exit
->e
= false_edge
;
692 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
696 /* Creates an IFSESE with CONDITION on edge ENTRY. */
699 create_if_region_on_edge (edge entry
, tree condition
)
703 sese sese_region
= XNEW (struct sese_s
);
704 sese true_region
= XNEW (struct sese_s
);
705 sese false_region
= XNEW (struct sese_s
);
706 ifsese if_region
= XNEW (struct ifsese_s
);
707 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
709 if_region
->region
= sese_region
;
710 if_region
->region
->entry
= entry
;
711 if_region
->region
->exit
= exit
;
713 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
715 if (e
->flags
& EDGE_TRUE_VALUE
)
717 true_region
->entry
= e
;
718 true_region
->exit
= single_succ_edge (e
->dest
);
719 if_region
->true_region
= true_region
;
721 else if (e
->flags
& EDGE_FALSE_VALUE
)
723 false_region
->entry
= e
;
724 false_region
->exit
= single_succ_edge (e
->dest
);
725 if_region
->false_region
= false_region
;
732 /* Moves REGION in a condition expression:
740 move_sese_in_condition (sese region
)
742 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
745 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
746 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
747 if_region_set_false_region (if_region
, region
);
752 /* Replaces the condition of the IF_REGION with CONDITION:
760 set_ifsese_condition (ifsese if_region
, tree condition
)
762 sese region
= if_region
->region
;
763 edge entry
= region
->entry
;
764 basic_block bb
= entry
->dest
;
765 gimple last
= last_stmt (bb
);
766 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
769 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
771 gsi_remove (&gsi
, true);
772 gsi
= gsi_last_bb (bb
);
773 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
774 false, GSI_NEW_STMT
);
775 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
776 gsi
= gsi_last_bb (bb
);
777 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
780 /* Returns the scalar evolution of T in REGION. Every variable that
781 is not defined in the REGION is considered a parameter. */
784 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
787 struct loop
*def_loop
;
788 basic_block before
= block_before_sese (region
);
790 if (TREE_CODE (t
) != SSA_NAME
791 || loop_in_sese_p (loop
, region
))
792 return instantiate_scev (before
, loop
,
793 analyze_scalar_evolution (loop
, t
));
795 if (!defined_in_sese_p (t
, region
))
798 def
= SSA_NAME_DEF_STMT (t
);
799 def_loop
= loop_containing_stmt (def
);
801 if (loop_in_sese_p (def_loop
, region
))
803 t
= analyze_scalar_evolution (def_loop
, t
);
804 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
805 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
809 return instantiate_scev (before
, loop
, t
);