1 /* Tail merging for gimple.
2 Copyright (C) 2011-2017 Free Software Foundation, Inc.
3 Contributed by Tom de Vries (tom@codesourcery.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 gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
28 hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
30 struct FILED.1638 * fpD.2605;
31 charD.1 fileNameD.2604[1000];
33 const charD.1 * restrict outputFileName.0D.3914;
36 # PRED: ENTRY [100.0%] (fallthru,exec)
37 # PT = nonlocal { D.3926 } (restr)
38 outputFileName.0D.3914_3
39 = (const charD.1 * restrict) outputFileNameD.2600_2(D);
40 # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
41 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
42 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
43 sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
44 # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
45 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
46 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
47 D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
55 # PRED: 2 [10.0%] (true,exec)
56 # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
57 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
58 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
59 freeD.898 (ctxD.2601_5(D));
61 # SUCC: 7 [100.0%] (fallthru,exec)
64 # PRED: 2 [90.0%] (false,exec)
65 # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
66 # PT = nonlocal escaped
67 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
68 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
69 fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
77 # PRED: 4 [1.9%] (true,exec)
78 # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
79 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
80 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
81 freeD.898 (ctxD.2601_5(D));
83 # SUCC: 7 [100.0%] (fallthru,exec)
86 # PRED: 4 [98.1%] (false,exec)
87 # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
88 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
89 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
90 fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
91 # SUCC: 7 [100.0%] (fallthru,exec)
94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
95 6 [100.0%] (fallthru,exec)
98 # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
99 # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
101 # VUSE <.MEMD.3923_11>
103 # SUCC: EXIT [100.0%]
106 bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
107 same successors, and the same operations.
112 A technique called tail merging (or cross jumping) can fix the example
113 above. For a block, we look for common code at the end (the tail) of the
114 predecessor blocks, and insert jumps from one block to the other.
115 The example is a special case for tail merging, in that 2 whole blocks
116 can be merged, rather than just the end parts of it.
117 We currently only focus on whole block merging, so in that sense
118 calling this pass tail merge is a bit of a misnomer.
120 We distinguish 2 kinds of situations in which blocks can be merged:
121 - same operations, same predecessors. The successor edges coming from one
122 block are redirected to come from the other block.
123 - same operations, same successors. The predecessor edges entering one block
124 are redirected to enter the other block. Note that this operation might
125 involve introducing phi operations.
127 For efficient implementation, we would like to value numbers the blocks, and
128 have a comparison operator that tells us whether the blocks are equal.
129 Besides being runtime efficient, block value numbering should also abstract
130 from irrelevant differences in order of operations, much like normal value
131 numbering abstracts from irrelevant order of operations.
133 For the first situation (same_operations, same predecessors), normal value
134 numbering fits well. We can calculate a block value number based on the
135 value numbers of the defs and vdefs.
137 For the second situation (same operations, same successors), this approach
138 doesn't work so well. We can illustrate this using the example. The calls
139 to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
140 remain different in value numbering, since they represent different memory
141 states. So the resulting vdefs of the frees will be different in value
142 numbering, so the block value numbers will be different.
144 The reason why we call the blocks equal is not because they define the same
145 values, but because uses in the blocks use (possibly different) defs in the
146 same way. To be able to detect this efficiently, we need to do some kind of
147 reverse value numbering, meaning number the uses rather than the defs, and
148 calculate a block value number based on the value number of the uses.
149 Ideally, a block comparison operator will also indicate which phis are needed
152 For the moment, we don't do block value numbering, but we do insn-by-insn
153 matching, using scc value numbers to match operations with results, and
154 structural comparison otherwise, while ignoring vop mismatches.
159 1. The pass first determines all groups of blocks with the same successor
161 2. Within each group, it tries to determine clusters of equal basic blocks.
162 3. The clusters are applied.
163 4. The same successor groups are updated.
164 5. This process is repeated from 2 onwards, until no more changes.
170 - handles only 'same operations, same successors'.
171 It handles same predecessors as a special subcase though.
172 - does not implement the reverse value numbering and block value numbering.
173 - improve memory allocation: use garbage collected memory, obstacks,
174 allocpools where appropriate.
175 - no insertion of gimple_reg phis, We only introduce vop-phis.
176 - handle blocks with gimple_reg phi_nodes.
180 This 'pass' is not a stand-alone gimple pass, but runs as part of
181 pass_pre, in order to share the value numbering.
186 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
190 #include "coretypes.h"
194 #include "cfghooks.h"
195 #include "tree-pass.h"
197 #include "fold-const.h"
198 #include "trans-mem.h"
200 #include "cfgcleanup.h"
201 #include "gimple-iterator.h"
202 #include "tree-cfg.h"
203 #include "tree-into-ssa.h"
205 #include "tree-ssa-sccvn.h"
209 /* Describes a group of bbs with the same successors. The successor bbs are
210 cached in succs, and the successor edge flags are cached in succ_flags.
211 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
212 it's marked in inverse.
213 Additionally, the hash value for the struct is cached in hashval, and
214 in_worklist indicates whether it's currently part of worklist. */
216 struct same_succ
: pointer_hash
<same_succ
>
218 /* The bbs that have the same successor bbs. */
220 /* The successor bbs. */
222 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
225 /* The edge flags for each of the successor bbs. */
227 /* Indicates whether the struct is currently in the worklist. */
229 /* The hash value of the struct. */
232 /* hash_table support. */
233 static inline hashval_t
hash (const same_succ
*);
234 static int equal (const same_succ
*, const same_succ
*);
235 static void remove (same_succ
*);
238 /* hash routine for hash_table support, returns hashval of E. */
241 same_succ::hash (const same_succ
*e
)
246 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
250 /* The bbs in the cluster. */
252 /* The preds of the bbs in the cluster. */
254 /* Index in all_clusters vector. */
256 /* The bb to replace the cluster with. */
264 /* The number of non-debug statements in the bb. */
266 /* The same_succ that this bb is a member of. */
267 same_succ
*bb_same_succ
;
268 /* The cluster that this bb is a member of. */
270 /* The vop state at the exit of a bb. This is shortlived data, used to
271 communicate data between update_block_by and update_vuses. */
273 /* The bb that either contains or is dominated by the dependencies of the
278 /* Macros to access the fields of struct aux_bb_info. */
280 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
281 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
282 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
283 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
284 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
286 /* Returns true if the only effect a statement STMT has, is to define locally
290 stmt_local_def (gimple
*stmt
)
292 basic_block bb
, def_bb
;
293 imm_use_iterator iter
;
298 if (gimple_vdef (stmt
) != NULL_TREE
299 || gimple_has_side_effects (stmt
)
300 || gimple_could_trap_p_1 (stmt
, false, false)
301 || gimple_vuse (stmt
) != NULL_TREE
)
304 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
308 val
= DEF_FROM_PTR (def_p
);
309 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
312 def_bb
= gimple_bb (stmt
);
314 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
316 if (is_gimple_debug (USE_STMT (use_p
)))
318 bb
= gimple_bb (USE_STMT (use_p
));
322 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
323 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
332 /* Let GSI skip forwards over local defs. */
335 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
341 if (gsi_end_p (*gsi
))
343 stmt
= gsi_stmt (*gsi
);
344 if (!stmt_local_def (stmt
))
346 gsi_next_nondebug (gsi
);
350 /* VAL1 and VAL2 are either:
351 - uses in BB1 and BB2, or
352 - phi alternatives for BB1 and BB2.
353 Return true if the uses have the same gvn value. */
356 gvn_uses_equal (tree val1
, tree val2
)
358 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
363 if (vn_valueize (val1
) != vn_valueize (val2
))
366 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
367 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
370 /* Prints E to FILE. */
373 same_succ_print (FILE *file
, const same_succ
*e
)
376 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
377 bitmap_print (file
, e
->succs
, "succs:", "\n");
378 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
379 fprintf (file
, "flags:");
380 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
381 fprintf (file
, " %x", e
->succ_flags
[i
]);
382 fprintf (file
, "\n");
385 /* Prints same_succ VE to VFILE. */
388 ssa_same_succ_print_traverse (same_succ
**pe
, FILE *file
)
390 const same_succ
*e
= *pe
;
391 same_succ_print (file
, e
);
395 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
398 update_dep_bb (basic_block use_bb
, tree val
)
403 if (TREE_CODE (val
) != SSA_NAME
)
406 /* Skip use of global def. */
407 if (SSA_NAME_IS_DEFAULT_DEF (val
))
410 /* Skip use of local def. */
411 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
412 if (dep_bb
== use_bb
)
415 if (BB_DEP_BB (use_bb
) == NULL
416 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
417 BB_DEP_BB (use_bb
) = dep_bb
;
420 /* Update BB_DEP_BB, given the dependencies in STMT. */
423 stmt_update_dep_bb (gimple
*stmt
)
428 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
429 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
432 /* Calculates hash value for same_succ VE. */
435 same_succ_hash (const same_succ
*e
)
437 inchash::hash
hstate (bitmap_hash (e
->succs
));
440 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
441 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
448 for (gimple_stmt_iterator gsi
= gsi_start_nondebug_bb (bb
);
449 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
451 stmt
= gsi_stmt (gsi
);
452 stmt_update_dep_bb (stmt
);
453 if (stmt_local_def (stmt
))
457 hstate
.add_int (gimple_code (stmt
));
458 if (is_gimple_assign (stmt
))
459 hstate
.add_int (gimple_assign_rhs_code (stmt
));
460 if (!is_gimple_call (stmt
))
462 if (gimple_call_internal_p (stmt
))
463 hstate
.add_int (gimple_call_internal_fn (stmt
));
466 inchash::add_expr (gimple_call_fn (stmt
), hstate
);
467 if (gimple_call_chain (stmt
))
468 inchash::add_expr (gimple_call_chain (stmt
), hstate
);
470 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
472 arg
= gimple_call_arg (stmt
, i
);
473 arg
= vn_valueize (arg
);
474 inchash::add_expr (arg
, hstate
);
478 hstate
.add_int (size
);
481 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
483 flags
= e
->succ_flags
[i
];
484 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
485 hstate
.add_int (flags
);
488 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
490 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
491 for (gphi_iterator gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
));
495 gphi
*phi
= gsi
.phi ();
496 tree lhs
= gimple_phi_result (phi
);
497 tree val
= gimple_phi_arg_def (phi
, n
);
499 if (virtual_operand_p (lhs
))
501 update_dep_bb (bb
, val
);
505 return hstate
.end ();
508 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
509 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
510 the other edge flags. */
513 inverse_flags (const same_succ
*e1
, const same_succ
*e2
)
515 int f1a
, f1b
, f2a
, f2b
;
516 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
518 if (e1
->succ_flags
.length () != 2)
521 f1a
= e1
->succ_flags
[0];
522 f1b
= e1
->succ_flags
[1];
523 f2a
= e2
->succ_flags
[0];
524 f2b
= e2
->succ_flags
[1];
526 if (f1a
== f2a
&& f1b
== f2b
)
529 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
532 /* Compares SAME_SUCCs E1 and E2. */
535 same_succ::equal (const same_succ
*e1
, const same_succ
*e2
)
537 unsigned int i
, first1
, first2
;
538 gimple_stmt_iterator gsi1
, gsi2
;
540 basic_block bb1
, bb2
;
545 if (e1
->hashval
!= e2
->hashval
)
548 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
551 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
554 if (!inverse_flags (e1
, e2
))
556 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
557 if (e1
->succ_flags
[i
] != e2
->succ_flags
[i
])
561 first1
= bitmap_first_set_bit (e1
->bbs
);
562 first2
= bitmap_first_set_bit (e2
->bbs
);
564 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
565 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
567 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
570 gsi1
= gsi_start_nondebug_bb (bb1
);
571 gsi2
= gsi_start_nondebug_bb (bb2
);
572 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
573 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
574 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
576 s1
= gsi_stmt (gsi1
);
577 s2
= gsi_stmt (gsi2
);
578 if (gimple_code (s1
) != gimple_code (s2
))
580 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
582 gsi_next_nondebug (&gsi1
);
583 gsi_next_nondebug (&gsi2
);
584 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
585 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
591 /* Alloc and init a new SAME_SUCC. */
594 same_succ_alloc (void)
596 same_succ
*same
= XNEW (struct same_succ
);
598 same
->bbs
= BITMAP_ALLOC (NULL
);
599 same
->succs
= BITMAP_ALLOC (NULL
);
600 same
->inverse
= BITMAP_ALLOC (NULL
);
601 same
->succ_flags
.create (10);
602 same
->in_worklist
= false;
607 /* Delete same_succ E. */
610 same_succ::remove (same_succ
*e
)
612 BITMAP_FREE (e
->bbs
);
613 BITMAP_FREE (e
->succs
);
614 BITMAP_FREE (e
->inverse
);
615 e
->succ_flags
.release ();
620 /* Reset same_succ SAME. */
623 same_succ_reset (same_succ
*same
)
625 bitmap_clear (same
->bbs
);
626 bitmap_clear (same
->succs
);
627 bitmap_clear (same
->inverse
);
628 same
->succ_flags
.truncate (0);
631 static hash_table
<same_succ
> *same_succ_htab
;
633 /* Array that is used to store the edge flags for a successor. */
635 static int *same_succ_edge_flags
;
637 /* Bitmap that is used to mark bbs that are recently deleted. */
639 static bitmap deleted_bbs
;
641 /* Bitmap that is used to mark predecessors of bbs that are
644 static bitmap deleted_bb_preds
;
646 /* Prints same_succ_htab to stderr. */
648 extern void debug_same_succ (void);
650 debug_same_succ ( void)
652 same_succ_htab
->traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
656 /* Vector of bbs to process. */
658 static vec
<same_succ
*> worklist
;
660 /* Prints worklist to FILE. */
663 print_worklist (FILE *file
)
666 for (i
= 0; i
< worklist
.length (); ++i
)
667 same_succ_print (file
, worklist
[i
]);
670 /* Adds SAME to worklist. */
673 add_to_worklist (same_succ
*same
)
675 if (same
->in_worklist
)
678 if (bitmap_count_bits (same
->bbs
) < 2)
681 same
->in_worklist
= true;
682 worklist
.safe_push (same
);
685 /* Add BB to same_succ_htab. */
688 find_same_succ_bb (basic_block bb
, same_succ
**same_p
)
692 same_succ
*same
= *same_p
;
698 /* Be conservative with loop structure. It's not evident that this test
699 is sufficient. Before tail-merge, we've just called
700 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
701 set, so there's no guarantee that the loop->latch value is still valid.
702 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
703 start of pre, we've kept that property intact throughout pre, and are
704 keeping it throughout tail-merge using this test. */
705 || bb
->loop_father
->latch
== bb
)
707 bitmap_set_bit (same
->bbs
, bb
->index
);
708 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
710 int index
= e
->dest
->index
;
711 bitmap_set_bit (same
->succs
, index
);
712 same_succ_edge_flags
[index
] = e
->flags
;
714 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
715 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
717 same
->hashval
= same_succ_hash (same
);
719 slot
= same_succ_htab
->find_slot_with_hash (same
, same
->hashval
, INSERT
);
723 BB_SAME_SUCC (bb
) = same
;
724 add_to_worklist (same
);
729 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
730 BB_SAME_SUCC (bb
) = *slot
;
731 add_to_worklist (*slot
);
732 if (inverse_flags (same
, *slot
))
733 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
734 same_succ_reset (same
);
738 /* Find bbs with same successors. */
741 find_same_succ (void)
743 same_succ
*same
= same_succ_alloc ();
746 FOR_EACH_BB_FN (bb
, cfun
)
748 find_same_succ_bb (bb
, &same
);
750 same
= same_succ_alloc ();
753 same_succ::remove (same
);
756 /* Initializes worklist administration. */
761 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
762 same_succ_htab
= new hash_table
<same_succ
> (n_basic_blocks_for_fn (cfun
));
763 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
764 deleted_bbs
= BITMAP_ALLOC (NULL
);
765 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
766 worklist
.create (n_basic_blocks_for_fn (cfun
));
769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
771 fprintf (dump_file
, "initial worklist:\n");
772 print_worklist (dump_file
);
776 /* Deletes worklist administration. */
779 delete_worklist (void)
781 free_aux_for_blocks ();
782 delete same_succ_htab
;
783 same_succ_htab
= NULL
;
784 XDELETEVEC (same_succ_edge_flags
);
785 same_succ_edge_flags
= NULL
;
786 BITMAP_FREE (deleted_bbs
);
787 BITMAP_FREE (deleted_bb_preds
);
791 /* Mark BB as deleted, and mark its predecessors. */
794 mark_basic_block_deleted (basic_block bb
)
799 bitmap_set_bit (deleted_bbs
, bb
->index
);
801 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
802 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
805 /* Removes BB from its corresponding same_succ. */
808 same_succ_flush_bb (basic_block bb
)
810 same_succ
*same
= BB_SAME_SUCC (bb
);
814 BB_SAME_SUCC (bb
) = NULL
;
815 if (bitmap_single_bit_set_p (same
->bbs
))
816 same_succ_htab
->remove_elt_with_hash (same
, same
->hashval
);
818 bitmap_clear_bit (same
->bbs
, bb
->index
);
821 /* Removes all bbs in BBS from their corresponding same_succ. */
824 same_succ_flush_bbs (bitmap bbs
)
829 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
830 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
833 /* Release the last vdef in BB, either normal or phi result. */
836 release_last_vdef (basic_block bb
)
838 for (gimple_stmt_iterator i
= gsi_last_bb (bb
); !gsi_end_p (i
);
839 gsi_prev_nondebug (&i
))
841 gimple
*stmt
= gsi_stmt (i
);
842 if (gimple_vdef (stmt
) == NULL_TREE
)
845 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
849 for (gphi_iterator i
= gsi_start_phis (bb
); !gsi_end_p (i
);
852 gphi
*phi
= i
.phi ();
853 tree res
= gimple_phi_result (phi
);
855 if (!virtual_operand_p (res
))
858 mark_virtual_phi_result_for_renaming (phi
);
863 /* For deleted_bb_preds, find bbs with same successors. */
866 update_worklist (void)
873 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
874 bitmap_clear (deleted_bbs
);
876 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
877 same_succ_flush_bbs (deleted_bb_preds
);
879 same
= same_succ_alloc ();
880 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
882 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
883 gcc_assert (bb
!= NULL
);
884 find_same_succ_bb (bb
, &same
);
886 same
= same_succ_alloc ();
888 same_succ::remove (same
);
889 bitmap_clear (deleted_bb_preds
);
892 /* Prints cluster C to FILE. */
895 print_cluster (FILE *file
, bb_cluster
*c
)
899 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
900 bitmap_print (file
, c
->preds
, "preds:", "\n");
903 /* Prints cluster C to stderr. */
905 extern void debug_cluster (bb_cluster
*);
907 debug_cluster (bb_cluster
*c
)
909 print_cluster (stderr
, c
);
912 /* Update C->rep_bb, given that BB is added to the cluster. */
915 update_rep_bb (bb_cluster
*c
, basic_block bb
)
918 if (c
->rep_bb
== NULL
)
924 /* Current needs no deps, keep it. */
925 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
928 /* Bb needs no deps, change rep_bb. */
929 if (BB_DEP_BB (bb
) == NULL
)
935 /* Bb needs last deps earlier than current, change rep_bb. A potential
936 problem with this, is that the first deps might also be earlier, which
937 would mean we prefer longer lifetimes for the deps. To be able to check
938 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
939 BB_DEP_BB, which is really BB_LAST_DEP_BB.
940 The benefit of choosing the bb with last deps earlier, is that it can
941 potentially be used as replacement for more bbs. */
942 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
946 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
949 add_bb_to_cluster (bb_cluster
*c
, basic_block bb
)
954 bitmap_set_bit (c
->bbs
, bb
->index
);
956 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
957 bitmap_set_bit (c
->preds
, e
->src
->index
);
959 update_rep_bb (c
, bb
);
962 /* Allocate and init new cluster. */
968 c
= XCNEW (bb_cluster
);
969 c
->bbs
= BITMAP_ALLOC (NULL
);
970 c
->preds
= BITMAP_ALLOC (NULL
);
975 /* Delete clusters. */
978 delete_cluster (bb_cluster
*c
)
982 BITMAP_FREE (c
->bbs
);
983 BITMAP_FREE (c
->preds
);
988 /* Array that contains all clusters. */
990 static vec
<bb_cluster
*> all_clusters
;
992 /* Allocate all cluster vectors. */
995 alloc_cluster_vectors (void)
997 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1000 /* Reset all cluster vectors. */
1003 reset_cluster_vectors (void)
1007 for (i
= 0; i
< all_clusters
.length (); ++i
)
1008 delete_cluster (all_clusters
[i
]);
1009 all_clusters
.truncate (0);
1010 FOR_EACH_BB_FN (bb
, cfun
)
1011 BB_CLUSTER (bb
) = NULL
;
1014 /* Delete all cluster vectors. */
1017 delete_cluster_vectors (void)
1020 for (i
= 0; i
< all_clusters
.length (); ++i
)
1021 delete_cluster (all_clusters
[i
]);
1022 all_clusters
.release ();
1025 /* Merge cluster C2 into C1. */
1028 merge_clusters (bb_cluster
*c1
, bb_cluster
*c2
)
1030 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1031 bitmap_ior_into (c1
->preds
, c2
->preds
);
1034 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1035 all_clusters, or merge c with existing cluster. */
1038 set_cluster (basic_block bb1
, basic_block bb2
)
1040 basic_block merge_bb
, other_bb
;
1041 bb_cluster
*merge
, *old
, *c
;
1043 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1046 add_bb_to_cluster (c
, bb1
);
1047 add_bb_to_cluster (c
, bb2
);
1048 BB_CLUSTER (bb1
) = c
;
1049 BB_CLUSTER (bb2
) = c
;
1050 c
->index
= all_clusters
.length ();
1051 all_clusters
.safe_push (c
);
1053 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1055 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1056 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1057 merge
= BB_CLUSTER (merge_bb
);
1058 add_bb_to_cluster (merge
, other_bb
);
1059 BB_CLUSTER (other_bb
) = merge
;
1061 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1066 old
= BB_CLUSTER (bb2
);
1067 merge
= BB_CLUSTER (bb1
);
1068 merge_clusters (merge
, old
);
1069 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1070 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1071 all_clusters
[old
->index
] = NULL
;
1072 update_rep_bb (merge
, old
->rep_bb
);
1073 delete_cluster (old
);
1079 /* Return true if gimple operands T1 and T2 have the same value. */
1082 gimple_operand_equal_value_p (tree t1
, tree t2
)
1091 if (operand_equal_p (t1
, t2
, OEP_MATCH_SIDE_EFFECTS
))
1094 return gvn_uses_equal (t1
, t2
);
1097 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1098 gimple_bb (s2) are members of SAME_SUCC. */
1101 gimple_equal_p (same_succ
*same_succ
, gimple
*s1
, gimple
*s2
)
1105 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1108 enum tree_code code1
, code2
;
1110 if (gimple_code (s1
) != gimple_code (s2
))
1113 switch (gimple_code (s1
))
1116 if (!gimple_call_same_target_p (s1
, s2
))
1119 t1
= gimple_call_chain (s1
);
1120 t2
= gimple_call_chain (s2
);
1121 if (!gimple_operand_equal_value_p (t1
, t2
))
1124 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1127 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1129 t1
= gimple_call_arg (s1
, i
);
1130 t2
= gimple_call_arg (s2
, i
);
1131 if (!gimple_operand_equal_value_p (t1
, t2
))
1135 lhs1
= gimple_get_lhs (s1
);
1136 lhs2
= gimple_get_lhs (s2
);
1137 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1139 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1141 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1142 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1143 return operand_equal_p (lhs1
, lhs2
, 0);
1146 lhs1
= gimple_get_lhs (s1
);
1147 lhs2
= gimple_get_lhs (s2
);
1148 if (TREE_CODE (lhs1
) != SSA_NAME
1149 && TREE_CODE (lhs2
) != SSA_NAME
)
1150 return (operand_equal_p (lhs1
, lhs2
, 0)
1151 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1152 gimple_assign_rhs1 (s2
)));
1153 else if (TREE_CODE (lhs1
) == SSA_NAME
1154 && TREE_CODE (lhs2
) == SSA_NAME
)
1155 return operand_equal_p (gimple_assign_rhs1 (s1
),
1156 gimple_assign_rhs1 (s2
), 0);
1160 t1
= gimple_cond_lhs (s1
);
1161 t2
= gimple_cond_lhs (s2
);
1162 if (!gimple_operand_equal_value_p (t1
, t2
))
1165 t1
= gimple_cond_rhs (s1
);
1166 t2
= gimple_cond_rhs (s2
);
1167 if (!gimple_operand_equal_value_p (t1
, t2
))
1170 code1
= gimple_expr_code (s1
);
1171 code2
= gimple_expr_code (s2
);
1172 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1173 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1176 bool honor_nans
= HONOR_NANS (t1
);
1177 code2
= invert_tree_comparison (code2
, honor_nans
);
1179 return code1
== code2
;
1186 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1187 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1188 processed statements. */
1191 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1199 if (gsi_end_p (*gsi
))
1201 stmt
= gsi_stmt (*gsi
);
1203 lvuse
= gimple_vuse (stmt
);
1204 if (lvuse
!= NULL_TREE
)
1207 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1208 *vuse_escaped
= true;
1211 if (!stmt_local_def (stmt
))
1213 gsi_prev_nondebug (gsi
);
1217 /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1218 STMT2 are allowed to be merged. */
1221 merge_stmts_p (gimple
*stmt1
, gimple
*stmt2
)
1223 /* What could be better than this here is to blacklist the bb
1224 containing the stmt, when encountering the stmt f.i. in
1226 if (is_tm_ending (stmt1
))
1229 /* Verify EH landing pads. */
1230 if (lookup_stmt_eh_lp_fn (cfun
, stmt1
) != lookup_stmt_eh_lp_fn (cfun
, stmt2
))
1233 if (is_gimple_call (stmt1
)
1234 && gimple_call_internal_p (stmt1
))
1235 switch (gimple_call_internal_fn (stmt1
))
1237 case IFN_UBSAN_NULL
:
1238 case IFN_UBSAN_BOUNDS
:
1239 case IFN_UBSAN_VPTR
:
1240 case IFN_UBSAN_CHECK_ADD
:
1241 case IFN_UBSAN_CHECK_SUB
:
1242 case IFN_UBSAN_CHECK_MUL
:
1243 case IFN_UBSAN_OBJECT_SIZE
:
1244 case IFN_ASAN_CHECK
:
1245 /* For these internal functions, gimple_location is an implicit
1246 parameter, which will be used explicitly after expansion.
1247 Merging these statements may cause confusing line numbers in
1248 sanitizer messages. */
1249 return gimple_location (stmt1
) == gimple_location (stmt2
);
1257 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1261 find_duplicate (same_succ
*same_succ
, basic_block bb1
, basic_block bb2
)
1263 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1264 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1265 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1266 bool vuse_escaped
= false;
1268 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1269 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1271 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1273 gimple
*stmt1
= gsi_stmt (gsi1
);
1274 gimple
*stmt2
= gsi_stmt (gsi2
);
1276 if (gimple_code (stmt1
) == GIMPLE_LABEL
1277 && gimple_code (stmt2
) == GIMPLE_LABEL
)
1280 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1283 if (!merge_stmts_p (stmt1
, stmt2
))
1286 gsi_prev_nondebug (&gsi1
);
1287 gsi_prev_nondebug (&gsi2
);
1288 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1289 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1292 while (!gsi_end_p (gsi1
) && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1294 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi1
)));
1295 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
1299 while (!gsi_end_p (gsi2
) && gimple_code (gsi_stmt (gsi2
)) == GIMPLE_LABEL
)
1301 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi2
)));
1302 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
1306 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1309 /* If the incoming vuses are not the same, and the vuse escaped into an
1310 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1311 which potentially means the semantics of one of the blocks will be changed.
1312 TODO: make this check more precise. */
1313 if (vuse_escaped
&& vuse1
!= vuse2
)
1317 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1318 bb1
->index
, bb2
->index
);
1320 set_cluster (bb1
, bb2
);
1323 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1327 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1329 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1332 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1334 gphi
*phi
= gsi
.phi ();
1335 tree lhs
= gimple_phi_result (phi
);
1336 tree val1
= gimple_phi_arg_def (phi
, n1
);
1337 tree val2
= gimple_phi_arg_def (phi
, n2
);
1339 if (virtual_operand_p (lhs
))
1342 if (operand_equal_for_phi_arg_p (val1
, val2
))
1344 if (gvn_uses_equal (val1
, val2
))
1353 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1354 phi alternatives for BB1 and BB2 are equal. */
1357 same_phi_alternatives (same_succ
*same_succ
, basic_block bb1
, basic_block bb2
)
1364 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1366 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1367 e1
= find_edge (bb1
, succ
);
1368 e2
= find_edge (bb2
, succ
);
1369 if (e1
->flags
& EDGE_COMPLEX
1370 || e2
->flags
& EDGE_COMPLEX
)
1373 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1375 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1382 /* Return true if BB has non-vop phis. */
1385 bb_has_non_vop_phi (basic_block bb
)
1387 gimple_seq phis
= phi_nodes (bb
);
1393 if (!gimple_seq_singleton_p (phis
))
1396 phi
= gimple_seq_first_stmt (phis
);
1397 return !virtual_operand_p (gimple_phi_result (phi
));
1400 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1401 invariant that uses in FROM are dominates by their defs. */
1404 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1406 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1413 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1414 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1415 bitmap_set_bit (from_preds
, e
->src
->index
);
1416 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1417 BITMAP_FREE (from_preds
);
1419 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1422 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1423 replacement bb) and vice versa maintains the invariant that uses in the
1424 replacement are dominates by their defs. */
1427 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1429 if (BB_CLUSTER (bb1
) != NULL
)
1430 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1432 if (BB_CLUSTER (bb2
) != NULL
)
1433 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1435 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1436 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1439 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1442 find_clusters_1 (same_succ
*same_succ
)
1444 basic_block bb1
, bb2
;
1446 bitmap_iterator bi
, bj
;
1448 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1450 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1452 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1454 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1455 phi-nodes in bb1 and bb2, with the same alternatives for the same
1457 if (bb_has_non_vop_phi (bb1
) || bb_has_eh_pred (bb1
))
1461 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1463 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1465 if (bb_has_non_vop_phi (bb2
) || bb_has_eh_pred (bb2
))
1468 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1471 /* Limit quadratic behavior. */
1473 if (nr_comparisons
> max_comparisons
)
1476 /* This is a conservative dependency check. We could test more
1477 precise for allowed replacement direction. */
1478 if (!deps_ok_for_redirect (bb1
, bb2
))
1481 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1484 find_duplicate (same_succ
, bb1
, bb2
);
1489 /* Find clusters of bbs which can be merged. */
1492 find_clusters (void)
1496 while (!worklist
.is_empty ())
1498 same
= worklist
.pop ();
1499 same
->in_worklist
= false;
1500 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1502 fprintf (dump_file
, "processing worklist entry\n");
1503 same_succ_print (dump_file
, same
);
1505 find_clusters_1 (same
);
1509 /* Returns the vop phi of BB, if any. */
1512 vop_phi (basic_block bb
)
1516 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1519 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1526 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1529 replace_block_by (basic_block bb1
, basic_block bb2
)
1537 bb2_phi
= vop_phi (bb2
);
1539 /* Mark the basic block as deleted. */
1540 mark_basic_block_deleted (bb1
);
1542 /* Redirect the incoming edges of bb1 to bb2. */
1543 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1545 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1546 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1547 gcc_assert (pred_edge
!= NULL
);
1549 if (bb2_phi
== NULL
)
1552 /* The phi might have run out of capacity when the redirect added an
1553 argument, which means it could have been replaced. Refresh it. */
1554 bb2_phi
= vop_phi (bb2
);
1556 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1557 pred_edge
, UNKNOWN_LOCATION
);
1560 bb2
->frequency
+= bb1
->frequency
;
1561 if (bb2
->frequency
> BB_FREQ_MAX
)
1562 bb2
->frequency
= BB_FREQ_MAX
;
1564 bb2
->count
+= bb1
->count
;
1566 /* Merge the outgoing edge counts from bb1 onto bb2. */
1567 gcov_type out_sum
= 0;
1568 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1570 e2
= find_edge (bb2
, e1
->dest
);
1572 e2
->count
+= e1
->count
;
1573 out_sum
+= e2
->count
;
1575 /* Recompute the edge probabilities from the new merged edge count.
1576 Use the sum of the new merged edge counts computed above instead
1577 of bb2's merged count, in case there are profile count insanities
1578 making the bb count inconsistent with the edge weights. */
1579 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1581 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1584 /* Move over any user labels from bb1 after the bb2 labels. */
1585 gimple_stmt_iterator gsi1
= gsi_start_bb (bb1
);
1586 if (!gsi_end_p (gsi1
) && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1588 gimple_stmt_iterator gsi2
= gsi_after_labels (bb2
);
1589 while (!gsi_end_p (gsi1
)
1590 && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1592 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi1
)));
1593 gcc_assert (!DECL_NONLOCAL (label
) && !FORCED_LABEL (label
));
1594 if (DECL_ARTIFICIAL (label
))
1597 gsi_move_before (&gsi1
, &gsi2
);
1601 /* Clear range info from all stmts in BB2 -- this transformation
1602 could make them out of date. */
1603 reset_flow_sensitive_info_in_bb (bb2
);
1605 /* Do updates that use bb1, before deleting bb1. */
1606 release_last_vdef (bb1
);
1607 same_succ_flush_bb (bb1
);
1609 delete_basic_block (bb1
);
1612 /* Bbs for which update_debug_stmt need to be called. */
1614 static bitmap update_bbs
;
1616 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1617 number of bbs removed. */
1620 apply_clusters (void)
1622 basic_block bb1
, bb2
;
1626 int nr_bbs_removed
= 0;
1628 for (i
= 0; i
< all_clusters
.length (); ++i
)
1630 c
= all_clusters
[i
];
1635 bitmap_set_bit (update_bbs
, bb2
->index
);
1637 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1638 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1640 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1641 bitmap_clear_bit (update_bbs
, bb1
->index
);
1643 replace_block_by (bb1
, bb2
);
1648 return nr_bbs_removed
;
1651 /* Resets debug statement STMT if it has uses that are not dominated by their
1655 update_debug_stmt (gimple
*stmt
)
1657 use_operand_p use_p
;
1661 if (!gimple_debug_bind_p (stmt
))
1664 bbuse
= gimple_bb (stmt
);
1665 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1667 tree name
= USE_FROM_PTR (use_p
);
1668 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1669 basic_block bbdef
= gimple_bb (def_stmt
);
1670 if (bbdef
== NULL
|| bbuse
== bbdef
1671 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1674 gimple_debug_bind_reset_value (stmt
);
1680 /* Resets all debug statements that have uses that are not
1681 dominated by their defs. */
1684 update_debug_stmts (void)
1690 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1693 gimple_stmt_iterator gsi
;
1695 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1696 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1698 stmt
= gsi_stmt (gsi
);
1699 if (!is_gimple_debug (stmt
))
1701 update_debug_stmt (stmt
);
1706 /* Runs tail merge optimization. */
1709 tail_merge_optimize (unsigned int todo
)
1711 int nr_bbs_removed_total
= 0;
1713 bool loop_entered
= false;
1714 int iteration_nr
= 0;
1715 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1717 if (!flag_tree_tail_merge
1718 || max_iterations
== 0)
1721 timevar_push (TV_TREE_TAIL_MERGE
);
1723 if (!dom_info_available_p (CDI_DOMINATORS
))
1725 /* PRE can leave us with unreachable blocks, remove them now. */
1726 delete_unreachable_blocks ();
1727 calculate_dominance_info (CDI_DOMINATORS
);
1731 while (!worklist
.is_empty ())
1735 loop_entered
= true;
1736 alloc_cluster_vectors ();
1737 update_bbs
= BITMAP_ALLOC (NULL
);
1740 reset_cluster_vectors ();
1743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1744 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1747 gcc_assert (worklist
.is_empty ());
1748 if (all_clusters
.is_empty ())
1751 nr_bbs_removed
= apply_clusters ();
1752 nr_bbs_removed_total
+= nr_bbs_removed
;
1753 if (nr_bbs_removed
== 0)
1756 free_dominance_info (CDI_DOMINATORS
);
1758 if (iteration_nr
== max_iterations
)
1761 calculate_dominance_info (CDI_DOMINATORS
);
1765 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1766 fprintf (dump_file
, "htab collision / search: %f\n",
1767 same_succ_htab
->collisions ());
1769 if (nr_bbs_removed_total
> 0)
1771 if (MAY_HAVE_DEBUG_STMTS
)
1773 calculate_dominance_info (CDI_DOMINATORS
);
1774 update_debug_stmts ();
1777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1779 fprintf (dump_file
, "Before TODOs.\n");
1780 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1783 mark_virtual_operands_for_renaming (cfun
);
1789 delete_cluster_vectors ();
1790 BITMAP_FREE (update_bbs
);
1793 timevar_pop (TV_TREE_TAIL_MERGE
);