1 /* Tail merging for gimple.
2 Copyright (C) 2011, 2012 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.
181 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
185 #include "coretypes.h"
189 #include "basic-block.h"
191 #include "function.h"
192 #include "tree-flow.h"
194 #include "tree-ssa-alias.h"
197 #include "gimple-pretty-print.h"
198 #include "tree-ssa-sccvn.h"
199 #include "tree-dump.h"
201 /* ??? This currently runs as part of tree-ssa-pre. Why is this not
202 a stand-alone GIMPLE pass? */
203 #include "tree-pass.h"
205 /* Describes a group of bbs with the same successors. The successor bbs are
206 cached in succs, and the successor edge flags are cached in succ_flags.
207 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
208 it's marked in inverse.
209 Additionally, the hash value for the struct is cached in hashval, and
210 in_worklist indicates whether it's currently part of worklist. */
214 /* The bbs that have the same successor bbs. */
216 /* The successor bbs. */
218 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
221 /* The edge flags for each of the successor bbs. */
222 VEC (int, heap
) *succ_flags
;
223 /* Indicates whether the struct is currently in the worklist. */
225 /* The hash value of the struct. */
228 typedef struct same_succ_def
*same_succ
;
229 typedef const struct same_succ_def
*const_same_succ
;
231 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
233 struct bb_cluster_def
235 /* The bbs in the cluster. */
237 /* The preds of the bbs in the cluster. */
239 /* Index in all_clusters vector. */
241 /* The bb to replace the cluster with. */
244 typedef struct bb_cluster_def
*bb_cluster
;
245 typedef const struct bb_cluster_def
*const_bb_cluster
;
251 /* The number of non-debug statements in the bb. */
253 /* The same_succ that this bb is a member of. */
254 same_succ bb_same_succ
;
255 /* The cluster that this bb is a member of. */
257 /* The vop state at the exit of a bb. This is shortlived data, used to
258 communicate data between update_block_by and update_vuses. */
260 /* The bb that either contains or is dominated by the dependencies of the
265 /* Macros to access the fields of struct aux_bb_info. */
267 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
268 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
269 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
270 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
271 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
273 /* Returns true if the only effect a statement STMT has, is to define locally
277 stmt_local_def (gimple stmt
)
279 basic_block bb
, def_bb
;
280 imm_use_iterator iter
;
285 if (gimple_has_side_effects (stmt
))
288 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
292 val
= DEF_FROM_PTR (def_p
);
293 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
296 def_bb
= gimple_bb (stmt
);
298 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
300 if (is_gimple_debug (USE_STMT (use_p
)))
302 bb
= gimple_bb (USE_STMT (use_p
));
306 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
307 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
316 /* Let GSI skip forwards over local defs. */
319 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
325 if (gsi_end_p (*gsi
))
327 stmt
= gsi_stmt (*gsi
);
328 if (!stmt_local_def (stmt
))
330 gsi_next_nondebug (gsi
);
334 /* VAL1 and VAL2 are either:
335 - uses in BB1 and BB2, or
336 - phi alternatives for BB1 and BB2.
337 Return true if the uses have the same gvn value. */
340 gvn_uses_equal (tree val1
, tree val2
)
342 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
347 if (vn_valueize (val1
) != vn_valueize (val2
))
350 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
351 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
354 /* Prints E to FILE. */
357 same_succ_print (FILE *file
, const same_succ e
)
360 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
361 bitmap_print (file
, e
->succs
, "succs:", "\n");
362 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
363 fprintf (file
, "flags:");
364 for (i
= 0; i
< VEC_length (int, e
->succ_flags
); ++i
)
365 fprintf (file
, " %x", VEC_index (int, e
->succ_flags
, i
));
366 fprintf (file
, "\n");
369 /* Prints same_succ VE to VFILE. */
372 same_succ_print_traverse (void **ve
, void *vfile
)
374 const same_succ e
= *((const same_succ
*)ve
);
375 FILE *file
= ((FILE*)vfile
);
376 same_succ_print (file
, e
);
380 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
383 update_dep_bb (basic_block use_bb
, tree val
)
388 if (TREE_CODE (val
) != SSA_NAME
)
391 /* Skip use of global def. */
392 if (SSA_NAME_IS_DEFAULT_DEF (val
))
395 /* Skip use of local def. */
396 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
397 if (dep_bb
== use_bb
)
400 if (BB_DEP_BB (use_bb
) == NULL
401 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
402 BB_DEP_BB (use_bb
) = dep_bb
;
405 /* Update BB_DEP_BB, given the dependencies in STMT. */
408 stmt_update_dep_bb (gimple stmt
)
413 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
414 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
417 /* Calculates hash value for same_succ VE. */
420 same_succ_hash (const void *ve
)
422 const_same_succ e
= (const_same_succ
)ve
;
423 hashval_t hashval
= bitmap_hash (e
->succs
);
426 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
427 basic_block bb
= BASIC_BLOCK (first
);
429 gimple_stmt_iterator gsi
;
435 for (gsi
= gsi_start_nondebug_bb (bb
);
436 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
438 stmt
= gsi_stmt (gsi
);
439 stmt_update_dep_bb (stmt
);
440 if (stmt_local_def (stmt
))
444 hashval
= iterative_hash_hashval_t (gimple_code (stmt
), hashval
);
445 if (is_gimple_assign (stmt
))
446 hashval
= iterative_hash_hashval_t (gimple_assign_rhs_code (stmt
),
448 if (!is_gimple_call (stmt
))
450 if (gimple_call_internal_p (stmt
))
451 hashval
= iterative_hash_hashval_t
452 ((hashval_t
) gimple_call_internal_fn (stmt
), hashval
);
454 hashval
= iterative_hash_expr (gimple_call_fn (stmt
), hashval
);
455 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
457 arg
= gimple_call_arg (stmt
, i
);
458 arg
= vn_valueize (arg
);
459 hashval
= iterative_hash_expr (arg
, hashval
);
463 hashval
= iterative_hash_hashval_t (size
, hashval
);
466 for (i
= 0; i
< VEC_length (int, e
->succ_flags
); ++i
)
468 flags
= VEC_index (int, e
->succ_flags
, i
);
469 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
470 hashval
= iterative_hash_hashval_t (flags
, hashval
);
473 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
475 int n
= find_edge (bb
, BASIC_BLOCK (s
))->dest_idx
;
476 for (gsi
= gsi_start_phis (BASIC_BLOCK (s
)); !gsi_end_p (gsi
);
479 gimple phi
= gsi_stmt (gsi
);
480 tree lhs
= gimple_phi_result (phi
);
481 tree val
= gimple_phi_arg_def (phi
, n
);
483 if (!is_gimple_reg (lhs
))
485 update_dep_bb (bb
, val
);
492 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
493 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
494 the other edge flags. */
497 inverse_flags (const_same_succ e1
, const_same_succ e2
)
499 int f1a
, f1b
, f2a
, f2b
;
500 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
502 if (VEC_length (int, e1
->succ_flags
) != 2)
505 f1a
= VEC_index (int, e1
->succ_flags
, 0);
506 f1b
= VEC_index (int, e1
->succ_flags
, 1);
507 f2a
= VEC_index (int, e2
->succ_flags
, 0);
508 f2b
= VEC_index (int, e2
->succ_flags
, 1);
510 if (f1a
== f2a
&& f1b
== f2b
)
513 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
516 /* Compares SAME_SUCCs VE1 and VE2. */
519 same_succ_equal (const void *ve1
, const void *ve2
)
521 const_same_succ e1
= (const_same_succ
)ve1
;
522 const_same_succ e2
= (const_same_succ
)ve2
;
523 unsigned int i
, first1
, first2
;
524 gimple_stmt_iterator gsi1
, gsi2
;
526 basic_block bb1
, bb2
;
528 if (e1
->hashval
!= e2
->hashval
)
531 if (VEC_length (int, e1
->succ_flags
) != VEC_length (int, e2
->succ_flags
))
534 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
537 if (!inverse_flags (e1
, e2
))
539 for (i
= 0; i
< VEC_length (int, e1
->succ_flags
); ++i
)
540 if (VEC_index (int, e1
->succ_flags
, i
)
541 != VEC_index (int, e1
->succ_flags
, i
))
545 first1
= bitmap_first_set_bit (e1
->bbs
);
546 first2
= bitmap_first_set_bit (e2
->bbs
);
548 bb1
= BASIC_BLOCK (first1
);
549 bb2
= BASIC_BLOCK (first2
);
551 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
554 gsi1
= gsi_start_nondebug_bb (bb1
);
555 gsi2
= gsi_start_nondebug_bb (bb2
);
556 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
557 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
558 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
560 s1
= gsi_stmt (gsi1
);
561 s2
= gsi_stmt (gsi2
);
562 if (gimple_code (s1
) != gimple_code (s2
))
564 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
566 gsi_next_nondebug (&gsi1
);
567 gsi_next_nondebug (&gsi2
);
568 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
569 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
575 /* Alloc and init a new SAME_SUCC. */
578 same_succ_alloc (void)
580 same_succ same
= XNEW (struct same_succ_def
);
582 same
->bbs
= BITMAP_ALLOC (NULL
);
583 same
->succs
= BITMAP_ALLOC (NULL
);
584 same
->inverse
= BITMAP_ALLOC (NULL
);
585 same
->succ_flags
= VEC_alloc (int, heap
, 10);
586 same
->in_worklist
= false;
591 /* Delete same_succ VE. */
594 same_succ_delete (void *ve
)
596 same_succ e
= (same_succ
)ve
;
598 BITMAP_FREE (e
->bbs
);
599 BITMAP_FREE (e
->succs
);
600 BITMAP_FREE (e
->inverse
);
601 VEC_free (int, heap
, e
->succ_flags
);
606 /* Reset same_succ SAME. */
609 same_succ_reset (same_succ same
)
611 bitmap_clear (same
->bbs
);
612 bitmap_clear (same
->succs
);
613 bitmap_clear (same
->inverse
);
614 VEC_truncate (int, same
->succ_flags
, 0);
617 /* Hash table with all same_succ entries. */
619 static htab_t same_succ_htab
;
621 /* Array that is used to store the edge flags for a successor. */
623 static int *same_succ_edge_flags
;
625 /* Bitmap that is used to mark bbs that are recently deleted. */
627 static bitmap deleted_bbs
;
629 /* Bitmap that is used to mark predecessors of bbs that are
632 static bitmap deleted_bb_preds
;
634 /* Prints same_succ_htab to stderr. */
636 extern void debug_same_succ (void);
638 debug_same_succ ( void)
640 htab_traverse (same_succ_htab
, same_succ_print_traverse
, stderr
);
643 DEF_VEC_P (same_succ
);
644 DEF_VEC_ALLOC_P (same_succ
, heap
);
646 /* Vector of bbs to process. */
648 static VEC (same_succ
, heap
) *worklist
;
650 /* Prints worklist to FILE. */
653 print_worklist (FILE *file
)
656 for (i
= 0; i
< VEC_length (same_succ
, worklist
); ++i
)
657 same_succ_print (file
, VEC_index (same_succ
, worklist
, i
));
660 /* Adds SAME to worklist. */
663 add_to_worklist (same_succ same
)
665 if (same
->in_worklist
)
668 if (bitmap_count_bits (same
->bbs
) < 2)
671 same
->in_worklist
= true;
672 VEC_safe_push (same_succ
, heap
, worklist
, same
);
675 /* Add BB to same_succ_htab. */
678 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
682 same_succ same
= *same_p
;
689 bitmap_set_bit (same
->bbs
, bb
->index
);
690 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
692 int index
= e
->dest
->index
;
693 bitmap_set_bit (same
->succs
, index
);
694 same_succ_edge_flags
[index
] = e
->flags
;
696 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
697 VEC_safe_push (int, heap
, same
->succ_flags
, same_succ_edge_flags
[j
]);
699 same
->hashval
= same_succ_hash (same
);
701 slot
= (same_succ
*) htab_find_slot_with_hash (same_succ_htab
, same
,
702 same
->hashval
, INSERT
);
706 BB_SAME_SUCC (bb
) = same
;
707 add_to_worklist (same
);
712 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
713 BB_SAME_SUCC (bb
) = *slot
;
714 add_to_worklist (*slot
);
715 if (inverse_flags (same
, *slot
))
716 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
717 same_succ_reset (same
);
721 /* Find bbs with same successors. */
724 find_same_succ (void)
726 same_succ same
= same_succ_alloc ();
731 find_same_succ_bb (bb
, &same
);
733 same
= same_succ_alloc ();
736 same_succ_delete (same
);
739 /* Initializes worklist administration. */
744 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
746 = htab_create (n_basic_blocks
, same_succ_hash
, same_succ_equal
,
748 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block
);
749 deleted_bbs
= BITMAP_ALLOC (NULL
);
750 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
751 worklist
= VEC_alloc (same_succ
, heap
, n_basic_blocks
);
754 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, "initial worklist:\n");
757 print_worklist (dump_file
);
761 /* Deletes worklist administration. */
764 delete_worklist (void)
766 free_aux_for_blocks ();
767 htab_delete (same_succ_htab
);
768 same_succ_htab
= NULL
;
769 XDELETEVEC (same_succ_edge_flags
);
770 same_succ_edge_flags
= NULL
;
771 BITMAP_FREE (deleted_bbs
);
772 BITMAP_FREE (deleted_bb_preds
);
773 VEC_free (same_succ
, heap
, worklist
);
776 /* Mark BB as deleted, and mark its predecessors. */
779 mark_basic_block_deleted (basic_block bb
)
784 bitmap_set_bit (deleted_bbs
, bb
->index
);
786 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
787 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
790 /* Removes BB from its corresponding same_succ. */
793 same_succ_flush_bb (basic_block bb
)
795 same_succ same
= BB_SAME_SUCC (bb
);
796 BB_SAME_SUCC (bb
) = NULL
;
797 if (bitmap_single_bit_set_p (same
->bbs
))
798 htab_remove_elt_with_hash (same_succ_htab
, same
, same
->hashval
);
800 bitmap_clear_bit (same
->bbs
, bb
->index
);
803 /* Removes all bbs in BBS from their corresponding same_succ. */
806 same_succ_flush_bbs (bitmap bbs
)
811 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
812 same_succ_flush_bb (BASIC_BLOCK (i
));
815 /* For deleted_bb_preds, find bbs with same successors. */
818 update_worklist (void)
825 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
826 bitmap_clear (deleted_bbs
);
828 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
829 same_succ_flush_bbs (deleted_bb_preds
);
831 same
= same_succ_alloc ();
832 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
834 bb
= BASIC_BLOCK (i
);
835 gcc_assert (bb
!= NULL
);
836 find_same_succ_bb (bb
, &same
);
838 same
= same_succ_alloc ();
840 same_succ_delete (same
);
841 bitmap_clear (deleted_bb_preds
);
844 /* Prints cluster C to FILE. */
847 print_cluster (FILE *file
, bb_cluster c
)
851 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
852 bitmap_print (file
, c
->preds
, "preds:", "\n");
855 /* Prints cluster C to stderr. */
857 extern void debug_cluster (bb_cluster
);
859 debug_cluster (bb_cluster c
)
861 print_cluster (stderr
, c
);
864 /* Update C->rep_bb, given that BB is added to the cluster. */
867 update_rep_bb (bb_cluster c
, basic_block bb
)
870 if (c
->rep_bb
== NULL
)
876 /* Current needs no deps, keep it. */
877 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
880 /* Bb needs no deps, change rep_bb. */
881 if (BB_DEP_BB (bb
) == NULL
)
887 /* Bb needs last deps earlier than current, change rep_bb. A potential
888 problem with this, is that the first deps might also be earlier, which
889 would mean we prefer longer lifetimes for the deps. To be able to check
890 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
891 BB_DEP_BB, which is really BB_LAST_DEP_BB.
892 The benefit of choosing the bb with last deps earlier, is that it can
893 potentially be used as replacement for more bbs. */
894 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
898 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
901 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
906 bitmap_set_bit (c
->bbs
, bb
->index
);
908 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
909 bitmap_set_bit (c
->preds
, e
->src
->index
);
911 update_rep_bb (c
, bb
);
914 /* Allocate and init new cluster. */
920 c
= XCNEW (struct bb_cluster_def
);
921 c
->bbs
= BITMAP_ALLOC (NULL
);
922 c
->preds
= BITMAP_ALLOC (NULL
);
927 /* Delete clusters. */
930 delete_cluster (bb_cluster c
)
934 BITMAP_FREE (c
->bbs
);
935 BITMAP_FREE (c
->preds
);
939 DEF_VEC_P (bb_cluster
);
940 DEF_VEC_ALLOC_P (bb_cluster
, heap
);
942 /* Array that contains all clusters. */
944 static VEC (bb_cluster
, heap
) *all_clusters
;
946 /* Allocate all cluster vectors. */
949 alloc_cluster_vectors (void)
951 all_clusters
= VEC_alloc (bb_cluster
, heap
, n_basic_blocks
);
954 /* Reset all cluster vectors. */
957 reset_cluster_vectors (void)
961 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
962 delete_cluster (VEC_index (bb_cluster
, all_clusters
, i
));
963 VEC_truncate (bb_cluster
, all_clusters
, 0);
965 BB_CLUSTER (bb
) = NULL
;
968 /* Delete all cluster vectors. */
971 delete_cluster_vectors (void)
974 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
975 delete_cluster (VEC_index (bb_cluster
, all_clusters
, i
));
976 VEC_free (bb_cluster
, heap
, all_clusters
);
979 /* Merge cluster C2 into C1. */
982 merge_clusters (bb_cluster c1
, bb_cluster c2
)
984 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
985 bitmap_ior_into (c1
->preds
, c2
->preds
);
988 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
989 all_clusters, or merge c with existing cluster. */
992 set_cluster (basic_block bb1
, basic_block bb2
)
994 basic_block merge_bb
, other_bb
;
995 bb_cluster merge
, old
, c
;
997 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1000 add_bb_to_cluster (c
, bb1
);
1001 add_bb_to_cluster (c
, bb2
);
1002 BB_CLUSTER (bb1
) = c
;
1003 BB_CLUSTER (bb2
) = c
;
1004 c
->index
= VEC_length (bb_cluster
, all_clusters
);
1005 VEC_safe_push (bb_cluster
, heap
, all_clusters
, c
);
1007 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1009 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1010 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1011 merge
= BB_CLUSTER (merge_bb
);
1012 add_bb_to_cluster (merge
, other_bb
);
1013 BB_CLUSTER (other_bb
) = merge
;
1015 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1020 old
= BB_CLUSTER (bb2
);
1021 merge
= BB_CLUSTER (bb1
);
1022 merge_clusters (merge
, old
);
1023 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1024 BB_CLUSTER (BASIC_BLOCK (i
)) = merge
;
1025 VEC_replace (bb_cluster
, all_clusters
, old
->index
, NULL
);
1026 update_rep_bb (merge
, old
->rep_bb
);
1027 delete_cluster (old
);
1033 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1034 gimple_bb (s2) are members of SAME_SUCC. */
1037 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1041 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1043 bool equal
, inv_cond
;
1044 enum tree_code code1
, code2
;
1046 if (gimple_code (s1
) != gimple_code (s2
))
1049 switch (gimple_code (s1
))
1052 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1054 if (!gimple_call_same_target_p (s1
, s2
))
1057 /* Eventually, we'll significantly complicate the CFG by adding
1058 back edges to properly model the effects of transaction restart.
1059 For the bulk of optimization this does not matter, but what we
1060 cannot recover from is tail merging blocks between two separate
1061 transactions. Avoid that by making commit not match. */
1062 if (gimple_call_builtin_p (s1
, BUILT_IN_TM_COMMIT
))
1066 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1068 t1
= gimple_call_arg (s1
, i
);
1069 t2
= gimple_call_arg (s2
, i
);
1070 if (operand_equal_p (t1
, t2
, 0))
1072 if (gvn_uses_equal (t1
, t2
))
1080 lhs1
= gimple_get_lhs (s1
);
1081 lhs2
= gimple_get_lhs (s2
);
1082 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1084 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1086 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1087 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1088 return operand_equal_p (lhs1
, lhs2
, 0);
1091 lhs1
= gimple_get_lhs (s1
);
1092 lhs2
= gimple_get_lhs (s2
);
1093 if (gimple_vdef (s1
))
1095 if (vn_valueize (gimple_vdef (s1
)) != vn_valueize (gimple_vdef (s2
)))
1097 if (TREE_CODE (lhs1
) != SSA_NAME
1098 && TREE_CODE (lhs2
) != SSA_NAME
)
1101 return (TREE_CODE (lhs1
) == SSA_NAME
1102 && TREE_CODE (lhs2
) == SSA_NAME
1103 && vn_valueize (lhs1
) == vn_valueize (lhs2
));
1106 t1
= gimple_cond_lhs (s1
);
1107 t2
= gimple_cond_lhs (s2
);
1108 if (!operand_equal_p (t1
, t2
, 0)
1109 && !gvn_uses_equal (t1
, t2
))
1112 t1
= gimple_cond_rhs (s1
);
1113 t2
= gimple_cond_rhs (s2
);
1114 if (!operand_equal_p (t1
, t2
, 0)
1115 && !gvn_uses_equal (t1
, t2
))
1118 code1
= gimple_expr_code (s1
);
1119 code2
= gimple_expr_code (s2
);
1120 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1121 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1125 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1126 code2
= invert_tree_comparison (code2
, honor_nans
);
1128 return code1
== code2
;
1135 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1136 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1137 processed statements. */
1140 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1148 if (gsi_end_p (*gsi
))
1150 stmt
= gsi_stmt (*gsi
);
1152 lvuse
= gimple_vuse (stmt
);
1153 if (lvuse
!= NULL_TREE
)
1156 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1157 *vuse_escaped
= true;
1160 if (!stmt_local_def (stmt
))
1162 gsi_prev_nondebug (gsi
);
1166 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1170 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1172 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1173 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1174 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1175 bool vuse_escaped
= false;
1177 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1178 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1180 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1182 if (!gimple_equal_p (same_succ
, gsi_stmt (gsi1
), gsi_stmt (gsi2
)))
1185 gsi_prev_nondebug (&gsi1
);
1186 gsi_prev_nondebug (&gsi2
);
1187 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1188 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1191 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1194 /* If the incoming vuses are not the same, and the vuse escaped into an
1195 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1196 which potentially means the semantics of one of the blocks will be changed.
1197 TODO: make this check more precise. */
1198 if (vuse_escaped
&& vuse1
!= vuse2
)
1202 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1203 bb1
->index
, bb2
->index
);
1205 set_cluster (bb1
, bb2
);
1208 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1212 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1214 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1215 gimple_stmt_iterator gsi
;
1217 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1219 gimple phi
= gsi_stmt (gsi
);
1220 tree lhs
= gimple_phi_result (phi
);
1221 tree val1
= gimple_phi_arg_def (phi
, n1
);
1222 tree val2
= gimple_phi_arg_def (phi
, n2
);
1224 if (!is_gimple_reg (lhs
))
1227 if (operand_equal_for_phi_arg_p (val1
, val2
))
1229 if (gvn_uses_equal (val1
, val2
))
1238 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1239 phi alternatives for BB1 and BB2 are equal. */
1242 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1249 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1251 succ
= BASIC_BLOCK (s
);
1252 e1
= find_edge (bb1
, succ
);
1253 e2
= find_edge (bb2
, succ
);
1254 if (e1
->flags
& EDGE_COMPLEX
1255 || e2
->flags
& EDGE_COMPLEX
)
1258 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1260 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1267 /* Return true if BB has non-vop phis. */
1270 bb_has_non_vop_phi (basic_block bb
)
1272 gimple_seq phis
= phi_nodes (bb
);
1278 if (!gimple_seq_singleton_p (phis
))
1281 phi
= gimple_seq_first_stmt (phis
);
1282 return is_gimple_reg (gimple_phi_result (phi
));
1285 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1286 invariant that uses in FROM are dominates by their defs. */
1289 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1291 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1294 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1299 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1300 bitmap_set_bit (from_preds
, e
->src
->index
);
1301 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1302 BITMAP_FREE (from_preds
);
1304 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1307 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1308 replacement bb) and vice versa maintains the invariant that uses in the
1309 replacement are dominates by their defs. */
1312 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1314 if (BB_CLUSTER (bb1
) != NULL
)
1315 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1317 if (BB_CLUSTER (bb2
) != NULL
)
1318 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1320 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1321 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1324 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1327 find_clusters_1 (same_succ same_succ
)
1329 basic_block bb1
, bb2
;
1331 bitmap_iterator bi
, bj
;
1333 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1335 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1337 bb1
= BASIC_BLOCK (i
);
1339 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1340 phi-nodes in bb1 and bb2, with the same alternatives for the same
1342 if (bb_has_non_vop_phi (bb1
))
1346 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1348 bb2
= BASIC_BLOCK (j
);
1350 if (bb_has_non_vop_phi (bb2
))
1353 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1356 /* Limit quadratic behaviour. */
1358 if (nr_comparisons
> max_comparisons
)
1361 /* This is a conservative dependency check. We could test more
1362 precise for allowed replacement direction. */
1363 if (!deps_ok_for_redirect (bb1
, bb2
))
1366 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1369 find_duplicate (same_succ
, bb1
, bb2
);
1374 /* Find clusters of bbs which can be merged. */
1377 find_clusters (void)
1381 while (!VEC_empty (same_succ
, worklist
))
1383 same
= VEC_pop (same_succ
, worklist
);
1384 same
->in_worklist
= false;
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1387 fprintf (dump_file
, "processing worklist entry\n");
1388 same_succ_print (dump_file
, same
);
1390 find_clusters_1 (same
);
1394 /* Returns the vop phi of BB, if any. */
1397 vop_phi (basic_block bb
)
1400 gimple_stmt_iterator gsi
;
1401 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1403 stmt
= gsi_stmt (gsi
);
1404 if (is_gimple_reg (gimple_phi_result (stmt
)))
1411 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1414 replace_block_by (basic_block bb1
, basic_block bb2
)
1420 bb2_phi
= vop_phi (bb2
);
1422 /* Mark the basic block as deleted. */
1423 mark_basic_block_deleted (bb1
);
1425 /* Redirect the incoming edges of bb1 to bb2. */
1426 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1428 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1429 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1430 gcc_assert (pred_edge
!= NULL
);
1432 if (bb2_phi
== NULL
)
1435 /* The phi might have run out of capacity when the redirect added an
1436 argument, which means it could have been replaced. Refresh it. */
1437 bb2_phi
= vop_phi (bb2
);
1439 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1440 pred_edge
, UNKNOWN_LOCATION
);
1443 bb2
->frequency
+= bb1
->frequency
;
1444 if (bb2
->frequency
> BB_FREQ_MAX
)
1445 bb2
->frequency
= BB_FREQ_MAX
;
1448 /* Do updates that use bb1, before deleting bb1. */
1449 same_succ_flush_bb (bb1
);
1451 delete_basic_block (bb1
);
1454 /* Bbs for which update_debug_stmt need to be called. */
1456 static bitmap update_bbs
;
1458 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1459 number of bbs removed. */
1462 apply_clusters (void)
1464 basic_block bb1
, bb2
;
1468 int nr_bbs_removed
= 0;
1470 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
1472 c
= VEC_index (bb_cluster
, all_clusters
, i
);
1477 bitmap_set_bit (update_bbs
, bb2
->index
);
1479 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1480 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1482 bb1
= BASIC_BLOCK (j
);
1483 bitmap_clear_bit (update_bbs
, bb1
->index
);
1485 replace_block_by (bb1
, bb2
);
1490 return nr_bbs_removed
;
1493 /* Resets debug statement STMT if it has uses that are not dominated by their
1497 update_debug_stmt (gimple stmt
)
1499 use_operand_p use_p
;
1501 basic_block bbdef
, bbuse
;
1505 if (!gimple_debug_bind_p (stmt
))
1508 bbuse
= gimple_bb (stmt
);
1509 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1511 name
= USE_FROM_PTR (use_p
);
1512 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1514 def_stmt
= SSA_NAME_DEF_STMT (name
);
1515 gcc_assert (def_stmt
!= NULL
);
1517 bbdef
= gimple_bb (def_stmt
);
1518 if (bbdef
== NULL
|| bbuse
== bbdef
1519 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1522 gimple_debug_bind_reset_value (stmt
);
1527 /* Resets all debug statements that have uses that are not
1528 dominated by their defs. */
1531 update_debug_stmts (void)
1537 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1540 gimple_stmt_iterator gsi
;
1542 bb
= BASIC_BLOCK (i
);
1543 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1545 stmt
= gsi_stmt (gsi
);
1546 if (!is_gimple_debug (stmt
))
1548 update_debug_stmt (stmt
);
1553 /* Runs tail merge optimization. */
1556 tail_merge_optimize (unsigned int todo
)
1558 int nr_bbs_removed_total
= 0;
1560 bool loop_entered
= false;
1561 int iteration_nr
= 0;
1562 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1564 if (!flag_tree_tail_merge
|| max_iterations
== 0)
1567 timevar_push (TV_TREE_TAIL_MERGE
);
1569 calculate_dominance_info (CDI_DOMINATORS
);
1572 while (!VEC_empty (same_succ
, worklist
))
1576 loop_entered
= true;
1577 alloc_cluster_vectors ();
1578 update_bbs
= BITMAP_ALLOC (NULL
);
1581 reset_cluster_vectors ();
1584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1585 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1588 gcc_assert (VEC_empty (same_succ
, worklist
));
1589 if (VEC_empty (bb_cluster
, all_clusters
))
1592 nr_bbs_removed
= apply_clusters ();
1593 nr_bbs_removed_total
+= nr_bbs_removed
;
1594 if (nr_bbs_removed
== 0)
1597 free_dominance_info (CDI_DOMINATORS
);
1599 if (iteration_nr
== max_iterations
)
1602 calculate_dominance_info (CDI_DOMINATORS
);
1606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1607 fprintf (dump_file
, "htab collision / search: %f\n",
1608 htab_collisions (same_succ_htab
));
1610 if (nr_bbs_removed_total
> 0)
1612 if (MAY_HAVE_DEBUG_STMTS
)
1614 calculate_dominance_info (CDI_DOMINATORS
);
1615 update_debug_stmts ();
1618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1620 fprintf (dump_file
, "Before TODOs.\n");
1621 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1624 todo
|= (TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow
);
1625 mark_virtual_operands_for_renaming (cfun
);
1631 delete_cluster_vectors ();
1632 BITMAP_FREE (update_bbs
);
1635 timevar_pop (TV_TREE_TAIL_MERGE
);