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"
194 #include "basic-block.h"
196 #include "function.h"
198 #include "gimple-iterator.h"
199 #include "gimple-ssa.h"
200 #include "tree-cfg.h"
201 #include "tree-phinodes.h"
202 #include "ssa-iterators.h"
203 #include "tree-into-ssa.h"
204 #include "tree-ssa-alias.h"
206 #include "hash-table.h"
207 #include "gimple-pretty-print.h"
208 #include "tree-ssa-sccvn.h"
209 #include "tree-dump.h"
211 #include "tree-pass.h"
213 /* Describes a group of bbs with the same successors. The successor bbs are
214 cached in succs, and the successor edge flags are cached in succ_flags.
215 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
216 it's marked in inverse.
217 Additionally, the hash value for the struct is cached in hashval, and
218 in_worklist indicates whether it's currently part of worklist. */
222 /* The bbs that have the same successor bbs. */
224 /* The successor bbs. */
226 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
229 /* The edge flags for each of the successor bbs. */
231 /* Indicates whether the struct is currently in the worklist. */
233 /* The hash value of the struct. */
236 /* hash_table support. */
237 typedef same_succ_def value_type
;
238 typedef same_succ_def compare_type
;
239 static inline hashval_t
hash (const value_type
*);
240 static int equal (const value_type
*, const compare_type
*);
241 static void remove (value_type
*);
243 typedef struct same_succ_def
*same_succ
;
244 typedef const struct same_succ_def
*const_same_succ
;
246 /* hash routine for hash_table support, returns hashval of E. */
249 same_succ_def::hash (const value_type
*e
)
254 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
256 struct bb_cluster_def
258 /* The bbs in the cluster. */
260 /* The preds of the bbs in the cluster. */
262 /* Index in all_clusters vector. */
264 /* The bb to replace the cluster with. */
267 typedef struct bb_cluster_def
*bb_cluster
;
268 typedef const struct bb_cluster_def
*const_bb_cluster
;
274 /* The number of non-debug statements in the bb. */
276 /* The same_succ that this bb is a member of. */
277 same_succ bb_same_succ
;
278 /* The cluster that this bb is a member of. */
280 /* The vop state at the exit of a bb. This is shortlived data, used to
281 communicate data between update_block_by and update_vuses. */
283 /* The bb that either contains or is dominated by the dependencies of the
288 /* Macros to access the fields of struct aux_bb_info. */
290 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
291 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
292 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
293 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
294 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
296 /* Returns true if the only effect a statement STMT has, is to define locally
300 stmt_local_def (gimple stmt
)
302 basic_block bb
, def_bb
;
303 imm_use_iterator iter
;
308 if (gimple_has_side_effects (stmt
)
309 || gimple_vdef (stmt
) != NULL_TREE
)
312 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
316 val
= DEF_FROM_PTR (def_p
);
317 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
320 def_bb
= gimple_bb (stmt
);
322 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
324 if (is_gimple_debug (USE_STMT (use_p
)))
326 bb
= gimple_bb (USE_STMT (use_p
));
330 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
331 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
340 /* Let GSI skip forwards over local defs. */
343 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
349 if (gsi_end_p (*gsi
))
351 stmt
= gsi_stmt (*gsi
);
352 if (!stmt_local_def (stmt
))
354 gsi_next_nondebug (gsi
);
358 /* VAL1 and VAL2 are either:
359 - uses in BB1 and BB2, or
360 - phi alternatives for BB1 and BB2.
361 Return true if the uses have the same gvn value. */
364 gvn_uses_equal (tree val1
, tree val2
)
366 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
371 if (vn_valueize (val1
) != vn_valueize (val2
))
374 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
375 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
378 /* Prints E to FILE. */
381 same_succ_print (FILE *file
, const same_succ e
)
384 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
385 bitmap_print (file
, e
->succs
, "succs:", "\n");
386 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
387 fprintf (file
, "flags:");
388 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
389 fprintf (file
, " %x", e
->succ_flags
[i
]);
390 fprintf (file
, "\n");
393 /* Prints same_succ VE to VFILE. */
396 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
398 const same_succ e
= *pe
;
399 same_succ_print (file
, e
);
403 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
406 update_dep_bb (basic_block use_bb
, tree val
)
411 if (TREE_CODE (val
) != SSA_NAME
)
414 /* Skip use of global def. */
415 if (SSA_NAME_IS_DEFAULT_DEF (val
))
418 /* Skip use of local def. */
419 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
420 if (dep_bb
== use_bb
)
423 if (BB_DEP_BB (use_bb
) == NULL
424 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
425 BB_DEP_BB (use_bb
) = dep_bb
;
428 /* Update BB_DEP_BB, given the dependencies in STMT. */
431 stmt_update_dep_bb (gimple stmt
)
436 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
437 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
440 /* Calculates hash value for same_succ VE. */
443 same_succ_hash (const_same_succ e
)
445 hashval_t hashval
= bitmap_hash (e
->succs
);
448 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
449 basic_block bb
= BASIC_BLOCK (first
);
451 gimple_stmt_iterator gsi
;
457 for (gsi
= gsi_start_nondebug_bb (bb
);
458 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
460 stmt
= gsi_stmt (gsi
);
461 stmt_update_dep_bb (stmt
);
462 if (stmt_local_def (stmt
))
466 hashval
= iterative_hash_hashval_t (gimple_code (stmt
), hashval
);
467 if (is_gimple_assign (stmt
))
468 hashval
= iterative_hash_hashval_t (gimple_assign_rhs_code (stmt
),
470 if (!is_gimple_call (stmt
))
472 if (gimple_call_internal_p (stmt
))
473 hashval
= iterative_hash_hashval_t
474 ((hashval_t
) gimple_call_internal_fn (stmt
), hashval
);
476 hashval
= iterative_hash_expr (gimple_call_fn (stmt
), hashval
);
477 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
479 arg
= gimple_call_arg (stmt
, i
);
480 arg
= vn_valueize (arg
);
481 hashval
= iterative_hash_expr (arg
, hashval
);
485 hashval
= iterative_hash_hashval_t (size
, hashval
);
488 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
490 flags
= e
->succ_flags
[i
];
491 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
492 hashval
= iterative_hash_hashval_t (flags
, hashval
);
495 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
497 int n
= find_edge (bb
, BASIC_BLOCK (s
))->dest_idx
;
498 for (gsi
= gsi_start_phis (BASIC_BLOCK (s
)); !gsi_end_p (gsi
);
501 gimple phi
= gsi_stmt (gsi
);
502 tree lhs
= gimple_phi_result (phi
);
503 tree val
= gimple_phi_arg_def (phi
, n
);
505 if (virtual_operand_p (lhs
))
507 update_dep_bb (bb
, val
);
514 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
515 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
516 the other edge flags. */
519 inverse_flags (const_same_succ e1
, const_same_succ e2
)
521 int f1a
, f1b
, f2a
, f2b
;
522 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
524 if (e1
->succ_flags
.length () != 2)
527 f1a
= e1
->succ_flags
[0];
528 f1b
= e1
->succ_flags
[1];
529 f2a
= e2
->succ_flags
[0];
530 f2b
= e2
->succ_flags
[1];
532 if (f1a
== f2a
&& f1b
== f2b
)
535 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
538 /* Compares SAME_SUCCs E1 and E2. */
541 same_succ_def::equal (const value_type
*e1
, const compare_type
*e2
)
543 unsigned int i
, first1
, first2
;
544 gimple_stmt_iterator gsi1
, gsi2
;
546 basic_block bb1
, bb2
;
548 if (e1
->hashval
!= e2
->hashval
)
551 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
554 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
557 if (!inverse_flags (e1
, e2
))
559 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
560 if (e1
->succ_flags
[i
] != e1
->succ_flags
[i
])
564 first1
= bitmap_first_set_bit (e1
->bbs
);
565 first2
= bitmap_first_set_bit (e2
->bbs
);
567 bb1
= BASIC_BLOCK (first1
);
568 bb2
= BASIC_BLOCK (first2
);
570 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
573 gsi1
= gsi_start_nondebug_bb (bb1
);
574 gsi2
= gsi_start_nondebug_bb (bb2
);
575 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
576 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
577 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
579 s1
= gsi_stmt (gsi1
);
580 s2
= gsi_stmt (gsi2
);
581 if (gimple_code (s1
) != gimple_code (s2
))
583 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
585 gsi_next_nondebug (&gsi1
);
586 gsi_next_nondebug (&gsi2
);
587 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
588 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
594 /* Alloc and init a new SAME_SUCC. */
597 same_succ_alloc (void)
599 same_succ same
= XNEW (struct same_succ_def
);
601 same
->bbs
= BITMAP_ALLOC (NULL
);
602 same
->succs
= BITMAP_ALLOC (NULL
);
603 same
->inverse
= BITMAP_ALLOC (NULL
);
604 same
->succ_flags
.create (10);
605 same
->in_worklist
= false;
610 /* Delete same_succ E. */
613 same_succ_def::remove (same_succ e
)
615 BITMAP_FREE (e
->bbs
);
616 BITMAP_FREE (e
->succs
);
617 BITMAP_FREE (e
->inverse
);
618 e
->succ_flags
.release ();
623 /* Reset same_succ SAME. */
626 same_succ_reset (same_succ same
)
628 bitmap_clear (same
->bbs
);
629 bitmap_clear (same
->succs
);
630 bitmap_clear (same
->inverse
);
631 same
->succ_flags
.truncate (0);
634 static hash_table
<same_succ_def
> same_succ_htab
;
636 /* Array that is used to store the edge flags for a successor. */
638 static int *same_succ_edge_flags
;
640 /* Bitmap that is used to mark bbs that are recently deleted. */
642 static bitmap deleted_bbs
;
644 /* Bitmap that is used to mark predecessors of bbs that are
647 static bitmap deleted_bb_preds
;
649 /* Prints same_succ_htab to stderr. */
651 extern void debug_same_succ (void);
653 debug_same_succ ( void)
655 same_succ_htab
.traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
659 /* Vector of bbs to process. */
661 static vec
<same_succ
> worklist
;
663 /* Prints worklist to FILE. */
666 print_worklist (FILE *file
)
669 for (i
= 0; i
< worklist
.length (); ++i
)
670 same_succ_print (file
, worklist
[i
]);
673 /* Adds SAME to worklist. */
676 add_to_worklist (same_succ same
)
678 if (same
->in_worklist
)
681 if (bitmap_count_bits (same
->bbs
) < 2)
684 same
->in_worklist
= true;
685 worklist
.safe_push (same
);
688 /* Add BB to same_succ_htab. */
691 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
695 same_succ same
= *same_p
;
701 /* Be conservative with loop structure. It's not evident that this test
702 is sufficient. Before tail-merge, we've just called
703 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
704 set, so there's no guarantee that the loop->latch value is still valid.
705 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
706 start of pre, we've kept that property intact throughout pre, and are
707 keeping it throughout tail-merge using this test. */
708 || bb
->loop_father
->latch
== bb
)
710 bitmap_set_bit (same
->bbs
, bb
->index
);
711 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
713 int index
= e
->dest
->index
;
714 bitmap_set_bit (same
->succs
, index
);
715 same_succ_edge_flags
[index
] = e
->flags
;
717 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
718 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
720 same
->hashval
= same_succ_hash (same
);
722 slot
= same_succ_htab
.find_slot_with_hash (same
, same
->hashval
, INSERT
);
726 BB_SAME_SUCC (bb
) = same
;
727 add_to_worklist (same
);
732 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
733 BB_SAME_SUCC (bb
) = *slot
;
734 add_to_worklist (*slot
);
735 if (inverse_flags (same
, *slot
))
736 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
737 same_succ_reset (same
);
741 /* Find bbs with same successors. */
744 find_same_succ (void)
746 same_succ same
= same_succ_alloc ();
751 find_same_succ_bb (bb
, &same
);
753 same
= same_succ_alloc ();
756 same_succ_def::remove (same
);
759 /* Initializes worklist administration. */
764 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
765 same_succ_htab
.create (n_basic_blocks
);
766 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block
);
767 deleted_bbs
= BITMAP_ALLOC (NULL
);
768 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
769 worklist
.create (n_basic_blocks
);
772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
774 fprintf (dump_file
, "initial worklist:\n");
775 print_worklist (dump_file
);
779 /* Deletes worklist administration. */
782 delete_worklist (void)
784 free_aux_for_blocks ();
785 same_succ_htab
.dispose ();
786 XDELETEVEC (same_succ_edge_flags
);
787 same_succ_edge_flags
= NULL
;
788 BITMAP_FREE (deleted_bbs
);
789 BITMAP_FREE (deleted_bb_preds
);
793 /* Mark BB as deleted, and mark its predecessors. */
796 mark_basic_block_deleted (basic_block bb
)
801 bitmap_set_bit (deleted_bbs
, bb
->index
);
803 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
804 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
807 /* Removes BB from its corresponding same_succ. */
810 same_succ_flush_bb (basic_block bb
)
812 same_succ same
= BB_SAME_SUCC (bb
);
813 BB_SAME_SUCC (bb
) = NULL
;
814 if (bitmap_single_bit_set_p (same
->bbs
))
815 same_succ_htab
.remove_elt_with_hash (same
, same
->hashval
);
817 bitmap_clear_bit (same
->bbs
, bb
->index
);
820 /* Removes all bbs in BBS from their corresponding same_succ. */
823 same_succ_flush_bbs (bitmap bbs
)
828 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
829 same_succ_flush_bb (BASIC_BLOCK (i
));
832 /* Release the last vdef in BB, either normal or phi result. */
835 release_last_vdef (basic_block bb
)
837 gimple_stmt_iterator i
;
839 for (i
= gsi_last_bb (bb
); !gsi_end_p (i
); gsi_prev_nondebug (&i
))
841 gimple stmt
= gsi_stmt (i
);
842 if (gimple_vdef (stmt
) == NULL_TREE
)
845 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
849 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
851 gimple phi
= gsi_stmt (i
);
852 tree res
= gimple_phi_result (phi
);
854 if (!virtual_operand_p (res
))
857 mark_virtual_phi_result_for_renaming (phi
);
863 /* For deleted_bb_preds, find bbs with same successors. */
866 update_worklist (void)
873 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
874 bitmap_clear (deleted_bbs
);
876 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
877 same_succ_flush_bbs (deleted_bb_preds
);
879 same
= same_succ_alloc ();
880 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
882 bb
= BASIC_BLOCK (i
);
883 gcc_assert (bb
!= NULL
);
884 find_same_succ_bb (bb
, &same
);
886 same
= same_succ_alloc ();
888 same_succ_def::remove (same
);
889 bitmap_clear (deleted_bb_preds
);
892 /* Prints cluster C to FILE. */
895 print_cluster (FILE *file
, bb_cluster c
)
899 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
900 bitmap_print (file
, c
->preds
, "preds:", "\n");
903 /* Prints cluster C to stderr. */
905 extern void debug_cluster (bb_cluster
);
907 debug_cluster (bb_cluster c
)
909 print_cluster (stderr
, c
);
912 /* Update C->rep_bb, given that BB is added to the cluster. */
915 update_rep_bb (bb_cluster c
, basic_block bb
)
918 if (c
->rep_bb
== NULL
)
924 /* Current needs no deps, keep it. */
925 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
928 /* Bb needs no deps, change rep_bb. */
929 if (BB_DEP_BB (bb
) == NULL
)
935 /* Bb needs last deps earlier than current, change rep_bb. A potential
936 problem with this, is that the first deps might also be earlier, which
937 would mean we prefer longer lifetimes for the deps. To be able to check
938 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
939 BB_DEP_BB, which is really BB_LAST_DEP_BB.
940 The benefit of choosing the bb with last deps earlier, is that it can
941 potentially be used as replacement for more bbs. */
942 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
946 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
949 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
954 bitmap_set_bit (c
->bbs
, bb
->index
);
956 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
957 bitmap_set_bit (c
->preds
, e
->src
->index
);
959 update_rep_bb (c
, bb
);
962 /* Allocate and init new cluster. */
968 c
= XCNEW (struct bb_cluster_def
);
969 c
->bbs
= BITMAP_ALLOC (NULL
);
970 c
->preds
= BITMAP_ALLOC (NULL
);
975 /* Delete clusters. */
978 delete_cluster (bb_cluster c
)
982 BITMAP_FREE (c
->bbs
);
983 BITMAP_FREE (c
->preds
);
988 /* Array that contains all clusters. */
990 static vec
<bb_cluster
> all_clusters
;
992 /* Allocate all cluster vectors. */
995 alloc_cluster_vectors (void)
997 all_clusters
.create (n_basic_blocks
);
1000 /* Reset all cluster vectors. */
1003 reset_cluster_vectors (void)
1007 for (i
= 0; i
< all_clusters
.length (); ++i
)
1008 delete_cluster (all_clusters
[i
]);
1009 all_clusters
.truncate (0);
1011 BB_CLUSTER (bb
) = NULL
;
1014 /* Delete all cluster vectors. */
1017 delete_cluster_vectors (void)
1020 for (i
= 0; i
< all_clusters
.length (); ++i
)
1021 delete_cluster (all_clusters
[i
]);
1022 all_clusters
.release ();
1025 /* Merge cluster C2 into C1. */
1028 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1030 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1031 bitmap_ior_into (c1
->preds
, c2
->preds
);
1034 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1035 all_clusters, or merge c with existing cluster. */
1038 set_cluster (basic_block bb1
, basic_block bb2
)
1040 basic_block merge_bb
, other_bb
;
1041 bb_cluster merge
, old
, c
;
1043 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1046 add_bb_to_cluster (c
, bb1
);
1047 add_bb_to_cluster (c
, bb2
);
1048 BB_CLUSTER (bb1
) = c
;
1049 BB_CLUSTER (bb2
) = c
;
1050 c
->index
= all_clusters
.length ();
1051 all_clusters
.safe_push (c
);
1053 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1055 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1056 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1057 merge
= BB_CLUSTER (merge_bb
);
1058 add_bb_to_cluster (merge
, other_bb
);
1059 BB_CLUSTER (other_bb
) = merge
;
1061 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1066 old
= BB_CLUSTER (bb2
);
1067 merge
= BB_CLUSTER (bb1
);
1068 merge_clusters (merge
, old
);
1069 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1070 BB_CLUSTER (BASIC_BLOCK (i
)) = merge
;
1071 all_clusters
[old
->index
] = NULL
;
1072 update_rep_bb (merge
, old
->rep_bb
);
1073 delete_cluster (old
);
1079 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1080 gimple_bb (s2) are members of SAME_SUCC. */
1083 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1087 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1089 bool equal
, inv_cond
;
1090 enum tree_code code1
, code2
;
1092 if (gimple_code (s1
) != gimple_code (s2
))
1095 switch (gimple_code (s1
))
1098 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1100 if (!gimple_call_same_target_p (s1
, s2
))
1103 /* Eventually, we'll significantly complicate the CFG by adding
1104 back edges to properly model the effects of transaction restart.
1105 For the bulk of optimization this does not matter, but what we
1106 cannot recover from is tail merging blocks between two separate
1107 transactions. Avoid that by making commit not match. */
1108 if (gimple_call_builtin_p (s1
, BUILT_IN_TM_COMMIT
))
1112 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1114 t1
= gimple_call_arg (s1
, i
);
1115 t2
= gimple_call_arg (s2
, i
);
1116 if (operand_equal_p (t1
, t2
, 0))
1118 if (gvn_uses_equal (t1
, t2
))
1126 lhs1
= gimple_get_lhs (s1
);
1127 lhs2
= gimple_get_lhs (s2
);
1128 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1130 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1132 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1133 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1134 return operand_equal_p (lhs1
, lhs2
, 0);
1137 lhs1
= gimple_get_lhs (s1
);
1138 lhs2
= gimple_get_lhs (s2
);
1139 if (TREE_CODE (lhs1
) != SSA_NAME
1140 && TREE_CODE (lhs2
) != SSA_NAME
)
1141 return (vn_valueize (gimple_vdef (s1
))
1142 == vn_valueize (gimple_vdef (s2
)));
1143 else if (TREE_CODE (lhs1
) == SSA_NAME
1144 && TREE_CODE (lhs2
) == SSA_NAME
)
1145 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1149 t1
= gimple_cond_lhs (s1
);
1150 t2
= gimple_cond_lhs (s2
);
1151 if (!operand_equal_p (t1
, t2
, 0)
1152 && !gvn_uses_equal (t1
, t2
))
1155 t1
= gimple_cond_rhs (s1
);
1156 t2
= gimple_cond_rhs (s2
);
1157 if (!operand_equal_p (t1
, t2
, 0)
1158 && !gvn_uses_equal (t1
, t2
))
1161 code1
= gimple_expr_code (s1
);
1162 code2
= gimple_expr_code (s2
);
1163 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1164 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1168 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1169 code2
= invert_tree_comparison (code2
, honor_nans
);
1171 return code1
== code2
;
1178 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1179 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1180 processed statements. */
1183 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1191 if (gsi_end_p (*gsi
))
1193 stmt
= gsi_stmt (*gsi
);
1195 lvuse
= gimple_vuse (stmt
);
1196 if (lvuse
!= NULL_TREE
)
1199 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1200 *vuse_escaped
= true;
1203 if (!stmt_local_def (stmt
))
1205 gsi_prev_nondebug (gsi
);
1209 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1213 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1215 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1216 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1217 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1218 bool vuse_escaped
= false;
1220 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1221 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1223 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1225 gimple stmt1
= gsi_stmt (gsi1
);
1226 gimple stmt2
= gsi_stmt (gsi2
);
1228 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1231 // We cannot tail-merge the builtins that end transactions.
1232 // ??? The alternative being unsharing of BBs in the tm_init pass.
1234 && is_gimple_call (stmt1
)
1235 && (gimple_call_flags (stmt1
) & ECF_TM_BUILTIN
)
1236 && is_tm_ending_fndecl (gimple_call_fndecl (stmt1
)))
1239 gsi_prev_nondebug (&gsi1
);
1240 gsi_prev_nondebug (&gsi2
);
1241 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1242 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1245 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1248 /* If the incoming vuses are not the same, and the vuse escaped into an
1249 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1250 which potentially means the semantics of one of the blocks will be changed.
1251 TODO: make this check more precise. */
1252 if (vuse_escaped
&& vuse1
!= vuse2
)
1256 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1257 bb1
->index
, bb2
->index
);
1259 set_cluster (bb1
, bb2
);
1262 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1266 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1268 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1269 gimple_stmt_iterator gsi
;
1271 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1273 gimple phi
= gsi_stmt (gsi
);
1274 tree lhs
= gimple_phi_result (phi
);
1275 tree val1
= gimple_phi_arg_def (phi
, n1
);
1276 tree val2
= gimple_phi_arg_def (phi
, n2
);
1278 if (virtual_operand_p (lhs
))
1281 if (operand_equal_for_phi_arg_p (val1
, val2
))
1283 if (gvn_uses_equal (val1
, val2
))
1292 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1293 phi alternatives for BB1 and BB2 are equal. */
1296 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1303 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1305 succ
= BASIC_BLOCK (s
);
1306 e1
= find_edge (bb1
, succ
);
1307 e2
= find_edge (bb2
, succ
);
1308 if (e1
->flags
& EDGE_COMPLEX
1309 || e2
->flags
& EDGE_COMPLEX
)
1312 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1314 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1321 /* Return true if BB has non-vop phis. */
1324 bb_has_non_vop_phi (basic_block bb
)
1326 gimple_seq phis
= phi_nodes (bb
);
1332 if (!gimple_seq_singleton_p (phis
))
1335 phi
= gimple_seq_first_stmt (phis
);
1336 return !virtual_operand_p (gimple_phi_result (phi
));
1339 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1340 invariant that uses in FROM are dominates by their defs. */
1343 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1345 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1348 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1353 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1354 bitmap_set_bit (from_preds
, e
->src
->index
);
1355 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1356 BITMAP_FREE (from_preds
);
1358 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1361 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1362 replacement bb) and vice versa maintains the invariant that uses in the
1363 replacement are dominates by their defs. */
1366 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1368 if (BB_CLUSTER (bb1
) != NULL
)
1369 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1371 if (BB_CLUSTER (bb2
) != NULL
)
1372 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1374 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1375 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1378 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1381 find_clusters_1 (same_succ same_succ
)
1383 basic_block bb1
, bb2
;
1385 bitmap_iterator bi
, bj
;
1387 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1389 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1391 bb1
= BASIC_BLOCK (i
);
1393 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1394 phi-nodes in bb1 and bb2, with the same alternatives for the same
1396 if (bb_has_non_vop_phi (bb1
))
1400 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1402 bb2
= BASIC_BLOCK (j
);
1404 if (bb_has_non_vop_phi (bb2
))
1407 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1410 /* Limit quadratic behaviour. */
1412 if (nr_comparisons
> max_comparisons
)
1415 /* This is a conservative dependency check. We could test more
1416 precise for allowed replacement direction. */
1417 if (!deps_ok_for_redirect (bb1
, bb2
))
1420 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1423 find_duplicate (same_succ
, bb1
, bb2
);
1428 /* Find clusters of bbs which can be merged. */
1431 find_clusters (void)
1435 while (!worklist
.is_empty ())
1437 same
= worklist
.pop ();
1438 same
->in_worklist
= false;
1439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1441 fprintf (dump_file
, "processing worklist entry\n");
1442 same_succ_print (dump_file
, same
);
1444 find_clusters_1 (same
);
1448 /* Returns the vop phi of BB, if any. */
1451 vop_phi (basic_block bb
)
1454 gimple_stmt_iterator gsi
;
1455 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1457 stmt
= gsi_stmt (gsi
);
1458 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1465 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1468 replace_block_by (basic_block bb1
, basic_block bb2
)
1476 bb2_phi
= vop_phi (bb2
);
1478 /* Mark the basic block as deleted. */
1479 mark_basic_block_deleted (bb1
);
1481 /* Redirect the incoming edges of bb1 to bb2. */
1482 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1484 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1485 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1486 gcc_assert (pred_edge
!= NULL
);
1488 if (bb2_phi
== NULL
)
1491 /* The phi might have run out of capacity when the redirect added an
1492 argument, which means it could have been replaced. Refresh it. */
1493 bb2_phi
= vop_phi (bb2
);
1495 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1496 pred_edge
, UNKNOWN_LOCATION
);
1499 bb2
->frequency
+= bb1
->frequency
;
1500 if (bb2
->frequency
> BB_FREQ_MAX
)
1501 bb2
->frequency
= BB_FREQ_MAX
;
1503 bb2
->count
+= bb1
->count
;
1505 /* Merge the outgoing edge counts from bb1 onto bb2. */
1506 gcov_type out_sum
= 0;
1507 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1509 e2
= find_edge (bb2
, e1
->dest
);
1511 e2
->count
+= e1
->count
;
1512 out_sum
+= e2
->count
;
1514 /* Recompute the edge probabilities from the new merged edge count.
1515 Use the sum of the new merged edge counts computed above instead
1516 of bb2's merged count, in case there are profile count insanities
1517 making the bb count inconsistent with the edge weights. */
1518 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1520 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1523 /* Do updates that use bb1, before deleting bb1. */
1524 release_last_vdef (bb1
);
1525 same_succ_flush_bb (bb1
);
1527 delete_basic_block (bb1
);
1530 /* Bbs for which update_debug_stmt need to be called. */
1532 static bitmap update_bbs
;
1534 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1535 number of bbs removed. */
1538 apply_clusters (void)
1540 basic_block bb1
, bb2
;
1544 int nr_bbs_removed
= 0;
1546 for (i
= 0; i
< all_clusters
.length (); ++i
)
1548 c
= all_clusters
[i
];
1553 bitmap_set_bit (update_bbs
, bb2
->index
);
1555 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1556 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1558 bb1
= BASIC_BLOCK (j
);
1559 bitmap_clear_bit (update_bbs
, bb1
->index
);
1561 replace_block_by (bb1
, bb2
);
1566 return nr_bbs_removed
;
1569 /* Resets debug statement STMT if it has uses that are not dominated by their
1573 update_debug_stmt (gimple stmt
)
1575 use_operand_p use_p
;
1577 basic_block bbdef
, bbuse
;
1581 if (!gimple_debug_bind_p (stmt
))
1584 bbuse
= gimple_bb (stmt
);
1585 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1587 name
= USE_FROM_PTR (use_p
);
1588 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1590 def_stmt
= SSA_NAME_DEF_STMT (name
);
1591 gcc_assert (def_stmt
!= NULL
);
1593 bbdef
= gimple_bb (def_stmt
);
1594 if (bbdef
== NULL
|| bbuse
== bbdef
1595 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1598 gimple_debug_bind_reset_value (stmt
);
1603 /* Resets all debug statements that have uses that are not
1604 dominated by their defs. */
1607 update_debug_stmts (void)
1613 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1616 gimple_stmt_iterator gsi
;
1618 bb
= BASIC_BLOCK (i
);
1619 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1621 stmt
= gsi_stmt (gsi
);
1622 if (!is_gimple_debug (stmt
))
1624 update_debug_stmt (stmt
);
1629 /* Runs tail merge optimization. */
1632 tail_merge_optimize (unsigned int todo
)
1634 int nr_bbs_removed_total
= 0;
1636 bool loop_entered
= false;
1637 int iteration_nr
= 0;
1638 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1640 if (!flag_tree_tail_merge
1641 || max_iterations
== 0
1642 /* We try to be conservative with respect to loop structure, since:
1643 - the cases where tail-merging could both affect loop structure and be
1644 beneficial are rare,
1645 - it prevents us from having to fixup the loops using
1646 loops_state_set (LOOPS_NEED_FIXUP), and
1647 - keeping loop structure may allow us to simplify the pass.
1648 In order to be conservative, we need loop information. In rare cases
1649 (about 7 test-cases in the g++ testsuite) there is none (because
1650 loop_optimizer_finalize has been called before tail-merge, and
1651 PROP_loops is not set), so we bail out. */
1652 || current_loops
== NULL
)
1655 timevar_push (TV_TREE_TAIL_MERGE
);
1657 if (!dom_info_available_p (CDI_DOMINATORS
))
1659 /* PRE can leave us with unreachable blocks, remove them now. */
1660 delete_unreachable_blocks ();
1661 calculate_dominance_info (CDI_DOMINATORS
);
1665 while (!worklist
.is_empty ())
1669 loop_entered
= true;
1670 alloc_cluster_vectors ();
1671 update_bbs
= BITMAP_ALLOC (NULL
);
1674 reset_cluster_vectors ();
1677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1678 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1681 gcc_assert (worklist
.is_empty ());
1682 if (all_clusters
.is_empty ())
1685 nr_bbs_removed
= apply_clusters ();
1686 nr_bbs_removed_total
+= nr_bbs_removed
;
1687 if (nr_bbs_removed
== 0)
1690 free_dominance_info (CDI_DOMINATORS
);
1692 if (iteration_nr
== max_iterations
)
1695 calculate_dominance_info (CDI_DOMINATORS
);
1699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1700 fprintf (dump_file
, "htab collision / search: %f\n",
1701 same_succ_htab
.collisions ());
1703 if (nr_bbs_removed_total
> 0)
1705 if (MAY_HAVE_DEBUG_STMTS
)
1707 calculate_dominance_info (CDI_DOMINATORS
);
1708 update_debug_stmts ();
1711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1713 fprintf (dump_file
, "Before TODOs.\n");
1714 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1717 todo
|= (TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow
);
1718 mark_virtual_operands_for_renaming (cfun
);
1724 delete_cluster_vectors ();
1725 BITMAP_FREE (update_bbs
);
1728 timevar_pop (TV_TREE_TAIL_MERGE
);