1 /* Tail merging for gimple.
2 Copyright (C) 2011-2013 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"
193 #include "stor-layout.h"
194 #include "trans-mem.h"
196 #include "basic-block.h"
198 #include "function.h"
200 #include "gimple-iterator.h"
201 #include "gimple-ssa.h"
202 #include "tree-cfg.h"
203 #include "tree-phinodes.h"
204 #include "ssa-iterators.h"
205 #include "tree-into-ssa.h"
206 #include "tree-ssa-alias.h"
208 #include "hash-table.h"
209 #include "gimple-pretty-print.h"
210 #include "tree-ssa-sccvn.h"
211 #include "tree-dump.h"
213 #include "tree-pass.h"
214 #include "trans-mem.h"
216 /* Describes a group of bbs with the same successors. The successor bbs are
217 cached in succs, and the successor edge flags are cached in succ_flags.
218 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
219 it's marked in inverse.
220 Additionally, the hash value for the struct is cached in hashval, and
221 in_worklist indicates whether it's currently part of worklist. */
225 /* The bbs that have the same successor bbs. */
227 /* The successor bbs. */
229 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
232 /* The edge flags for each of the successor bbs. */
234 /* Indicates whether the struct is currently in the worklist. */
236 /* The hash value of the struct. */
239 /* hash_table support. */
240 typedef same_succ_def value_type
;
241 typedef same_succ_def compare_type
;
242 static inline hashval_t
hash (const value_type
*);
243 static int equal (const value_type
*, const compare_type
*);
244 static void remove (value_type
*);
246 typedef struct same_succ_def
*same_succ
;
247 typedef const struct same_succ_def
*const_same_succ
;
249 /* hash routine for hash_table support, returns hashval of E. */
252 same_succ_def::hash (const value_type
*e
)
257 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
259 struct bb_cluster_def
261 /* The bbs in the cluster. */
263 /* The preds of the bbs in the cluster. */
265 /* Index in all_clusters vector. */
267 /* The bb to replace the cluster with. */
270 typedef struct bb_cluster_def
*bb_cluster
;
271 typedef const struct bb_cluster_def
*const_bb_cluster
;
277 /* The number of non-debug statements in the bb. */
279 /* The same_succ that this bb is a member of. */
280 same_succ bb_same_succ
;
281 /* The cluster that this bb is a member of. */
283 /* The vop state at the exit of a bb. This is shortlived data, used to
284 communicate data between update_block_by and update_vuses. */
286 /* The bb that either contains or is dominated by the dependencies of the
291 /* Macros to access the fields of struct aux_bb_info. */
293 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
294 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
295 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
296 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
297 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
299 /* Returns true if the only effect a statement STMT has, is to define locally
303 stmt_local_def (gimple stmt
)
305 basic_block bb
, def_bb
;
306 imm_use_iterator iter
;
311 if (gimple_has_side_effects (stmt
)
312 || stmt_could_throw_p (stmt
)
313 || gimple_vdef (stmt
) != NULL_TREE
)
316 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
320 val
= DEF_FROM_PTR (def_p
);
321 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
324 def_bb
= gimple_bb (stmt
);
326 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
328 if (is_gimple_debug (USE_STMT (use_p
)))
330 bb
= gimple_bb (USE_STMT (use_p
));
334 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
335 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
344 /* Let GSI skip forwards over local defs. */
347 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
353 if (gsi_end_p (*gsi
))
355 stmt
= gsi_stmt (*gsi
);
356 if (!stmt_local_def (stmt
))
358 gsi_next_nondebug (gsi
);
362 /* VAL1 and VAL2 are either:
363 - uses in BB1 and BB2, or
364 - phi alternatives for BB1 and BB2.
365 Return true if the uses have the same gvn value. */
368 gvn_uses_equal (tree val1
, tree val2
)
370 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
375 if (vn_valueize (val1
) != vn_valueize (val2
))
378 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
379 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
382 /* Prints E to FILE. */
385 same_succ_print (FILE *file
, const same_succ e
)
388 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
389 bitmap_print (file
, e
->succs
, "succs:", "\n");
390 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
391 fprintf (file
, "flags:");
392 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
393 fprintf (file
, " %x", e
->succ_flags
[i
]);
394 fprintf (file
, "\n");
397 /* Prints same_succ VE to VFILE. */
400 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
402 const same_succ e
= *pe
;
403 same_succ_print (file
, e
);
407 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
410 update_dep_bb (basic_block use_bb
, tree val
)
415 if (TREE_CODE (val
) != SSA_NAME
)
418 /* Skip use of global def. */
419 if (SSA_NAME_IS_DEFAULT_DEF (val
))
422 /* Skip use of local def. */
423 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
424 if (dep_bb
== use_bb
)
427 if (BB_DEP_BB (use_bb
) == NULL
428 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
429 BB_DEP_BB (use_bb
) = dep_bb
;
432 /* Update BB_DEP_BB, given the dependencies in STMT. */
435 stmt_update_dep_bb (gimple stmt
)
440 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
441 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
444 /* Calculates hash value for same_succ VE. */
447 same_succ_hash (const_same_succ e
)
449 hashval_t hashval
= bitmap_hash (e
->succs
);
452 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
453 basic_block bb
= BASIC_BLOCK (first
);
455 gimple_stmt_iterator gsi
;
461 for (gsi
= gsi_start_nondebug_bb (bb
);
462 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
464 stmt
= gsi_stmt (gsi
);
465 stmt_update_dep_bb (stmt
);
466 if (stmt_local_def (stmt
))
470 hashval
= iterative_hash_hashval_t (gimple_code (stmt
), hashval
);
471 if (is_gimple_assign (stmt
))
472 hashval
= iterative_hash_hashval_t (gimple_assign_rhs_code (stmt
),
474 if (!is_gimple_call (stmt
))
476 if (gimple_call_internal_p (stmt
))
477 hashval
= iterative_hash_hashval_t
478 ((hashval_t
) gimple_call_internal_fn (stmt
), hashval
);
480 hashval
= iterative_hash_expr (gimple_call_fn (stmt
), hashval
);
481 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
483 arg
= gimple_call_arg (stmt
, i
);
484 arg
= vn_valueize (arg
);
485 hashval
= iterative_hash_expr (arg
, hashval
);
489 hashval
= iterative_hash_hashval_t (size
, hashval
);
492 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
494 flags
= e
->succ_flags
[i
];
495 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
496 hashval
= iterative_hash_hashval_t (flags
, hashval
);
499 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
501 int n
= find_edge (bb
, BASIC_BLOCK (s
))->dest_idx
;
502 for (gsi
= gsi_start_phis (BASIC_BLOCK (s
)); !gsi_end_p (gsi
);
505 gimple phi
= gsi_stmt (gsi
);
506 tree lhs
= gimple_phi_result (phi
);
507 tree val
= gimple_phi_arg_def (phi
, n
);
509 if (virtual_operand_p (lhs
))
511 update_dep_bb (bb
, val
);
518 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
519 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
520 the other edge flags. */
523 inverse_flags (const_same_succ e1
, const_same_succ e2
)
525 int f1a
, f1b
, f2a
, f2b
;
526 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
528 if (e1
->succ_flags
.length () != 2)
531 f1a
= e1
->succ_flags
[0];
532 f1b
= e1
->succ_flags
[1];
533 f2a
= e2
->succ_flags
[0];
534 f2b
= e2
->succ_flags
[1];
536 if (f1a
== f2a
&& f1b
== f2b
)
539 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
542 /* Compares SAME_SUCCs E1 and E2. */
545 same_succ_def::equal (const value_type
*e1
, const compare_type
*e2
)
547 unsigned int i
, first1
, first2
;
548 gimple_stmt_iterator gsi1
, gsi2
;
550 basic_block bb1
, bb2
;
552 if (e1
->hashval
!= e2
->hashval
)
555 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
558 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
561 if (!inverse_flags (e1
, e2
))
563 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
564 if (e1
->succ_flags
[i
] != e1
->succ_flags
[i
])
568 first1
= bitmap_first_set_bit (e1
->bbs
);
569 first2
= bitmap_first_set_bit (e2
->bbs
);
571 bb1
= BASIC_BLOCK (first1
);
572 bb2
= BASIC_BLOCK (first2
);
574 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
577 gsi1
= gsi_start_nondebug_bb (bb1
);
578 gsi2
= gsi_start_nondebug_bb (bb2
);
579 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
580 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
581 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
583 s1
= gsi_stmt (gsi1
);
584 s2
= gsi_stmt (gsi2
);
585 if (gimple_code (s1
) != gimple_code (s2
))
587 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
589 gsi_next_nondebug (&gsi1
);
590 gsi_next_nondebug (&gsi2
);
591 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
592 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
598 /* Alloc and init a new SAME_SUCC. */
601 same_succ_alloc (void)
603 same_succ same
= XNEW (struct same_succ_def
);
605 same
->bbs
= BITMAP_ALLOC (NULL
);
606 same
->succs
= BITMAP_ALLOC (NULL
);
607 same
->inverse
= BITMAP_ALLOC (NULL
);
608 same
->succ_flags
.create (10);
609 same
->in_worklist
= false;
614 /* Delete same_succ E. */
617 same_succ_def::remove (same_succ e
)
619 BITMAP_FREE (e
->bbs
);
620 BITMAP_FREE (e
->succs
);
621 BITMAP_FREE (e
->inverse
);
622 e
->succ_flags
.release ();
627 /* Reset same_succ SAME. */
630 same_succ_reset (same_succ same
)
632 bitmap_clear (same
->bbs
);
633 bitmap_clear (same
->succs
);
634 bitmap_clear (same
->inverse
);
635 same
->succ_flags
.truncate (0);
638 static hash_table
<same_succ_def
> same_succ_htab
;
640 /* Array that is used to store the edge flags for a successor. */
642 static int *same_succ_edge_flags
;
644 /* Bitmap that is used to mark bbs that are recently deleted. */
646 static bitmap deleted_bbs
;
648 /* Bitmap that is used to mark predecessors of bbs that are
651 static bitmap deleted_bb_preds
;
653 /* Prints same_succ_htab to stderr. */
655 extern void debug_same_succ (void);
657 debug_same_succ ( void)
659 same_succ_htab
.traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
663 /* Vector of bbs to process. */
665 static vec
<same_succ
> worklist
;
667 /* Prints worklist to FILE. */
670 print_worklist (FILE *file
)
673 for (i
= 0; i
< worklist
.length (); ++i
)
674 same_succ_print (file
, worklist
[i
]);
677 /* Adds SAME to worklist. */
680 add_to_worklist (same_succ same
)
682 if (same
->in_worklist
)
685 if (bitmap_count_bits (same
->bbs
) < 2)
688 same
->in_worklist
= true;
689 worklist
.safe_push (same
);
692 /* Add BB to same_succ_htab. */
695 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
699 same_succ same
= *same_p
;
705 /* Be conservative with loop structure. It's not evident that this test
706 is sufficient. Before tail-merge, we've just called
707 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
708 set, so there's no guarantee that the loop->latch value is still valid.
709 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
710 start of pre, we've kept that property intact throughout pre, and are
711 keeping it throughout tail-merge using this test. */
712 || bb
->loop_father
->latch
== bb
)
714 bitmap_set_bit (same
->bbs
, bb
->index
);
715 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
717 int index
= e
->dest
->index
;
718 bitmap_set_bit (same
->succs
, index
);
719 same_succ_edge_flags
[index
] = e
->flags
;
721 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
722 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
724 same
->hashval
= same_succ_hash (same
);
726 slot
= same_succ_htab
.find_slot_with_hash (same
, same
->hashval
, INSERT
);
730 BB_SAME_SUCC (bb
) = same
;
731 add_to_worklist (same
);
736 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
737 BB_SAME_SUCC (bb
) = *slot
;
738 add_to_worklist (*slot
);
739 if (inverse_flags (same
, *slot
))
740 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
741 same_succ_reset (same
);
745 /* Find bbs with same successors. */
748 find_same_succ (void)
750 same_succ same
= same_succ_alloc ();
755 find_same_succ_bb (bb
, &same
);
757 same
= same_succ_alloc ();
760 same_succ_def::remove (same
);
763 /* Initializes worklist administration. */
768 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
769 same_succ_htab
.create (n_basic_blocks_for_fn (cfun
));
770 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block
);
771 deleted_bbs
= BITMAP_ALLOC (NULL
);
772 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
773 worklist
.create (n_basic_blocks_for_fn (cfun
));
776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
778 fprintf (dump_file
, "initial worklist:\n");
779 print_worklist (dump_file
);
783 /* Deletes worklist administration. */
786 delete_worklist (void)
788 free_aux_for_blocks ();
789 same_succ_htab
.dispose ();
790 XDELETEVEC (same_succ_edge_flags
);
791 same_succ_edge_flags
= NULL
;
792 BITMAP_FREE (deleted_bbs
);
793 BITMAP_FREE (deleted_bb_preds
);
797 /* Mark BB as deleted, and mark its predecessors. */
800 mark_basic_block_deleted (basic_block bb
)
805 bitmap_set_bit (deleted_bbs
, bb
->index
);
807 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
808 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
811 /* Removes BB from its corresponding same_succ. */
814 same_succ_flush_bb (basic_block bb
)
816 same_succ same
= BB_SAME_SUCC (bb
);
817 BB_SAME_SUCC (bb
) = NULL
;
818 if (bitmap_single_bit_set_p (same
->bbs
))
819 same_succ_htab
.remove_elt_with_hash (same
, same
->hashval
);
821 bitmap_clear_bit (same
->bbs
, bb
->index
);
824 /* Removes all bbs in BBS from their corresponding same_succ. */
827 same_succ_flush_bbs (bitmap bbs
)
832 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
833 same_succ_flush_bb (BASIC_BLOCK (i
));
836 /* Release the last vdef in BB, either normal or phi result. */
839 release_last_vdef (basic_block bb
)
841 gimple_stmt_iterator i
;
843 for (i
= gsi_last_bb (bb
); !gsi_end_p (i
); gsi_prev_nondebug (&i
))
845 gimple stmt
= gsi_stmt (i
);
846 if (gimple_vdef (stmt
) == NULL_TREE
)
849 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
853 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
855 gimple phi
= gsi_stmt (i
);
856 tree res
= gimple_phi_result (phi
);
858 if (!virtual_operand_p (res
))
861 mark_virtual_phi_result_for_renaming (phi
);
867 /* For deleted_bb_preds, find bbs with same successors. */
870 update_worklist (void)
877 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
878 bitmap_clear (deleted_bbs
);
880 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
881 same_succ_flush_bbs (deleted_bb_preds
);
883 same
= same_succ_alloc ();
884 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
886 bb
= BASIC_BLOCK (i
);
887 gcc_assert (bb
!= NULL
);
888 find_same_succ_bb (bb
, &same
);
890 same
= same_succ_alloc ();
892 same_succ_def::remove (same
);
893 bitmap_clear (deleted_bb_preds
);
896 /* Prints cluster C to FILE. */
899 print_cluster (FILE *file
, bb_cluster c
)
903 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
904 bitmap_print (file
, c
->preds
, "preds:", "\n");
907 /* Prints cluster C to stderr. */
909 extern void debug_cluster (bb_cluster
);
911 debug_cluster (bb_cluster c
)
913 print_cluster (stderr
, c
);
916 /* Update C->rep_bb, given that BB is added to the cluster. */
919 update_rep_bb (bb_cluster c
, basic_block bb
)
922 if (c
->rep_bb
== NULL
)
928 /* Current needs no deps, keep it. */
929 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
932 /* Bb needs no deps, change rep_bb. */
933 if (BB_DEP_BB (bb
) == NULL
)
939 /* Bb needs last deps earlier than current, change rep_bb. A potential
940 problem with this, is that the first deps might also be earlier, which
941 would mean we prefer longer lifetimes for the deps. To be able to check
942 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
943 BB_DEP_BB, which is really BB_LAST_DEP_BB.
944 The benefit of choosing the bb with last deps earlier, is that it can
945 potentially be used as replacement for more bbs. */
946 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
950 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
953 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
958 bitmap_set_bit (c
->bbs
, bb
->index
);
960 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
961 bitmap_set_bit (c
->preds
, e
->src
->index
);
963 update_rep_bb (c
, bb
);
966 /* Allocate and init new cluster. */
972 c
= XCNEW (struct bb_cluster_def
);
973 c
->bbs
= BITMAP_ALLOC (NULL
);
974 c
->preds
= BITMAP_ALLOC (NULL
);
979 /* Delete clusters. */
982 delete_cluster (bb_cluster c
)
986 BITMAP_FREE (c
->bbs
);
987 BITMAP_FREE (c
->preds
);
992 /* Array that contains all clusters. */
994 static vec
<bb_cluster
> all_clusters
;
996 /* Allocate all cluster vectors. */
999 alloc_cluster_vectors (void)
1001 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1004 /* Reset all cluster vectors. */
1007 reset_cluster_vectors (void)
1011 for (i
= 0; i
< all_clusters
.length (); ++i
)
1012 delete_cluster (all_clusters
[i
]);
1013 all_clusters
.truncate (0);
1015 BB_CLUSTER (bb
) = NULL
;
1018 /* Delete all cluster vectors. */
1021 delete_cluster_vectors (void)
1024 for (i
= 0; i
< all_clusters
.length (); ++i
)
1025 delete_cluster (all_clusters
[i
]);
1026 all_clusters
.release ();
1029 /* Merge cluster C2 into C1. */
1032 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1034 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1035 bitmap_ior_into (c1
->preds
, c2
->preds
);
1038 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1039 all_clusters, or merge c with existing cluster. */
1042 set_cluster (basic_block bb1
, basic_block bb2
)
1044 basic_block merge_bb
, other_bb
;
1045 bb_cluster merge
, old
, c
;
1047 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1050 add_bb_to_cluster (c
, bb1
);
1051 add_bb_to_cluster (c
, bb2
);
1052 BB_CLUSTER (bb1
) = c
;
1053 BB_CLUSTER (bb2
) = c
;
1054 c
->index
= all_clusters
.length ();
1055 all_clusters
.safe_push (c
);
1057 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1059 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1060 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1061 merge
= BB_CLUSTER (merge_bb
);
1062 add_bb_to_cluster (merge
, other_bb
);
1063 BB_CLUSTER (other_bb
) = merge
;
1065 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1070 old
= BB_CLUSTER (bb2
);
1071 merge
= BB_CLUSTER (bb1
);
1072 merge_clusters (merge
, old
);
1073 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1074 BB_CLUSTER (BASIC_BLOCK (i
)) = merge
;
1075 all_clusters
[old
->index
] = NULL
;
1076 update_rep_bb (merge
, old
->rep_bb
);
1077 delete_cluster (old
);
1083 /* Return true if gimple operands T1 and T2 have the same value. */
1086 gimple_operand_equal_value_p (tree t1
, tree t2
)
1095 if (operand_equal_p (t1
, t2
, 0))
1098 return gvn_uses_equal (t1
, t2
);
1101 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1102 gimple_bb (s2) are members of SAME_SUCC. */
1105 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1109 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1112 enum tree_code code1
, code2
;
1114 if (gimple_code (s1
) != gimple_code (s2
))
1117 switch (gimple_code (s1
))
1120 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1122 if (!gimple_call_same_target_p (s1
, s2
))
1125 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1127 t1
= gimple_call_arg (s1
, i
);
1128 t2
= gimple_call_arg (s2
, i
);
1129 if (gimple_operand_equal_value_p (t1
, t2
))
1134 lhs1
= gimple_get_lhs (s1
);
1135 lhs2
= gimple_get_lhs (s2
);
1136 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1138 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1140 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1141 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1142 return operand_equal_p (lhs1
, lhs2
, 0);
1145 lhs1
= gimple_get_lhs (s1
);
1146 lhs2
= gimple_get_lhs (s2
);
1147 if (TREE_CODE (lhs1
) != SSA_NAME
1148 && TREE_CODE (lhs2
) != SSA_NAME
)
1150 /* If the vdef is the same, it's the same statement. */
1151 if (vn_valueize (gimple_vdef (s1
))
1152 == vn_valueize (gimple_vdef (s2
)))
1155 /* Test for structural equality. */
1156 return (operand_equal_p (lhs1
, lhs2
, 0)
1157 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1158 gimple_assign_rhs1 (s2
)));
1160 else if (TREE_CODE (lhs1
) == SSA_NAME
1161 && TREE_CODE (lhs2
) == SSA_NAME
)
1162 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1166 t1
= gimple_cond_lhs (s1
);
1167 t2
= gimple_cond_lhs (s2
);
1168 if (!gimple_operand_equal_value_p (t1
, t2
))
1171 t1
= gimple_cond_rhs (s1
);
1172 t2
= gimple_cond_rhs (s2
);
1173 if (!gimple_operand_equal_value_p (t1
, t2
))
1176 code1
= gimple_expr_code (s1
);
1177 code2
= gimple_expr_code (s2
);
1178 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1179 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1183 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1184 code2
= invert_tree_comparison (code2
, honor_nans
);
1186 return code1
== code2
;
1193 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1194 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1195 processed statements. */
1198 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1206 if (gsi_end_p (*gsi
))
1208 stmt
= gsi_stmt (*gsi
);
1210 lvuse
= gimple_vuse (stmt
);
1211 if (lvuse
!= NULL_TREE
)
1214 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1215 *vuse_escaped
= true;
1218 if (!stmt_local_def (stmt
))
1220 gsi_prev_nondebug (gsi
);
1224 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1228 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1230 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1231 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1232 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1233 bool vuse_escaped
= false;
1235 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1236 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1238 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1240 gimple stmt1
= gsi_stmt (gsi1
);
1241 gimple stmt2
= gsi_stmt (gsi2
);
1243 /* What could be better than to this this here is to blacklist the bb
1244 containing the stmt, when encountering the stmt f.i. in
1246 if (is_tm_ending (stmt1
)
1247 || is_tm_ending (stmt2
))
1250 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1253 gsi_prev_nondebug (&gsi1
);
1254 gsi_prev_nondebug (&gsi2
);
1255 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1256 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1259 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1262 /* If the incoming vuses are not the same, and the vuse escaped into an
1263 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1264 which potentially means the semantics of one of the blocks will be changed.
1265 TODO: make this check more precise. */
1266 if (vuse_escaped
&& vuse1
!= vuse2
)
1270 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1271 bb1
->index
, bb2
->index
);
1273 set_cluster (bb1
, bb2
);
1276 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1280 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1282 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1283 gimple_stmt_iterator gsi
;
1285 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1287 gimple phi
= gsi_stmt (gsi
);
1288 tree lhs
= gimple_phi_result (phi
);
1289 tree val1
= gimple_phi_arg_def (phi
, n1
);
1290 tree val2
= gimple_phi_arg_def (phi
, n2
);
1292 if (virtual_operand_p (lhs
))
1295 if (operand_equal_for_phi_arg_p (val1
, val2
))
1297 if (gvn_uses_equal (val1
, val2
))
1306 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1307 phi alternatives for BB1 and BB2 are equal. */
1310 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1317 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1319 succ
= BASIC_BLOCK (s
);
1320 e1
= find_edge (bb1
, succ
);
1321 e2
= find_edge (bb2
, succ
);
1322 if (e1
->flags
& EDGE_COMPLEX
1323 || e2
->flags
& EDGE_COMPLEX
)
1326 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1328 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1335 /* Return true if BB has non-vop phis. */
1338 bb_has_non_vop_phi (basic_block bb
)
1340 gimple_seq phis
= phi_nodes (bb
);
1346 if (!gimple_seq_singleton_p (phis
))
1349 phi
= gimple_seq_first_stmt (phis
);
1350 return !virtual_operand_p (gimple_phi_result (phi
));
1353 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1354 invariant that uses in FROM are dominates by their defs. */
1357 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1359 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1362 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1367 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1368 bitmap_set_bit (from_preds
, e
->src
->index
);
1369 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1370 BITMAP_FREE (from_preds
);
1372 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1375 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1376 replacement bb) and vice versa maintains the invariant that uses in the
1377 replacement are dominates by their defs. */
1380 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1382 if (BB_CLUSTER (bb1
) != NULL
)
1383 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1385 if (BB_CLUSTER (bb2
) != NULL
)
1386 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1388 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1389 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1392 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1395 find_clusters_1 (same_succ same_succ
)
1397 basic_block bb1
, bb2
;
1399 bitmap_iterator bi
, bj
;
1401 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1403 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1405 bb1
= BASIC_BLOCK (i
);
1407 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1408 phi-nodes in bb1 and bb2, with the same alternatives for the same
1410 if (bb_has_non_vop_phi (bb1
))
1414 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1416 bb2
= BASIC_BLOCK (j
);
1418 if (bb_has_non_vop_phi (bb2
))
1421 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1424 /* Limit quadratic behaviour. */
1426 if (nr_comparisons
> max_comparisons
)
1429 /* This is a conservative dependency check. We could test more
1430 precise for allowed replacement direction. */
1431 if (!deps_ok_for_redirect (bb1
, bb2
))
1434 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1437 find_duplicate (same_succ
, bb1
, bb2
);
1442 /* Find clusters of bbs which can be merged. */
1445 find_clusters (void)
1449 while (!worklist
.is_empty ())
1451 same
= worklist
.pop ();
1452 same
->in_worklist
= false;
1453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1455 fprintf (dump_file
, "processing worklist entry\n");
1456 same_succ_print (dump_file
, same
);
1458 find_clusters_1 (same
);
1462 /* Returns the vop phi of BB, if any. */
1465 vop_phi (basic_block bb
)
1468 gimple_stmt_iterator gsi
;
1469 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1471 stmt
= gsi_stmt (gsi
);
1472 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1479 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1482 replace_block_by (basic_block bb1
, basic_block bb2
)
1490 bb2_phi
= vop_phi (bb2
);
1492 /* Mark the basic block as deleted. */
1493 mark_basic_block_deleted (bb1
);
1495 /* Redirect the incoming edges of bb1 to bb2. */
1496 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1498 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1499 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1500 gcc_assert (pred_edge
!= NULL
);
1502 if (bb2_phi
== NULL
)
1505 /* The phi might have run out of capacity when the redirect added an
1506 argument, which means it could have been replaced. Refresh it. */
1507 bb2_phi
= vop_phi (bb2
);
1509 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1510 pred_edge
, UNKNOWN_LOCATION
);
1513 bb2
->frequency
+= bb1
->frequency
;
1514 if (bb2
->frequency
> BB_FREQ_MAX
)
1515 bb2
->frequency
= BB_FREQ_MAX
;
1517 bb2
->count
+= bb1
->count
;
1519 /* Merge the outgoing edge counts from bb1 onto bb2. */
1520 gcov_type out_sum
= 0;
1521 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1523 e2
= find_edge (bb2
, e1
->dest
);
1525 e2
->count
+= e1
->count
;
1526 out_sum
+= e2
->count
;
1528 /* Recompute the edge probabilities from the new merged edge count.
1529 Use the sum of the new merged edge counts computed above instead
1530 of bb2's merged count, in case there are profile count insanities
1531 making the bb count inconsistent with the edge weights. */
1532 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1534 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1537 /* Do updates that use bb1, before deleting bb1. */
1538 release_last_vdef (bb1
);
1539 same_succ_flush_bb (bb1
);
1541 delete_basic_block (bb1
);
1544 /* Bbs for which update_debug_stmt need to be called. */
1546 static bitmap update_bbs
;
1548 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1549 number of bbs removed. */
1552 apply_clusters (void)
1554 basic_block bb1
, bb2
;
1558 int nr_bbs_removed
= 0;
1560 for (i
= 0; i
< all_clusters
.length (); ++i
)
1562 c
= all_clusters
[i
];
1567 bitmap_set_bit (update_bbs
, bb2
->index
);
1569 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1570 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1572 bb1
= BASIC_BLOCK (j
);
1573 bitmap_clear_bit (update_bbs
, bb1
->index
);
1575 replace_block_by (bb1
, bb2
);
1580 return nr_bbs_removed
;
1583 /* Resets debug statement STMT if it has uses that are not dominated by their
1587 update_debug_stmt (gimple stmt
)
1589 use_operand_p use_p
;
1591 basic_block bbdef
, bbuse
;
1595 if (!gimple_debug_bind_p (stmt
))
1598 bbuse
= gimple_bb (stmt
);
1599 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1601 name
= USE_FROM_PTR (use_p
);
1602 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1604 def_stmt
= SSA_NAME_DEF_STMT (name
);
1605 gcc_assert (def_stmt
!= NULL
);
1607 bbdef
= gimple_bb (def_stmt
);
1608 if (bbdef
== NULL
|| bbuse
== bbdef
1609 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1612 gimple_debug_bind_reset_value (stmt
);
1617 /* Resets all debug statements that have uses that are not
1618 dominated by their defs. */
1621 update_debug_stmts (void)
1627 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1630 gimple_stmt_iterator gsi
;
1632 bb
= BASIC_BLOCK (i
);
1633 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1635 stmt
= gsi_stmt (gsi
);
1636 if (!is_gimple_debug (stmt
))
1638 update_debug_stmt (stmt
);
1643 /* Runs tail merge optimization. */
1646 tail_merge_optimize (unsigned int todo
)
1648 int nr_bbs_removed_total
= 0;
1650 bool loop_entered
= false;
1651 int iteration_nr
= 0;
1652 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1654 if (!flag_tree_tail_merge
1655 || max_iterations
== 0
1656 /* We try to be conservative with respect to loop structure, since:
1657 - the cases where tail-merging could both affect loop structure and be
1658 beneficial are rare,
1659 - it prevents us from having to fixup the loops using
1660 loops_state_set (LOOPS_NEED_FIXUP), and
1661 - keeping loop structure may allow us to simplify the pass.
1662 In order to be conservative, we need loop information. In rare cases
1663 (about 7 test-cases in the g++ testsuite) there is none (because
1664 loop_optimizer_finalize has been called before tail-merge, and
1665 PROP_loops is not set), so we bail out. */
1666 || current_loops
== NULL
)
1669 timevar_push (TV_TREE_TAIL_MERGE
);
1671 if (!dom_info_available_p (CDI_DOMINATORS
))
1673 /* PRE can leave us with unreachable blocks, remove them now. */
1674 delete_unreachable_blocks ();
1675 calculate_dominance_info (CDI_DOMINATORS
);
1679 while (!worklist
.is_empty ())
1683 loop_entered
= true;
1684 alloc_cluster_vectors ();
1685 update_bbs
= BITMAP_ALLOC (NULL
);
1688 reset_cluster_vectors ();
1691 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1692 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1695 gcc_assert (worklist
.is_empty ());
1696 if (all_clusters
.is_empty ())
1699 nr_bbs_removed
= apply_clusters ();
1700 nr_bbs_removed_total
+= nr_bbs_removed
;
1701 if (nr_bbs_removed
== 0)
1704 free_dominance_info (CDI_DOMINATORS
);
1706 if (iteration_nr
== max_iterations
)
1709 calculate_dominance_info (CDI_DOMINATORS
);
1713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1714 fprintf (dump_file
, "htab collision / search: %f\n",
1715 same_succ_htab
.collisions ());
1717 if (nr_bbs_removed_total
> 0)
1719 if (MAY_HAVE_DEBUG_STMTS
)
1721 calculate_dominance_info (CDI_DOMINATORS
);
1722 update_debug_stmts ();
1725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1727 fprintf (dump_file
, "Before TODOs.\n");
1728 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1731 todo
|= (TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow
);
1732 mark_virtual_operands_for_renaming (cfun
);
1738 delete_cluster_vectors ();
1739 BITMAP_FREE (update_bbs
);
1742 timevar_pop (TV_TREE_TAIL_MERGE
);