1 /* Tail merging for gimple.
2 Copyright (C) 2011-2014 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"
199 #include "hash-table.h"
200 #include "tree-ssa-alias.h"
201 #include "internal-fn.h"
203 #include "gimple-expr.h"
206 #include "gimple-iterator.h"
207 #include "gimple-ssa.h"
208 #include "tree-cfg.h"
209 #include "tree-phinodes.h"
210 #include "ssa-iterators.h"
211 #include "tree-into-ssa.h"
213 #include "gimple-pretty-print.h"
214 #include "tree-ssa-sccvn.h"
215 #include "tree-dump.h"
217 #include "tree-pass.h"
218 #include "trans-mem.h"
220 /* Describes a group of bbs with the same successors. The successor bbs are
221 cached in succs, and the successor edge flags are cached in succ_flags.
222 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
223 it's marked in inverse.
224 Additionally, the hash value for the struct is cached in hashval, and
225 in_worklist indicates whether it's currently part of worklist. */
229 /* The bbs that have the same successor bbs. */
231 /* The successor bbs. */
233 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
236 /* The edge flags for each of the successor bbs. */
238 /* Indicates whether the struct is currently in the worklist. */
240 /* The hash value of the struct. */
243 /* hash_table support. */
244 typedef same_succ_def value_type
;
245 typedef same_succ_def compare_type
;
246 static inline hashval_t
hash (const value_type
*);
247 static int equal (const value_type
*, const compare_type
*);
248 static void remove (value_type
*);
250 typedef struct same_succ_def
*same_succ
;
251 typedef const struct same_succ_def
*const_same_succ
;
253 /* hash routine for hash_table support, returns hashval of E. */
256 same_succ_def::hash (const value_type
*e
)
261 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
263 struct bb_cluster_def
265 /* The bbs in the cluster. */
267 /* The preds of the bbs in the cluster. */
269 /* Index in all_clusters vector. */
271 /* The bb to replace the cluster with. */
274 typedef struct bb_cluster_def
*bb_cluster
;
275 typedef const struct bb_cluster_def
*const_bb_cluster
;
281 /* The number of non-debug statements in the bb. */
283 /* The same_succ that this bb is a member of. */
284 same_succ bb_same_succ
;
285 /* The cluster that this bb is a member of. */
287 /* The vop state at the exit of a bb. This is shortlived data, used to
288 communicate data between update_block_by and update_vuses. */
290 /* The bb that either contains or is dominated by the dependencies of the
295 /* Macros to access the fields of struct aux_bb_info. */
297 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
298 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
299 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
300 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
301 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
303 /* Returns true if the only effect a statement STMT has, is to define locally
307 stmt_local_def (gimple stmt
)
309 basic_block bb
, def_bb
;
310 imm_use_iterator iter
;
315 if (gimple_vdef (stmt
) != NULL_TREE
316 || gimple_has_side_effects (stmt
)
317 || gimple_could_trap_p_1 (stmt
, false, false))
320 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
324 val
= DEF_FROM_PTR (def_p
);
325 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
328 def_bb
= gimple_bb (stmt
);
330 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
332 if (is_gimple_debug (USE_STMT (use_p
)))
334 bb
= gimple_bb (USE_STMT (use_p
));
338 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
339 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
348 /* Let GSI skip forwards over local defs. */
351 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
357 if (gsi_end_p (*gsi
))
359 stmt
= gsi_stmt (*gsi
);
360 if (!stmt_local_def (stmt
))
362 gsi_next_nondebug (gsi
);
366 /* VAL1 and VAL2 are either:
367 - uses in BB1 and BB2, or
368 - phi alternatives for BB1 and BB2.
369 Return true if the uses have the same gvn value. */
372 gvn_uses_equal (tree val1
, tree val2
)
374 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
379 if (vn_valueize (val1
) != vn_valueize (val2
))
382 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
383 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
386 /* Prints E to FILE. */
389 same_succ_print (FILE *file
, const same_succ e
)
392 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
393 bitmap_print (file
, e
->succs
, "succs:", "\n");
394 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
395 fprintf (file
, "flags:");
396 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
397 fprintf (file
, " %x", e
->succ_flags
[i
]);
398 fprintf (file
, "\n");
401 /* Prints same_succ VE to VFILE. */
404 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
406 const same_succ e
= *pe
;
407 same_succ_print (file
, e
);
411 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
414 update_dep_bb (basic_block use_bb
, tree val
)
419 if (TREE_CODE (val
) != SSA_NAME
)
422 /* Skip use of global def. */
423 if (SSA_NAME_IS_DEFAULT_DEF (val
))
426 /* Skip use of local def. */
427 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
428 if (dep_bb
== use_bb
)
431 if (BB_DEP_BB (use_bb
) == NULL
432 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
433 BB_DEP_BB (use_bb
) = dep_bb
;
436 /* Update BB_DEP_BB, given the dependencies in STMT. */
439 stmt_update_dep_bb (gimple stmt
)
444 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
445 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
448 /* Calculates hash value for same_succ VE. */
451 same_succ_hash (const_same_succ e
)
453 hashval_t hashval
= bitmap_hash (e
->succs
);
456 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
457 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
459 gimple_stmt_iterator gsi
;
465 for (gsi
= gsi_start_nondebug_bb (bb
);
466 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
468 stmt
= gsi_stmt (gsi
);
469 stmt_update_dep_bb (stmt
);
470 if (stmt_local_def (stmt
))
474 hashval
= iterative_hash_hashval_t (gimple_code (stmt
), hashval
);
475 if (is_gimple_assign (stmt
))
476 hashval
= iterative_hash_hashval_t (gimple_assign_rhs_code (stmt
),
478 if (!is_gimple_call (stmt
))
480 if (gimple_call_internal_p (stmt
))
481 hashval
= iterative_hash_hashval_t
482 ((hashval_t
) gimple_call_internal_fn (stmt
), hashval
);
485 hashval
= iterative_hash_expr (gimple_call_fn (stmt
), hashval
);
486 if (gimple_call_chain (stmt
))
487 hashval
= iterative_hash_expr (gimple_call_chain (stmt
), hashval
);
489 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
491 arg
= gimple_call_arg (stmt
, i
);
492 arg
= vn_valueize (arg
);
493 hashval
= iterative_hash_expr (arg
, hashval
);
497 hashval
= iterative_hash_hashval_t (size
, hashval
);
500 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
502 flags
= e
->succ_flags
[i
];
503 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
504 hashval
= iterative_hash_hashval_t (flags
, hashval
);
507 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
509 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
510 for (gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
)); !gsi_end_p (gsi
);
513 gimple phi
= gsi_stmt (gsi
);
514 tree lhs
= gimple_phi_result (phi
);
515 tree val
= gimple_phi_arg_def (phi
, n
);
517 if (virtual_operand_p (lhs
))
519 update_dep_bb (bb
, val
);
526 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
527 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
528 the other edge flags. */
531 inverse_flags (const_same_succ e1
, const_same_succ e2
)
533 int f1a
, f1b
, f2a
, f2b
;
534 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
536 if (e1
->succ_flags
.length () != 2)
539 f1a
= e1
->succ_flags
[0];
540 f1b
= e1
->succ_flags
[1];
541 f2a
= e2
->succ_flags
[0];
542 f2b
= e2
->succ_flags
[1];
544 if (f1a
== f2a
&& f1b
== f2b
)
547 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
550 /* Compares SAME_SUCCs E1 and E2. */
553 same_succ_def::equal (const value_type
*e1
, const compare_type
*e2
)
555 unsigned int i
, first1
, first2
;
556 gimple_stmt_iterator gsi1
, gsi2
;
558 basic_block bb1
, bb2
;
560 if (e1
->hashval
!= e2
->hashval
)
563 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
566 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
569 if (!inverse_flags (e1
, e2
))
571 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
572 if (e1
->succ_flags
[i
] != e1
->succ_flags
[i
])
576 first1
= bitmap_first_set_bit (e1
->bbs
);
577 first2
= bitmap_first_set_bit (e2
->bbs
);
579 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
580 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
582 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
585 gsi1
= gsi_start_nondebug_bb (bb1
);
586 gsi2
= gsi_start_nondebug_bb (bb2
);
587 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
588 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
589 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
591 s1
= gsi_stmt (gsi1
);
592 s2
= gsi_stmt (gsi2
);
593 if (gimple_code (s1
) != gimple_code (s2
))
595 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
597 gsi_next_nondebug (&gsi1
);
598 gsi_next_nondebug (&gsi2
);
599 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
600 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
606 /* Alloc and init a new SAME_SUCC. */
609 same_succ_alloc (void)
611 same_succ same
= XNEW (struct same_succ_def
);
613 same
->bbs
= BITMAP_ALLOC (NULL
);
614 same
->succs
= BITMAP_ALLOC (NULL
);
615 same
->inverse
= BITMAP_ALLOC (NULL
);
616 same
->succ_flags
.create (10);
617 same
->in_worklist
= false;
622 /* Delete same_succ E. */
625 same_succ_def::remove (same_succ e
)
627 BITMAP_FREE (e
->bbs
);
628 BITMAP_FREE (e
->succs
);
629 BITMAP_FREE (e
->inverse
);
630 e
->succ_flags
.release ();
635 /* Reset same_succ SAME. */
638 same_succ_reset (same_succ same
)
640 bitmap_clear (same
->bbs
);
641 bitmap_clear (same
->succs
);
642 bitmap_clear (same
->inverse
);
643 same
->succ_flags
.truncate (0);
646 static hash_table
<same_succ_def
> same_succ_htab
;
648 /* Array that is used to store the edge flags for a successor. */
650 static int *same_succ_edge_flags
;
652 /* Bitmap that is used to mark bbs that are recently deleted. */
654 static bitmap deleted_bbs
;
656 /* Bitmap that is used to mark predecessors of bbs that are
659 static bitmap deleted_bb_preds
;
661 /* Prints same_succ_htab to stderr. */
663 extern void debug_same_succ (void);
665 debug_same_succ ( void)
667 same_succ_htab
.traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
671 /* Vector of bbs to process. */
673 static vec
<same_succ
> worklist
;
675 /* Prints worklist to FILE. */
678 print_worklist (FILE *file
)
681 for (i
= 0; i
< worklist
.length (); ++i
)
682 same_succ_print (file
, worklist
[i
]);
685 /* Adds SAME to worklist. */
688 add_to_worklist (same_succ same
)
690 if (same
->in_worklist
)
693 if (bitmap_count_bits (same
->bbs
) < 2)
696 same
->in_worklist
= true;
697 worklist
.safe_push (same
);
700 /* Add BB to same_succ_htab. */
703 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
707 same_succ same
= *same_p
;
713 /* Be conservative with loop structure. It's not evident that this test
714 is sufficient. Before tail-merge, we've just called
715 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
716 set, so there's no guarantee that the loop->latch value is still valid.
717 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
718 start of pre, we've kept that property intact throughout pre, and are
719 keeping it throughout tail-merge using this test. */
720 || bb
->loop_father
->latch
== bb
)
722 bitmap_set_bit (same
->bbs
, bb
->index
);
723 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
725 int index
= e
->dest
->index
;
726 bitmap_set_bit (same
->succs
, index
);
727 same_succ_edge_flags
[index
] = e
->flags
;
729 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
730 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
732 same
->hashval
= same_succ_hash (same
);
734 slot
= same_succ_htab
.find_slot_with_hash (same
, same
->hashval
, INSERT
);
738 BB_SAME_SUCC (bb
) = same
;
739 add_to_worklist (same
);
744 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
745 BB_SAME_SUCC (bb
) = *slot
;
746 add_to_worklist (*slot
);
747 if (inverse_flags (same
, *slot
))
748 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
749 same_succ_reset (same
);
753 /* Find bbs with same successors. */
756 find_same_succ (void)
758 same_succ same
= same_succ_alloc ();
761 FOR_EACH_BB_FN (bb
, cfun
)
763 find_same_succ_bb (bb
, &same
);
765 same
= same_succ_alloc ();
768 same_succ_def::remove (same
);
771 /* Initializes worklist administration. */
776 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
777 same_succ_htab
.create (n_basic_blocks_for_fn (cfun
));
778 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
779 deleted_bbs
= BITMAP_ALLOC (NULL
);
780 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
781 worklist
.create (n_basic_blocks_for_fn (cfun
));
784 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
786 fprintf (dump_file
, "initial worklist:\n");
787 print_worklist (dump_file
);
791 /* Deletes worklist administration. */
794 delete_worklist (void)
796 free_aux_for_blocks ();
797 same_succ_htab
.dispose ();
798 XDELETEVEC (same_succ_edge_flags
);
799 same_succ_edge_flags
= NULL
;
800 BITMAP_FREE (deleted_bbs
);
801 BITMAP_FREE (deleted_bb_preds
);
805 /* Mark BB as deleted, and mark its predecessors. */
808 mark_basic_block_deleted (basic_block bb
)
813 bitmap_set_bit (deleted_bbs
, bb
->index
);
815 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
816 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
819 /* Removes BB from its corresponding same_succ. */
822 same_succ_flush_bb (basic_block bb
)
824 same_succ same
= BB_SAME_SUCC (bb
);
825 BB_SAME_SUCC (bb
) = NULL
;
826 if (bitmap_single_bit_set_p (same
->bbs
))
827 same_succ_htab
.remove_elt_with_hash (same
, same
->hashval
);
829 bitmap_clear_bit (same
->bbs
, bb
->index
);
832 /* Removes all bbs in BBS from their corresponding same_succ. */
835 same_succ_flush_bbs (bitmap bbs
)
840 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
841 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
844 /* Release the last vdef in BB, either normal or phi result. */
847 release_last_vdef (basic_block bb
)
849 gimple_stmt_iterator i
;
851 for (i
= gsi_last_bb (bb
); !gsi_end_p (i
); gsi_prev_nondebug (&i
))
853 gimple stmt
= gsi_stmt (i
);
854 if (gimple_vdef (stmt
) == NULL_TREE
)
857 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
861 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
863 gimple phi
= gsi_stmt (i
);
864 tree res
= gimple_phi_result (phi
);
866 if (!virtual_operand_p (res
))
869 mark_virtual_phi_result_for_renaming (phi
);
875 /* For deleted_bb_preds, find bbs with same successors. */
878 update_worklist (void)
885 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
886 bitmap_clear (deleted_bbs
);
888 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
889 same_succ_flush_bbs (deleted_bb_preds
);
891 same
= same_succ_alloc ();
892 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
894 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
895 gcc_assert (bb
!= NULL
);
896 find_same_succ_bb (bb
, &same
);
898 same
= same_succ_alloc ();
900 same_succ_def::remove (same
);
901 bitmap_clear (deleted_bb_preds
);
904 /* Prints cluster C to FILE. */
907 print_cluster (FILE *file
, bb_cluster c
)
911 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
912 bitmap_print (file
, c
->preds
, "preds:", "\n");
915 /* Prints cluster C to stderr. */
917 extern void debug_cluster (bb_cluster
);
919 debug_cluster (bb_cluster c
)
921 print_cluster (stderr
, c
);
924 /* Update C->rep_bb, given that BB is added to the cluster. */
927 update_rep_bb (bb_cluster c
, basic_block bb
)
930 if (c
->rep_bb
== NULL
)
936 /* Current needs no deps, keep it. */
937 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
940 /* Bb needs no deps, change rep_bb. */
941 if (BB_DEP_BB (bb
) == NULL
)
947 /* Bb needs last deps earlier than current, change rep_bb. A potential
948 problem with this, is that the first deps might also be earlier, which
949 would mean we prefer longer lifetimes for the deps. To be able to check
950 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
951 BB_DEP_BB, which is really BB_LAST_DEP_BB.
952 The benefit of choosing the bb with last deps earlier, is that it can
953 potentially be used as replacement for more bbs. */
954 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
958 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
961 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
966 bitmap_set_bit (c
->bbs
, bb
->index
);
968 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
969 bitmap_set_bit (c
->preds
, e
->src
->index
);
971 update_rep_bb (c
, bb
);
974 /* Allocate and init new cluster. */
980 c
= XCNEW (struct bb_cluster_def
);
981 c
->bbs
= BITMAP_ALLOC (NULL
);
982 c
->preds
= BITMAP_ALLOC (NULL
);
987 /* Delete clusters. */
990 delete_cluster (bb_cluster c
)
994 BITMAP_FREE (c
->bbs
);
995 BITMAP_FREE (c
->preds
);
1000 /* Array that contains all clusters. */
1002 static vec
<bb_cluster
> all_clusters
;
1004 /* Allocate all cluster vectors. */
1007 alloc_cluster_vectors (void)
1009 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1012 /* Reset all cluster vectors. */
1015 reset_cluster_vectors (void)
1019 for (i
= 0; i
< all_clusters
.length (); ++i
)
1020 delete_cluster (all_clusters
[i
]);
1021 all_clusters
.truncate (0);
1022 FOR_EACH_BB_FN (bb
, cfun
)
1023 BB_CLUSTER (bb
) = NULL
;
1026 /* Delete all cluster vectors. */
1029 delete_cluster_vectors (void)
1032 for (i
= 0; i
< all_clusters
.length (); ++i
)
1033 delete_cluster (all_clusters
[i
]);
1034 all_clusters
.release ();
1037 /* Merge cluster C2 into C1. */
1040 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1042 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1043 bitmap_ior_into (c1
->preds
, c2
->preds
);
1046 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1047 all_clusters, or merge c with existing cluster. */
1050 set_cluster (basic_block bb1
, basic_block bb2
)
1052 basic_block merge_bb
, other_bb
;
1053 bb_cluster merge
, old
, c
;
1055 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1058 add_bb_to_cluster (c
, bb1
);
1059 add_bb_to_cluster (c
, bb2
);
1060 BB_CLUSTER (bb1
) = c
;
1061 BB_CLUSTER (bb2
) = c
;
1062 c
->index
= all_clusters
.length ();
1063 all_clusters
.safe_push (c
);
1065 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1067 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1068 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1069 merge
= BB_CLUSTER (merge_bb
);
1070 add_bb_to_cluster (merge
, other_bb
);
1071 BB_CLUSTER (other_bb
) = merge
;
1073 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1078 old
= BB_CLUSTER (bb2
);
1079 merge
= BB_CLUSTER (bb1
);
1080 merge_clusters (merge
, old
);
1081 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1082 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1083 all_clusters
[old
->index
] = NULL
;
1084 update_rep_bb (merge
, old
->rep_bb
);
1085 delete_cluster (old
);
1091 /* Return true if gimple operands T1 and T2 have the same value. */
1094 gimple_operand_equal_value_p (tree t1
, tree t2
)
1103 if (operand_equal_p (t1
, t2
, 0))
1106 return gvn_uses_equal (t1
, t2
);
1109 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1110 gimple_bb (s2) are members of SAME_SUCC. */
1113 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1117 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1120 enum tree_code code1
, code2
;
1122 if (gimple_code (s1
) != gimple_code (s2
))
1125 switch (gimple_code (s1
))
1128 if (!gimple_call_same_target_p (s1
, s2
))
1131 t1
= gimple_call_chain (s1
);
1132 t2
= gimple_call_chain (s2
);
1133 if (!gimple_operand_equal_value_p (t1
, t2
))
1136 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1139 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1141 t1
= gimple_call_arg (s1
, i
);
1142 t2
= gimple_call_arg (s2
, i
);
1143 if (!gimple_operand_equal_value_p (t1
, t2
))
1147 lhs1
= gimple_get_lhs (s1
);
1148 lhs2
= gimple_get_lhs (s2
);
1149 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1151 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1153 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1154 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1155 return operand_equal_p (lhs1
, lhs2
, 0);
1158 lhs1
= gimple_get_lhs (s1
);
1159 lhs2
= gimple_get_lhs (s2
);
1160 if (TREE_CODE (lhs1
) != SSA_NAME
1161 && TREE_CODE (lhs2
) != SSA_NAME
)
1162 return (operand_equal_p (lhs1
, lhs2
, 0)
1163 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1164 gimple_assign_rhs1 (s2
)));
1165 else if (TREE_CODE (lhs1
) == SSA_NAME
1166 && TREE_CODE (lhs2
) == SSA_NAME
)
1167 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1171 t1
= gimple_cond_lhs (s1
);
1172 t2
= gimple_cond_lhs (s2
);
1173 if (!gimple_operand_equal_value_p (t1
, t2
))
1176 t1
= gimple_cond_rhs (s1
);
1177 t2
= gimple_cond_rhs (s2
);
1178 if (!gimple_operand_equal_value_p (t1
, t2
))
1181 code1
= gimple_expr_code (s1
);
1182 code2
= gimple_expr_code (s2
);
1183 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1184 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1188 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1189 code2
= invert_tree_comparison (code2
, honor_nans
);
1191 return code1
== code2
;
1198 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1199 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1200 processed statements. */
1203 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1211 if (gsi_end_p (*gsi
))
1213 stmt
= gsi_stmt (*gsi
);
1215 lvuse
= gimple_vuse (stmt
);
1216 if (lvuse
!= NULL_TREE
)
1219 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1220 *vuse_escaped
= true;
1223 if (!stmt_local_def (stmt
))
1225 gsi_prev_nondebug (gsi
);
1229 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1233 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1235 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1236 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1237 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1238 bool vuse_escaped
= false;
1240 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1241 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1243 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1245 gimple stmt1
= gsi_stmt (gsi1
);
1246 gimple stmt2
= gsi_stmt (gsi2
);
1248 /* What could be better than to this this here is to blacklist the bb
1249 containing the stmt, when encountering the stmt f.i. in
1251 if (is_tm_ending (stmt1
)
1252 || is_tm_ending (stmt2
))
1255 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1258 gsi_prev_nondebug (&gsi1
);
1259 gsi_prev_nondebug (&gsi2
);
1260 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1261 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1264 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1267 /* If the incoming vuses are not the same, and the vuse escaped into an
1268 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1269 which potentially means the semantics of one of the blocks will be changed.
1270 TODO: make this check more precise. */
1271 if (vuse_escaped
&& vuse1
!= vuse2
)
1275 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1276 bb1
->index
, bb2
->index
);
1278 set_cluster (bb1
, bb2
);
1281 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1285 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1287 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1288 gimple_stmt_iterator gsi
;
1290 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1292 gimple phi
= gsi_stmt (gsi
);
1293 tree lhs
= gimple_phi_result (phi
);
1294 tree val1
= gimple_phi_arg_def (phi
, n1
);
1295 tree val2
= gimple_phi_arg_def (phi
, n2
);
1297 if (virtual_operand_p (lhs
))
1300 if (operand_equal_for_phi_arg_p (val1
, val2
))
1302 if (gvn_uses_equal (val1
, val2
))
1311 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1312 phi alternatives for BB1 and BB2 are equal. */
1315 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1322 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1324 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1325 e1
= find_edge (bb1
, succ
);
1326 e2
= find_edge (bb2
, succ
);
1327 if (e1
->flags
& EDGE_COMPLEX
1328 || e2
->flags
& EDGE_COMPLEX
)
1331 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1333 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1340 /* Return true if BB has non-vop phis. */
1343 bb_has_non_vop_phi (basic_block bb
)
1345 gimple_seq phis
= phi_nodes (bb
);
1351 if (!gimple_seq_singleton_p (phis
))
1354 phi
= gimple_seq_first_stmt (phis
);
1355 return !virtual_operand_p (gimple_phi_result (phi
));
1358 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1359 invariant that uses in FROM are dominates by their defs. */
1362 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1364 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1367 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1372 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1373 bitmap_set_bit (from_preds
, e
->src
->index
);
1374 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1375 BITMAP_FREE (from_preds
);
1377 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1380 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1381 replacement bb) and vice versa maintains the invariant that uses in the
1382 replacement are dominates by their defs. */
1385 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1387 if (BB_CLUSTER (bb1
) != NULL
)
1388 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1390 if (BB_CLUSTER (bb2
) != NULL
)
1391 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1393 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1394 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1397 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1400 find_clusters_1 (same_succ same_succ
)
1402 basic_block bb1
, bb2
;
1404 bitmap_iterator bi
, bj
;
1406 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1408 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1410 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1412 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1413 phi-nodes in bb1 and bb2, with the same alternatives for the same
1415 if (bb_has_non_vop_phi (bb1
))
1419 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1421 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1423 if (bb_has_non_vop_phi (bb2
))
1426 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1429 /* Limit quadratic behaviour. */
1431 if (nr_comparisons
> max_comparisons
)
1434 /* This is a conservative dependency check. We could test more
1435 precise for allowed replacement direction. */
1436 if (!deps_ok_for_redirect (bb1
, bb2
))
1439 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1442 find_duplicate (same_succ
, bb1
, bb2
);
1447 /* Find clusters of bbs which can be merged. */
1450 find_clusters (void)
1454 while (!worklist
.is_empty ())
1456 same
= worklist
.pop ();
1457 same
->in_worklist
= false;
1458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1460 fprintf (dump_file
, "processing worklist entry\n");
1461 same_succ_print (dump_file
, same
);
1463 find_clusters_1 (same
);
1467 /* Returns the vop phi of BB, if any. */
1470 vop_phi (basic_block bb
)
1473 gimple_stmt_iterator gsi
;
1474 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1476 stmt
= gsi_stmt (gsi
);
1477 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1484 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1487 replace_block_by (basic_block bb1
, basic_block bb2
)
1495 bb2_phi
= vop_phi (bb2
);
1497 /* Mark the basic block as deleted. */
1498 mark_basic_block_deleted (bb1
);
1500 /* Redirect the incoming edges of bb1 to bb2. */
1501 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1503 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1504 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1505 gcc_assert (pred_edge
!= NULL
);
1507 if (bb2_phi
== NULL
)
1510 /* The phi might have run out of capacity when the redirect added an
1511 argument, which means it could have been replaced. Refresh it. */
1512 bb2_phi
= vop_phi (bb2
);
1514 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1515 pred_edge
, UNKNOWN_LOCATION
);
1518 bb2
->frequency
+= bb1
->frequency
;
1519 if (bb2
->frequency
> BB_FREQ_MAX
)
1520 bb2
->frequency
= BB_FREQ_MAX
;
1522 bb2
->count
+= bb1
->count
;
1524 /* Merge the outgoing edge counts from bb1 onto bb2. */
1525 gcov_type out_sum
= 0;
1526 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1528 e2
= find_edge (bb2
, e1
->dest
);
1530 e2
->count
+= e1
->count
;
1531 out_sum
+= e2
->count
;
1533 /* Recompute the edge probabilities from the new merged edge count.
1534 Use the sum of the new merged edge counts computed above instead
1535 of bb2's merged count, in case there are profile count insanities
1536 making the bb count inconsistent with the edge weights. */
1537 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1539 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1542 /* Do updates that use bb1, before deleting bb1. */
1543 release_last_vdef (bb1
);
1544 same_succ_flush_bb (bb1
);
1546 delete_basic_block (bb1
);
1549 /* Bbs for which update_debug_stmt need to be called. */
1551 static bitmap update_bbs
;
1553 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1554 number of bbs removed. */
1557 apply_clusters (void)
1559 basic_block bb1
, bb2
;
1563 int nr_bbs_removed
= 0;
1565 for (i
= 0; i
< all_clusters
.length (); ++i
)
1567 c
= all_clusters
[i
];
1572 bitmap_set_bit (update_bbs
, bb2
->index
);
1574 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1575 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1577 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1578 bitmap_clear_bit (update_bbs
, bb1
->index
);
1580 replace_block_by (bb1
, bb2
);
1585 return nr_bbs_removed
;
1588 /* Resets debug statement STMT if it has uses that are not dominated by their
1592 update_debug_stmt (gimple stmt
)
1594 use_operand_p use_p
;
1596 basic_block bbdef
, bbuse
;
1600 if (!gimple_debug_bind_p (stmt
))
1603 bbuse
= gimple_bb (stmt
);
1604 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1606 name
= USE_FROM_PTR (use_p
);
1607 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1609 def_stmt
= SSA_NAME_DEF_STMT (name
);
1610 gcc_assert (def_stmt
!= NULL
);
1612 bbdef
= gimple_bb (def_stmt
);
1613 if (bbdef
== NULL
|| bbuse
== bbdef
1614 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1617 gimple_debug_bind_reset_value (stmt
);
1622 /* Resets all debug statements that have uses that are not
1623 dominated by their defs. */
1626 update_debug_stmts (void)
1632 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1635 gimple_stmt_iterator gsi
;
1637 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1638 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1640 stmt
= gsi_stmt (gsi
);
1641 if (!is_gimple_debug (stmt
))
1643 update_debug_stmt (stmt
);
1648 /* Runs tail merge optimization. */
1651 tail_merge_optimize (unsigned int todo
)
1653 int nr_bbs_removed_total
= 0;
1655 bool loop_entered
= false;
1656 int iteration_nr
= 0;
1657 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1659 if (!flag_tree_tail_merge
1660 || max_iterations
== 0
1661 /* We try to be conservative with respect to loop structure, since:
1662 - the cases where tail-merging could both affect loop structure and be
1663 beneficial are rare,
1664 - it prevents us from having to fixup the loops using
1665 loops_state_set (LOOPS_NEED_FIXUP), and
1666 - keeping loop structure may allow us to simplify the pass.
1667 In order to be conservative, we need loop information. In rare cases
1668 (about 7 test-cases in the g++ testsuite) there is none (because
1669 loop_optimizer_finalize has been called before tail-merge, and
1670 PROP_loops is not set), so we bail out. */
1671 || current_loops
== NULL
)
1674 timevar_push (TV_TREE_TAIL_MERGE
);
1676 if (!dom_info_available_p (CDI_DOMINATORS
))
1678 /* PRE can leave us with unreachable blocks, remove them now. */
1679 delete_unreachable_blocks ();
1680 calculate_dominance_info (CDI_DOMINATORS
);
1684 while (!worklist
.is_empty ())
1688 loop_entered
= true;
1689 alloc_cluster_vectors ();
1690 update_bbs
= BITMAP_ALLOC (NULL
);
1693 reset_cluster_vectors ();
1696 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1697 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1700 gcc_assert (worklist
.is_empty ());
1701 if (all_clusters
.is_empty ())
1704 nr_bbs_removed
= apply_clusters ();
1705 nr_bbs_removed_total
+= nr_bbs_removed
;
1706 if (nr_bbs_removed
== 0)
1709 free_dominance_info (CDI_DOMINATORS
);
1711 if (iteration_nr
== max_iterations
)
1714 calculate_dominance_info (CDI_DOMINATORS
);
1718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1719 fprintf (dump_file
, "htab collision / search: %f\n",
1720 same_succ_htab
.collisions ());
1722 if (nr_bbs_removed_total
> 0)
1724 if (MAY_HAVE_DEBUG_STMTS
)
1726 calculate_dominance_info (CDI_DOMINATORS
);
1727 update_debug_stmts ();
1730 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1732 fprintf (dump_file
, "Before TODOs.\n");
1733 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1736 todo
|= (TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow
);
1737 mark_virtual_operands_for_renaming (cfun
);
1743 delete_cluster_vectors ();
1744 BITMAP_FREE (update_bbs
);
1747 timevar_pop (TV_TREE_TAIL_MERGE
);