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 (virtual_operand_p (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 /* Release the last vdef in BB, either normal or phi result. */
818 release_last_vdef (basic_block bb
)
820 gimple_stmt_iterator i
;
822 for (i
= gsi_last_bb (bb
); !gsi_end_p (i
); gsi_prev_nondebug (&i
))
824 gimple stmt
= gsi_stmt (i
);
825 if (gimple_vdef (stmt
) == NULL_TREE
)
828 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
832 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
834 gimple phi
= gsi_stmt (i
);
835 tree res
= gimple_phi_result (phi
);
837 if (!virtual_operand_p (res
))
840 mark_virtual_phi_result_for_renaming (phi
);
846 /* For deleted_bb_preds, find bbs with same successors. */
849 update_worklist (void)
856 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
857 bitmap_clear (deleted_bbs
);
859 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
860 same_succ_flush_bbs (deleted_bb_preds
);
862 same
= same_succ_alloc ();
863 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
865 bb
= BASIC_BLOCK (i
);
866 gcc_assert (bb
!= NULL
);
867 find_same_succ_bb (bb
, &same
);
869 same
= same_succ_alloc ();
871 same_succ_delete (same
);
872 bitmap_clear (deleted_bb_preds
);
875 /* Prints cluster C to FILE. */
878 print_cluster (FILE *file
, bb_cluster c
)
882 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
883 bitmap_print (file
, c
->preds
, "preds:", "\n");
886 /* Prints cluster C to stderr. */
888 extern void debug_cluster (bb_cluster
);
890 debug_cluster (bb_cluster c
)
892 print_cluster (stderr
, c
);
895 /* Update C->rep_bb, given that BB is added to the cluster. */
898 update_rep_bb (bb_cluster c
, basic_block bb
)
901 if (c
->rep_bb
== NULL
)
907 /* Current needs no deps, keep it. */
908 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
911 /* Bb needs no deps, change rep_bb. */
912 if (BB_DEP_BB (bb
) == NULL
)
918 /* Bb needs last deps earlier than current, change rep_bb. A potential
919 problem with this, is that the first deps might also be earlier, which
920 would mean we prefer longer lifetimes for the deps. To be able to check
921 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
922 BB_DEP_BB, which is really BB_LAST_DEP_BB.
923 The benefit of choosing the bb with last deps earlier, is that it can
924 potentially be used as replacement for more bbs. */
925 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
929 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
932 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
937 bitmap_set_bit (c
->bbs
, bb
->index
);
939 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
940 bitmap_set_bit (c
->preds
, e
->src
->index
);
942 update_rep_bb (c
, bb
);
945 /* Allocate and init new cluster. */
951 c
= XCNEW (struct bb_cluster_def
);
952 c
->bbs
= BITMAP_ALLOC (NULL
);
953 c
->preds
= BITMAP_ALLOC (NULL
);
958 /* Delete clusters. */
961 delete_cluster (bb_cluster c
)
965 BITMAP_FREE (c
->bbs
);
966 BITMAP_FREE (c
->preds
);
970 DEF_VEC_P (bb_cluster
);
971 DEF_VEC_ALLOC_P (bb_cluster
, heap
);
973 /* Array that contains all clusters. */
975 static VEC (bb_cluster
, heap
) *all_clusters
;
977 /* Allocate all cluster vectors. */
980 alloc_cluster_vectors (void)
982 all_clusters
= VEC_alloc (bb_cluster
, heap
, n_basic_blocks
);
985 /* Reset all cluster vectors. */
988 reset_cluster_vectors (void)
992 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
993 delete_cluster (VEC_index (bb_cluster
, all_clusters
, i
));
994 VEC_truncate (bb_cluster
, all_clusters
, 0);
996 BB_CLUSTER (bb
) = NULL
;
999 /* Delete all cluster vectors. */
1002 delete_cluster_vectors (void)
1005 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
1006 delete_cluster (VEC_index (bb_cluster
, all_clusters
, i
));
1007 VEC_free (bb_cluster
, heap
, all_clusters
);
1010 /* Merge cluster C2 into C1. */
1013 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1015 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1016 bitmap_ior_into (c1
->preds
, c2
->preds
);
1019 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1020 all_clusters, or merge c with existing cluster. */
1023 set_cluster (basic_block bb1
, basic_block bb2
)
1025 basic_block merge_bb
, other_bb
;
1026 bb_cluster merge
, old
, c
;
1028 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1031 add_bb_to_cluster (c
, bb1
);
1032 add_bb_to_cluster (c
, bb2
);
1033 BB_CLUSTER (bb1
) = c
;
1034 BB_CLUSTER (bb2
) = c
;
1035 c
->index
= VEC_length (bb_cluster
, all_clusters
);
1036 VEC_safe_push (bb_cluster
, heap
, all_clusters
, c
);
1038 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1040 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1041 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1042 merge
= BB_CLUSTER (merge_bb
);
1043 add_bb_to_cluster (merge
, other_bb
);
1044 BB_CLUSTER (other_bb
) = merge
;
1046 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1051 old
= BB_CLUSTER (bb2
);
1052 merge
= BB_CLUSTER (bb1
);
1053 merge_clusters (merge
, old
);
1054 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1055 BB_CLUSTER (BASIC_BLOCK (i
)) = merge
;
1056 VEC_replace (bb_cluster
, all_clusters
, old
->index
, NULL
);
1057 update_rep_bb (merge
, old
->rep_bb
);
1058 delete_cluster (old
);
1064 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1065 gimple_bb (s2) are members of SAME_SUCC. */
1068 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1072 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1074 bool equal
, inv_cond
;
1075 enum tree_code code1
, code2
;
1077 if (gimple_code (s1
) != gimple_code (s2
))
1080 switch (gimple_code (s1
))
1083 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1085 if (!gimple_call_same_target_p (s1
, s2
))
1088 /* Eventually, we'll significantly complicate the CFG by adding
1089 back edges to properly model the effects of transaction restart.
1090 For the bulk of optimization this does not matter, but what we
1091 cannot recover from is tail merging blocks between two separate
1092 transactions. Avoid that by making commit not match. */
1093 if (gimple_call_builtin_p (s1
, BUILT_IN_TM_COMMIT
))
1097 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1099 t1
= gimple_call_arg (s1
, i
);
1100 t2
= gimple_call_arg (s2
, i
);
1101 if (operand_equal_p (t1
, t2
, 0))
1103 if (gvn_uses_equal (t1
, t2
))
1111 lhs1
= gimple_get_lhs (s1
);
1112 lhs2
= gimple_get_lhs (s2
);
1113 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1115 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1117 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1118 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1119 return operand_equal_p (lhs1
, lhs2
, 0);
1122 lhs1
= gimple_get_lhs (s1
);
1123 lhs2
= gimple_get_lhs (s2
);
1124 if (gimple_vdef (s1
))
1126 if (vn_valueize (gimple_vdef (s1
)) != vn_valueize (gimple_vdef (s2
)))
1128 if (TREE_CODE (lhs1
) != SSA_NAME
1129 && TREE_CODE (lhs2
) != SSA_NAME
)
1132 return (TREE_CODE (lhs1
) == SSA_NAME
1133 && TREE_CODE (lhs2
) == SSA_NAME
1134 && vn_valueize (lhs1
) == vn_valueize (lhs2
));
1137 t1
= gimple_cond_lhs (s1
);
1138 t2
= gimple_cond_lhs (s2
);
1139 if (!operand_equal_p (t1
, t2
, 0)
1140 && !gvn_uses_equal (t1
, t2
))
1143 t1
= gimple_cond_rhs (s1
);
1144 t2
= gimple_cond_rhs (s2
);
1145 if (!operand_equal_p (t1
, t2
, 0)
1146 && !gvn_uses_equal (t1
, t2
))
1149 code1
= gimple_expr_code (s1
);
1150 code2
= gimple_expr_code (s2
);
1151 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1152 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1156 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1157 code2
= invert_tree_comparison (code2
, honor_nans
);
1159 return code1
== code2
;
1166 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1167 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1168 processed statements. */
1171 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1179 if (gsi_end_p (*gsi
))
1181 stmt
= gsi_stmt (*gsi
);
1183 lvuse
= gimple_vuse (stmt
);
1184 if (lvuse
!= NULL_TREE
)
1187 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1188 *vuse_escaped
= true;
1191 if (!stmt_local_def (stmt
))
1193 gsi_prev_nondebug (gsi
);
1197 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1201 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1203 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1204 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1205 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1206 bool vuse_escaped
= false;
1208 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1209 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1211 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1213 if (!gimple_equal_p (same_succ
, gsi_stmt (gsi1
), gsi_stmt (gsi2
)))
1216 gsi_prev_nondebug (&gsi1
);
1217 gsi_prev_nondebug (&gsi2
);
1218 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1219 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1222 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1225 /* If the incoming vuses are not the same, and the vuse escaped into an
1226 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1227 which potentially means the semantics of one of the blocks will be changed.
1228 TODO: make this check more precise. */
1229 if (vuse_escaped
&& vuse1
!= vuse2
)
1233 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1234 bb1
->index
, bb2
->index
);
1236 set_cluster (bb1
, bb2
);
1239 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1243 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1245 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1246 gimple_stmt_iterator gsi
;
1248 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1250 gimple phi
= gsi_stmt (gsi
);
1251 tree lhs
= gimple_phi_result (phi
);
1252 tree val1
= gimple_phi_arg_def (phi
, n1
);
1253 tree val2
= gimple_phi_arg_def (phi
, n2
);
1255 if (virtual_operand_p (lhs
))
1258 if (operand_equal_for_phi_arg_p (val1
, val2
))
1260 if (gvn_uses_equal (val1
, val2
))
1269 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1270 phi alternatives for BB1 and BB2 are equal. */
1273 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1280 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1282 succ
= BASIC_BLOCK (s
);
1283 e1
= find_edge (bb1
, succ
);
1284 e2
= find_edge (bb2
, succ
);
1285 if (e1
->flags
& EDGE_COMPLEX
1286 || e2
->flags
& EDGE_COMPLEX
)
1289 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1291 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1298 /* Return true if BB has non-vop phis. */
1301 bb_has_non_vop_phi (basic_block bb
)
1303 gimple_seq phis
= phi_nodes (bb
);
1309 if (!gimple_seq_singleton_p (phis
))
1312 phi
= gimple_seq_first_stmt (phis
);
1313 return !virtual_operand_p (gimple_phi_result (phi
));
1316 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1317 invariant that uses in FROM are dominates by their defs. */
1320 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1322 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1325 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1330 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1331 bitmap_set_bit (from_preds
, e
->src
->index
);
1332 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1333 BITMAP_FREE (from_preds
);
1335 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1338 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1339 replacement bb) and vice versa maintains the invariant that uses in the
1340 replacement are dominates by their defs. */
1343 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1345 if (BB_CLUSTER (bb1
) != NULL
)
1346 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1348 if (BB_CLUSTER (bb2
) != NULL
)
1349 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1351 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1352 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1355 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1358 find_clusters_1 (same_succ same_succ
)
1360 basic_block bb1
, bb2
;
1362 bitmap_iterator bi
, bj
;
1364 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1366 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1368 bb1
= BASIC_BLOCK (i
);
1370 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1371 phi-nodes in bb1 and bb2, with the same alternatives for the same
1373 if (bb_has_non_vop_phi (bb1
))
1377 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1379 bb2
= BASIC_BLOCK (j
);
1381 if (bb_has_non_vop_phi (bb2
))
1384 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1387 /* Limit quadratic behaviour. */
1389 if (nr_comparisons
> max_comparisons
)
1392 /* This is a conservative dependency check. We could test more
1393 precise for allowed replacement direction. */
1394 if (!deps_ok_for_redirect (bb1
, bb2
))
1397 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1400 find_duplicate (same_succ
, bb1
, bb2
);
1405 /* Find clusters of bbs which can be merged. */
1408 find_clusters (void)
1412 while (!VEC_empty (same_succ
, worklist
))
1414 same
= VEC_pop (same_succ
, worklist
);
1415 same
->in_worklist
= false;
1416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1418 fprintf (dump_file
, "processing worklist entry\n");
1419 same_succ_print (dump_file
, same
);
1421 find_clusters_1 (same
);
1425 /* Returns the vop phi of BB, if any. */
1428 vop_phi (basic_block bb
)
1431 gimple_stmt_iterator gsi
;
1432 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1434 stmt
= gsi_stmt (gsi
);
1435 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1442 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1445 replace_block_by (basic_block bb1
, basic_block bb2
)
1451 bb2_phi
= vop_phi (bb2
);
1453 /* Mark the basic block as deleted. */
1454 mark_basic_block_deleted (bb1
);
1456 /* Redirect the incoming edges of bb1 to bb2. */
1457 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1459 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1460 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1461 gcc_assert (pred_edge
!= NULL
);
1463 if (bb2_phi
== NULL
)
1466 /* The phi might have run out of capacity when the redirect added an
1467 argument, which means it could have been replaced. Refresh it. */
1468 bb2_phi
= vop_phi (bb2
);
1470 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1471 pred_edge
, UNKNOWN_LOCATION
);
1474 bb2
->frequency
+= bb1
->frequency
;
1475 if (bb2
->frequency
> BB_FREQ_MAX
)
1476 bb2
->frequency
= BB_FREQ_MAX
;
1479 /* Do updates that use bb1, before deleting bb1. */
1480 release_last_vdef (bb1
);
1481 same_succ_flush_bb (bb1
);
1483 delete_basic_block (bb1
);
1486 /* Bbs for which update_debug_stmt need to be called. */
1488 static bitmap update_bbs
;
1490 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1491 number of bbs removed. */
1494 apply_clusters (void)
1496 basic_block bb1
, bb2
;
1500 int nr_bbs_removed
= 0;
1502 for (i
= 0; i
< VEC_length (bb_cluster
, all_clusters
); ++i
)
1504 c
= VEC_index (bb_cluster
, all_clusters
, i
);
1509 bitmap_set_bit (update_bbs
, bb2
->index
);
1511 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1512 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1514 bb1
= BASIC_BLOCK (j
);
1515 bitmap_clear_bit (update_bbs
, bb1
->index
);
1517 replace_block_by (bb1
, bb2
);
1522 return nr_bbs_removed
;
1525 /* Resets debug statement STMT if it has uses that are not dominated by their
1529 update_debug_stmt (gimple stmt
)
1531 use_operand_p use_p
;
1533 basic_block bbdef
, bbuse
;
1537 if (!gimple_debug_bind_p (stmt
))
1540 bbuse
= gimple_bb (stmt
);
1541 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1543 name
= USE_FROM_PTR (use_p
);
1544 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1546 def_stmt
= SSA_NAME_DEF_STMT (name
);
1547 gcc_assert (def_stmt
!= NULL
);
1549 bbdef
= gimple_bb (def_stmt
);
1550 if (bbdef
== NULL
|| bbuse
== bbdef
1551 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1554 gimple_debug_bind_reset_value (stmt
);
1559 /* Resets all debug statements that have uses that are not
1560 dominated by their defs. */
1563 update_debug_stmts (void)
1569 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1572 gimple_stmt_iterator gsi
;
1574 bb
= BASIC_BLOCK (i
);
1575 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1577 stmt
= gsi_stmt (gsi
);
1578 if (!is_gimple_debug (stmt
))
1580 update_debug_stmt (stmt
);
1585 /* Runs tail merge optimization. */
1588 tail_merge_optimize (unsigned int todo
)
1590 int nr_bbs_removed_total
= 0;
1592 bool loop_entered
= false;
1593 int iteration_nr
= 0;
1594 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1596 if (!flag_tree_tail_merge
|| max_iterations
== 0)
1599 timevar_push (TV_TREE_TAIL_MERGE
);
1601 calculate_dominance_info (CDI_DOMINATORS
);
1604 while (!VEC_empty (same_succ
, worklist
))
1608 loop_entered
= true;
1609 alloc_cluster_vectors ();
1610 update_bbs
= BITMAP_ALLOC (NULL
);
1613 reset_cluster_vectors ();
1616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1617 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1620 gcc_assert (VEC_empty (same_succ
, worklist
));
1621 if (VEC_empty (bb_cluster
, all_clusters
))
1624 nr_bbs_removed
= apply_clusters ();
1625 nr_bbs_removed_total
+= nr_bbs_removed
;
1626 if (nr_bbs_removed
== 0)
1629 free_dominance_info (CDI_DOMINATORS
);
1631 if (iteration_nr
== max_iterations
)
1634 calculate_dominance_info (CDI_DOMINATORS
);
1638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1639 fprintf (dump_file
, "htab collision / search: %f\n",
1640 htab_collisions (same_succ_htab
));
1642 if (nr_bbs_removed_total
> 0)
1644 if (MAY_HAVE_DEBUG_STMTS
)
1646 calculate_dominance_info (CDI_DOMINATORS
);
1647 update_debug_stmts ();
1650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1652 fprintf (dump_file
, "Before TODOs.\n");
1653 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1656 todo
|= (TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow
);
1657 mark_virtual_operands_for_renaming (cfun
);
1663 delete_cluster_vectors ();
1664 BITMAP_FREE (update_bbs
);
1667 timevar_pop (TV_TREE_TAIL_MERGE
);