1 /* Tail merging for gimple.
2 Copyright (C) 2011-2016 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 "cfghooks.h"
195 #include "tree-pass.h"
197 #include "fold-const.h"
198 #include "trans-mem.h"
200 #include "cfgcleanup.h"
201 #include "gimple-iterator.h"
202 #include "tree-cfg.h"
203 #include "tree-into-ssa.h"
205 #include "tree-ssa-sccvn.h"
208 /* Describes a group of bbs with the same successors. The successor bbs are
209 cached in succs, and the successor edge flags are cached in succ_flags.
210 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
211 it's marked in inverse.
212 Additionally, the hash value for the struct is cached in hashval, and
213 in_worklist indicates whether it's currently part of worklist. */
215 struct same_succ
: pointer_hash
<same_succ
>
217 /* The bbs that have the same successor bbs. */
219 /* The successor bbs. */
221 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
224 /* The edge flags for each of the successor bbs. */
226 /* Indicates whether the struct is currently in the worklist. */
228 /* The hash value of the struct. */
231 /* hash_table support. */
232 static inline hashval_t
hash (const same_succ
*);
233 static int equal (const same_succ
*, const same_succ
*);
234 static void remove (same_succ
*);
237 /* hash routine for hash_table support, returns hashval of E. */
240 same_succ::hash (const same_succ
*e
)
245 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
249 /* The bbs in the cluster. */
251 /* The preds of the bbs in the cluster. */
253 /* Index in all_clusters vector. */
255 /* The bb to replace the cluster with. */
263 /* The number of non-debug statements in the bb. */
265 /* The same_succ that this bb is a member of. */
266 same_succ
*bb_same_succ
;
267 /* The cluster that this bb is a member of. */
269 /* The vop state at the exit of a bb. This is shortlived data, used to
270 communicate data between update_block_by and update_vuses. */
272 /* The bb that either contains or is dominated by the dependencies of the
277 /* Macros to access the fields of struct aux_bb_info. */
279 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
280 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
281 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
282 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
283 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
285 /* Returns true if the only effect a statement STMT has, is to define locally
289 stmt_local_def (gimple
*stmt
)
291 basic_block bb
, def_bb
;
292 imm_use_iterator iter
;
297 if (gimple_vdef (stmt
) != NULL_TREE
298 || gimple_has_side_effects (stmt
)
299 || gimple_could_trap_p_1 (stmt
, false, false)
300 || gimple_vuse (stmt
) != NULL_TREE
)
303 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
307 val
= DEF_FROM_PTR (def_p
);
308 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
311 def_bb
= gimple_bb (stmt
);
313 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
315 if (is_gimple_debug (USE_STMT (use_p
)))
317 bb
= gimple_bb (USE_STMT (use_p
));
321 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
322 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
331 /* Let GSI skip forwards over local defs. */
334 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
340 if (gsi_end_p (*gsi
))
342 stmt
= gsi_stmt (*gsi
);
343 if (!stmt_local_def (stmt
))
345 gsi_next_nondebug (gsi
);
349 /* VAL1 and VAL2 are either:
350 - uses in BB1 and BB2, or
351 - phi alternatives for BB1 and BB2.
352 Return true if the uses have the same gvn value. */
355 gvn_uses_equal (tree val1
, tree val2
)
357 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
362 if (vn_valueize (val1
) != vn_valueize (val2
))
365 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
366 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
369 /* Prints E to FILE. */
372 same_succ_print (FILE *file
, const same_succ
*e
)
375 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
376 bitmap_print (file
, e
->succs
, "succs:", "\n");
377 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
378 fprintf (file
, "flags:");
379 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
380 fprintf (file
, " %x", e
->succ_flags
[i
]);
381 fprintf (file
, "\n");
384 /* Prints same_succ VE to VFILE. */
387 ssa_same_succ_print_traverse (same_succ
**pe
, FILE *file
)
389 const same_succ
*e
= *pe
;
390 same_succ_print (file
, e
);
394 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
397 update_dep_bb (basic_block use_bb
, tree val
)
402 if (TREE_CODE (val
) != SSA_NAME
)
405 /* Skip use of global def. */
406 if (SSA_NAME_IS_DEFAULT_DEF (val
))
409 /* Skip use of local def. */
410 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
411 if (dep_bb
== use_bb
)
414 if (BB_DEP_BB (use_bb
) == NULL
415 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
416 BB_DEP_BB (use_bb
) = dep_bb
;
419 /* Update BB_DEP_BB, given the dependencies in STMT. */
422 stmt_update_dep_bb (gimple
*stmt
)
427 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
428 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
431 /* Calculates hash value for same_succ VE. */
434 same_succ_hash (const same_succ
*e
)
436 inchash::hash
hstate (bitmap_hash (e
->succs
));
439 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
440 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
447 for (gimple_stmt_iterator gsi
= gsi_start_nondebug_bb (bb
);
448 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
450 stmt
= gsi_stmt (gsi
);
451 stmt_update_dep_bb (stmt
);
452 if (stmt_local_def (stmt
))
456 hstate
.add_int (gimple_code (stmt
));
457 if (is_gimple_assign (stmt
))
458 hstate
.add_int (gimple_assign_rhs_code (stmt
));
459 if (!is_gimple_call (stmt
))
461 if (gimple_call_internal_p (stmt
))
462 hstate
.add_int (gimple_call_internal_fn (stmt
));
465 inchash::add_expr (gimple_call_fn (stmt
), hstate
);
466 if (gimple_call_chain (stmt
))
467 inchash::add_expr (gimple_call_chain (stmt
), hstate
);
469 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
471 arg
= gimple_call_arg (stmt
, i
);
472 arg
= vn_valueize (arg
);
473 inchash::add_expr (arg
, hstate
);
477 hstate
.add_int (size
);
480 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
482 flags
= e
->succ_flags
[i
];
483 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
484 hstate
.add_int (flags
);
487 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
489 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
490 for (gphi_iterator gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
));
494 gphi
*phi
= gsi
.phi ();
495 tree lhs
= gimple_phi_result (phi
);
496 tree val
= gimple_phi_arg_def (phi
, n
);
498 if (virtual_operand_p (lhs
))
500 update_dep_bb (bb
, val
);
504 return hstate
.end ();
507 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
508 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
509 the other edge flags. */
512 inverse_flags (const same_succ
*e1
, const same_succ
*e2
)
514 int f1a
, f1b
, f2a
, f2b
;
515 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
517 if (e1
->succ_flags
.length () != 2)
520 f1a
= e1
->succ_flags
[0];
521 f1b
= e1
->succ_flags
[1];
522 f2a
= e2
->succ_flags
[0];
523 f2b
= e2
->succ_flags
[1];
525 if (f1a
== f2a
&& f1b
== f2b
)
528 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
531 /* Compares SAME_SUCCs E1 and E2. */
534 same_succ::equal (const same_succ
*e1
, const same_succ
*e2
)
536 unsigned int i
, first1
, first2
;
537 gimple_stmt_iterator gsi1
, gsi2
;
539 basic_block bb1
, bb2
;
544 if (e1
->hashval
!= e2
->hashval
)
547 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
550 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
553 if (!inverse_flags (e1
, e2
))
555 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
556 if (e1
->succ_flags
[i
] != e2
->succ_flags
[i
])
560 first1
= bitmap_first_set_bit (e1
->bbs
);
561 first2
= bitmap_first_set_bit (e2
->bbs
);
563 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
564 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
566 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
569 gsi1
= gsi_start_nondebug_bb (bb1
);
570 gsi2
= gsi_start_nondebug_bb (bb2
);
571 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
572 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
573 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
575 s1
= gsi_stmt (gsi1
);
576 s2
= gsi_stmt (gsi2
);
577 if (gimple_code (s1
) != gimple_code (s2
))
579 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
581 gsi_next_nondebug (&gsi1
);
582 gsi_next_nondebug (&gsi2
);
583 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
584 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
590 /* Alloc and init a new SAME_SUCC. */
593 same_succ_alloc (void)
595 same_succ
*same
= XNEW (struct same_succ
);
597 same
->bbs
= BITMAP_ALLOC (NULL
);
598 same
->succs
= BITMAP_ALLOC (NULL
);
599 same
->inverse
= BITMAP_ALLOC (NULL
);
600 same
->succ_flags
.create (10);
601 same
->in_worklist
= false;
606 /* Delete same_succ E. */
609 same_succ::remove (same_succ
*e
)
611 BITMAP_FREE (e
->bbs
);
612 BITMAP_FREE (e
->succs
);
613 BITMAP_FREE (e
->inverse
);
614 e
->succ_flags
.release ();
619 /* Reset same_succ SAME. */
622 same_succ_reset (same_succ
*same
)
624 bitmap_clear (same
->bbs
);
625 bitmap_clear (same
->succs
);
626 bitmap_clear (same
->inverse
);
627 same
->succ_flags
.truncate (0);
630 static hash_table
<same_succ
> *same_succ_htab
;
632 /* Array that is used to store the edge flags for a successor. */
634 static int *same_succ_edge_flags
;
636 /* Bitmap that is used to mark bbs that are recently deleted. */
638 static bitmap deleted_bbs
;
640 /* Bitmap that is used to mark predecessors of bbs that are
643 static bitmap deleted_bb_preds
;
645 /* Prints same_succ_htab to stderr. */
647 extern void debug_same_succ (void);
649 debug_same_succ ( void)
651 same_succ_htab
->traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
655 /* Vector of bbs to process. */
657 static vec
<same_succ
*> worklist
;
659 /* Prints worklist to FILE. */
662 print_worklist (FILE *file
)
665 for (i
= 0; i
< worklist
.length (); ++i
)
666 same_succ_print (file
, worklist
[i
]);
669 /* Adds SAME to worklist. */
672 add_to_worklist (same_succ
*same
)
674 if (same
->in_worklist
)
677 if (bitmap_count_bits (same
->bbs
) < 2)
680 same
->in_worklist
= true;
681 worklist
.safe_push (same
);
684 /* Add BB to same_succ_htab. */
687 find_same_succ_bb (basic_block bb
, same_succ
**same_p
)
691 same_succ
*same
= *same_p
;
697 /* Be conservative with loop structure. It's not evident that this test
698 is sufficient. Before tail-merge, we've just called
699 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
700 set, so there's no guarantee that the loop->latch value is still valid.
701 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
702 start of pre, we've kept that property intact throughout pre, and are
703 keeping it throughout tail-merge using this test. */
704 || bb
->loop_father
->latch
== bb
)
706 bitmap_set_bit (same
->bbs
, bb
->index
);
707 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
709 int index
= e
->dest
->index
;
710 bitmap_set_bit (same
->succs
, index
);
711 same_succ_edge_flags
[index
] = e
->flags
;
713 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
714 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
716 same
->hashval
= same_succ_hash (same
);
718 slot
= same_succ_htab
->find_slot_with_hash (same
, same
->hashval
, INSERT
);
722 BB_SAME_SUCC (bb
) = same
;
723 add_to_worklist (same
);
728 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
729 BB_SAME_SUCC (bb
) = *slot
;
730 add_to_worklist (*slot
);
731 if (inverse_flags (same
, *slot
))
732 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
733 same_succ_reset (same
);
737 /* Find bbs with same successors. */
740 find_same_succ (void)
742 same_succ
*same
= same_succ_alloc ();
745 FOR_EACH_BB_FN (bb
, cfun
)
747 find_same_succ_bb (bb
, &same
);
749 same
= same_succ_alloc ();
752 same_succ::remove (same
);
755 /* Initializes worklist administration. */
760 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
761 same_succ_htab
= new hash_table
<same_succ
> (n_basic_blocks_for_fn (cfun
));
762 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
763 deleted_bbs
= BITMAP_ALLOC (NULL
);
764 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
765 worklist
.create (n_basic_blocks_for_fn (cfun
));
768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
770 fprintf (dump_file
, "initial worklist:\n");
771 print_worklist (dump_file
);
775 /* Deletes worklist administration. */
778 delete_worklist (void)
780 free_aux_for_blocks ();
781 delete same_succ_htab
;
782 same_succ_htab
= NULL
;
783 XDELETEVEC (same_succ_edge_flags
);
784 same_succ_edge_flags
= NULL
;
785 BITMAP_FREE (deleted_bbs
);
786 BITMAP_FREE (deleted_bb_preds
);
790 /* Mark BB as deleted, and mark its predecessors. */
793 mark_basic_block_deleted (basic_block bb
)
798 bitmap_set_bit (deleted_bbs
, bb
->index
);
800 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
801 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
804 /* Removes BB from its corresponding same_succ. */
807 same_succ_flush_bb (basic_block bb
)
809 same_succ
*same
= BB_SAME_SUCC (bb
);
810 BB_SAME_SUCC (bb
) = NULL
;
811 if (bitmap_single_bit_set_p (same
->bbs
))
812 same_succ_htab
->remove_elt_with_hash (same
, same
->hashval
);
814 bitmap_clear_bit (same
->bbs
, bb
->index
);
817 /* Removes all bbs in BBS from their corresponding same_succ. */
820 same_succ_flush_bbs (bitmap bbs
)
825 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
826 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
829 /* Release the last vdef in BB, either normal or phi result. */
832 release_last_vdef (basic_block bb
)
834 for (gimple_stmt_iterator i
= gsi_last_bb (bb
); !gsi_end_p (i
);
835 gsi_prev_nondebug (&i
))
837 gimple
*stmt
= gsi_stmt (i
);
838 if (gimple_vdef (stmt
) == NULL_TREE
)
841 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
845 for (gphi_iterator i
= gsi_start_phis (bb
); !gsi_end_p (i
);
848 gphi
*phi
= i
.phi ();
849 tree res
= gimple_phi_result (phi
);
851 if (!virtual_operand_p (res
))
854 mark_virtual_phi_result_for_renaming (phi
);
859 /* For deleted_bb_preds, find bbs with same successors. */
862 update_worklist (void)
869 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
870 bitmap_clear (deleted_bbs
);
872 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
873 same_succ_flush_bbs (deleted_bb_preds
);
875 same
= same_succ_alloc ();
876 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
878 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
879 gcc_assert (bb
!= NULL
);
880 find_same_succ_bb (bb
, &same
);
882 same
= same_succ_alloc ();
884 same_succ::remove (same
);
885 bitmap_clear (deleted_bb_preds
);
888 /* Prints cluster C to FILE. */
891 print_cluster (FILE *file
, bb_cluster
*c
)
895 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
896 bitmap_print (file
, c
->preds
, "preds:", "\n");
899 /* Prints cluster C to stderr. */
901 extern void debug_cluster (bb_cluster
*);
903 debug_cluster (bb_cluster
*c
)
905 print_cluster (stderr
, c
);
908 /* Update C->rep_bb, given that BB is added to the cluster. */
911 update_rep_bb (bb_cluster
*c
, basic_block bb
)
914 if (c
->rep_bb
== NULL
)
920 /* Current needs no deps, keep it. */
921 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
924 /* Bb needs no deps, change rep_bb. */
925 if (BB_DEP_BB (bb
) == NULL
)
931 /* Bb needs last deps earlier than current, change rep_bb. A potential
932 problem with this, is that the first deps might also be earlier, which
933 would mean we prefer longer lifetimes for the deps. To be able to check
934 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
935 BB_DEP_BB, which is really BB_LAST_DEP_BB.
936 The benefit of choosing the bb with last deps earlier, is that it can
937 potentially be used as replacement for more bbs. */
938 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
942 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
945 add_bb_to_cluster (bb_cluster
*c
, basic_block bb
)
950 bitmap_set_bit (c
->bbs
, bb
->index
);
952 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
953 bitmap_set_bit (c
->preds
, e
->src
->index
);
955 update_rep_bb (c
, bb
);
958 /* Allocate and init new cluster. */
964 c
= XCNEW (bb_cluster
);
965 c
->bbs
= BITMAP_ALLOC (NULL
);
966 c
->preds
= BITMAP_ALLOC (NULL
);
971 /* Delete clusters. */
974 delete_cluster (bb_cluster
*c
)
978 BITMAP_FREE (c
->bbs
);
979 BITMAP_FREE (c
->preds
);
984 /* Array that contains all clusters. */
986 static vec
<bb_cluster
*> all_clusters
;
988 /* Allocate all cluster vectors. */
991 alloc_cluster_vectors (void)
993 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
996 /* Reset all cluster vectors. */
999 reset_cluster_vectors (void)
1003 for (i
= 0; i
< all_clusters
.length (); ++i
)
1004 delete_cluster (all_clusters
[i
]);
1005 all_clusters
.truncate (0);
1006 FOR_EACH_BB_FN (bb
, cfun
)
1007 BB_CLUSTER (bb
) = NULL
;
1010 /* Delete all cluster vectors. */
1013 delete_cluster_vectors (void)
1016 for (i
= 0; i
< all_clusters
.length (); ++i
)
1017 delete_cluster (all_clusters
[i
]);
1018 all_clusters
.release ();
1021 /* Merge cluster C2 into C1. */
1024 merge_clusters (bb_cluster
*c1
, bb_cluster
*c2
)
1026 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1027 bitmap_ior_into (c1
->preds
, c2
->preds
);
1030 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1031 all_clusters, or merge c with existing cluster. */
1034 set_cluster (basic_block bb1
, basic_block bb2
)
1036 basic_block merge_bb
, other_bb
;
1037 bb_cluster
*merge
, *old
, *c
;
1039 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1042 add_bb_to_cluster (c
, bb1
);
1043 add_bb_to_cluster (c
, bb2
);
1044 BB_CLUSTER (bb1
) = c
;
1045 BB_CLUSTER (bb2
) = c
;
1046 c
->index
= all_clusters
.length ();
1047 all_clusters
.safe_push (c
);
1049 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1051 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1052 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1053 merge
= BB_CLUSTER (merge_bb
);
1054 add_bb_to_cluster (merge
, other_bb
);
1055 BB_CLUSTER (other_bb
) = merge
;
1057 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1062 old
= BB_CLUSTER (bb2
);
1063 merge
= BB_CLUSTER (bb1
);
1064 merge_clusters (merge
, old
);
1065 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1066 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1067 all_clusters
[old
->index
] = NULL
;
1068 update_rep_bb (merge
, old
->rep_bb
);
1069 delete_cluster (old
);
1075 /* Return true if gimple operands T1 and T2 have the same value. */
1078 gimple_operand_equal_value_p (tree t1
, tree t2
)
1087 if (operand_equal_p (t1
, t2
, OEP_MATCH_SIDE_EFFECTS
))
1090 return gvn_uses_equal (t1
, t2
);
1093 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1094 gimple_bb (s2) are members of SAME_SUCC. */
1097 gimple_equal_p (same_succ
*same_succ
, gimple
*s1
, gimple
*s2
)
1101 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1104 enum tree_code code1
, code2
;
1106 if (gimple_code (s1
) != gimple_code (s2
))
1109 switch (gimple_code (s1
))
1112 if (!gimple_call_same_target_p (s1
, s2
))
1115 t1
= gimple_call_chain (s1
);
1116 t2
= gimple_call_chain (s2
);
1117 if (!gimple_operand_equal_value_p (t1
, t2
))
1120 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1123 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1125 t1
= gimple_call_arg (s1
, i
);
1126 t2
= gimple_call_arg (s2
, i
);
1127 if (!gimple_operand_equal_value_p (t1
, t2
))
1131 lhs1
= gimple_get_lhs (s1
);
1132 lhs2
= gimple_get_lhs (s2
);
1133 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1135 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1137 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1138 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1139 return operand_equal_p (lhs1
, lhs2
, 0);
1142 lhs1
= gimple_get_lhs (s1
);
1143 lhs2
= gimple_get_lhs (s2
);
1144 if (TREE_CODE (lhs1
) != SSA_NAME
1145 && TREE_CODE (lhs2
) != SSA_NAME
)
1146 return (operand_equal_p (lhs1
, lhs2
, 0)
1147 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1148 gimple_assign_rhs1 (s2
)));
1149 else if (TREE_CODE (lhs1
) == SSA_NAME
1150 && TREE_CODE (lhs2
) == SSA_NAME
)
1151 return operand_equal_p (gimple_assign_rhs1 (s1
),
1152 gimple_assign_rhs1 (s2
), 0);
1156 t1
= gimple_cond_lhs (s1
);
1157 t2
= gimple_cond_lhs (s2
);
1158 if (!gimple_operand_equal_value_p (t1
, t2
))
1161 t1
= gimple_cond_rhs (s1
);
1162 t2
= gimple_cond_rhs (s2
);
1163 if (!gimple_operand_equal_value_p (t1
, t2
))
1166 code1
= gimple_expr_code (s1
);
1167 code2
= gimple_expr_code (s2
);
1168 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1169 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1172 bool honor_nans
= HONOR_NANS (t1
);
1173 code2
= invert_tree_comparison (code2
, honor_nans
);
1175 return code1
== code2
;
1182 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1183 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1184 processed statements. */
1187 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1195 if (gsi_end_p (*gsi
))
1197 stmt
= gsi_stmt (*gsi
);
1199 lvuse
= gimple_vuse (stmt
);
1200 if (lvuse
!= NULL_TREE
)
1203 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1204 *vuse_escaped
= true;
1207 if (!stmt_local_def (stmt
))
1209 gsi_prev_nondebug (gsi
);
1213 /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1214 STMT2 are allowed to be merged. */
1217 merge_stmts_p (gimple
*stmt1
, gimple
*stmt2
)
1219 /* What could be better than this here is to blacklist the bb
1220 containing the stmt, when encountering the stmt f.i. in
1222 if (is_tm_ending (stmt1
))
1225 if (is_gimple_call (stmt1
)
1226 && gimple_call_internal_p (stmt1
))
1227 switch (gimple_call_internal_fn (stmt1
))
1229 case IFN_UBSAN_NULL
:
1230 case IFN_UBSAN_BOUNDS
:
1231 case IFN_UBSAN_VPTR
:
1232 case IFN_UBSAN_CHECK_ADD
:
1233 case IFN_UBSAN_CHECK_SUB
:
1234 case IFN_UBSAN_CHECK_MUL
:
1235 case IFN_UBSAN_OBJECT_SIZE
:
1236 case IFN_ASAN_CHECK
:
1237 /* For these internal functions, gimple_location is an implicit
1238 parameter, which will be used explicitly after expansion.
1239 Merging these statements may cause confusing line numbers in
1240 sanitizer messages. */
1241 return gimple_location (stmt1
) == gimple_location (stmt2
);
1249 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1253 find_duplicate (same_succ
*same_succ
, basic_block bb1
, basic_block bb2
)
1255 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1256 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1257 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1258 bool vuse_escaped
= false;
1260 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1261 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1263 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1265 gimple
*stmt1
= gsi_stmt (gsi1
);
1266 gimple
*stmt2
= gsi_stmt (gsi2
);
1268 if (gimple_code (stmt1
) == GIMPLE_LABEL
1269 && gimple_code (stmt2
) == GIMPLE_LABEL
)
1272 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1275 if (!merge_stmts_p (stmt1
, stmt2
))
1278 gsi_prev_nondebug (&gsi1
);
1279 gsi_prev_nondebug (&gsi2
);
1280 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1281 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1284 while (!gsi_end_p (gsi1
) && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1286 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi1
)));
1287 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
1291 while (!gsi_end_p (gsi2
) && gimple_code (gsi_stmt (gsi2
)) == GIMPLE_LABEL
)
1293 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi2
)));
1294 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
1298 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1301 /* If the incoming vuses are not the same, and the vuse escaped into an
1302 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1303 which potentially means the semantics of one of the blocks will be changed.
1304 TODO: make this check more precise. */
1305 if (vuse_escaped
&& vuse1
!= vuse2
)
1309 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1310 bb1
->index
, bb2
->index
);
1312 set_cluster (bb1
, bb2
);
1315 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1319 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1321 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1324 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1326 gphi
*phi
= gsi
.phi ();
1327 tree lhs
= gimple_phi_result (phi
);
1328 tree val1
= gimple_phi_arg_def (phi
, n1
);
1329 tree val2
= gimple_phi_arg_def (phi
, n2
);
1331 if (virtual_operand_p (lhs
))
1334 if (operand_equal_for_phi_arg_p (val1
, val2
))
1336 if (gvn_uses_equal (val1
, val2
))
1345 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1346 phi alternatives for BB1 and BB2 are equal. */
1349 same_phi_alternatives (same_succ
*same_succ
, basic_block bb1
, basic_block bb2
)
1356 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1358 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1359 e1
= find_edge (bb1
, succ
);
1360 e2
= find_edge (bb2
, succ
);
1361 if (e1
->flags
& EDGE_COMPLEX
1362 || e2
->flags
& EDGE_COMPLEX
)
1365 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1367 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1374 /* Return true if BB has non-vop phis. */
1377 bb_has_non_vop_phi (basic_block bb
)
1379 gimple_seq phis
= phi_nodes (bb
);
1385 if (!gimple_seq_singleton_p (phis
))
1388 phi
= gimple_seq_first_stmt (phis
);
1389 return !virtual_operand_p (gimple_phi_result (phi
));
1392 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1393 invariant that uses in FROM are dominates by their defs. */
1396 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1398 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1401 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1406 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1407 bitmap_set_bit (from_preds
, e
->src
->index
);
1408 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1409 BITMAP_FREE (from_preds
);
1411 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1414 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1415 replacement bb) and vice versa maintains the invariant that uses in the
1416 replacement are dominates by their defs. */
1419 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1421 if (BB_CLUSTER (bb1
) != NULL
)
1422 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1424 if (BB_CLUSTER (bb2
) != NULL
)
1425 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1427 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1428 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1431 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1434 find_clusters_1 (same_succ
*same_succ
)
1436 basic_block bb1
, bb2
;
1438 bitmap_iterator bi
, bj
;
1440 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1442 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1444 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1446 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1447 phi-nodes in bb1 and bb2, with the same alternatives for the same
1449 if (bb_has_non_vop_phi (bb1
))
1453 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1455 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1457 if (bb_has_non_vop_phi (bb2
))
1460 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1463 /* Limit quadratic behavior. */
1465 if (nr_comparisons
> max_comparisons
)
1468 /* This is a conservative dependency check. We could test more
1469 precise for allowed replacement direction. */
1470 if (!deps_ok_for_redirect (bb1
, bb2
))
1473 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1476 find_duplicate (same_succ
, bb1
, bb2
);
1481 /* Find clusters of bbs which can be merged. */
1484 find_clusters (void)
1488 while (!worklist
.is_empty ())
1490 same
= worklist
.pop ();
1491 same
->in_worklist
= false;
1492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1494 fprintf (dump_file
, "processing worklist entry\n");
1495 same_succ_print (dump_file
, same
);
1497 find_clusters_1 (same
);
1501 /* Returns the vop phi of BB, if any. */
1504 vop_phi (basic_block bb
)
1508 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1511 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1518 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1521 replace_block_by (basic_block bb1
, basic_block bb2
)
1529 bb2_phi
= vop_phi (bb2
);
1531 /* Mark the basic block as deleted. */
1532 mark_basic_block_deleted (bb1
);
1534 /* Redirect the incoming edges of bb1 to bb2. */
1535 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1537 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1538 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1539 gcc_assert (pred_edge
!= NULL
);
1541 if (bb2_phi
== NULL
)
1544 /* The phi might have run out of capacity when the redirect added an
1545 argument, which means it could have been replaced. Refresh it. */
1546 bb2_phi
= vop_phi (bb2
);
1548 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1549 pred_edge
, UNKNOWN_LOCATION
);
1552 bb2
->frequency
+= bb1
->frequency
;
1553 if (bb2
->frequency
> BB_FREQ_MAX
)
1554 bb2
->frequency
= BB_FREQ_MAX
;
1556 bb2
->count
+= bb1
->count
;
1558 /* Merge the outgoing edge counts from bb1 onto bb2. */
1559 gcov_type out_sum
= 0;
1560 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1562 e2
= find_edge (bb2
, e1
->dest
);
1564 e2
->count
+= e1
->count
;
1565 out_sum
+= e2
->count
;
1567 /* Recompute the edge probabilities from the new merged edge count.
1568 Use the sum of the new merged edge counts computed above instead
1569 of bb2's merged count, in case there are profile count insanities
1570 making the bb count inconsistent with the edge weights. */
1571 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1573 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1576 /* Move over any user labels from bb1 after the bb2 labels. */
1577 gimple_stmt_iterator gsi1
= gsi_start_bb (bb1
);
1578 if (!gsi_end_p (gsi1
) && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1580 gimple_stmt_iterator gsi2
= gsi_after_labels (bb2
);
1581 while (!gsi_end_p (gsi1
)
1582 && gimple_code (gsi_stmt (gsi1
)) == GIMPLE_LABEL
)
1584 tree label
= gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi1
)));
1585 gcc_assert (!DECL_NONLOCAL (label
) && !FORCED_LABEL (label
));
1586 if (DECL_ARTIFICIAL (label
))
1589 gsi_move_before (&gsi1
, &gsi2
);
1593 /* Clear range info from all stmts in BB2 -- this transformation
1594 could make them out of date. */
1595 reset_flow_sensitive_info_in_bb (bb2
);
1597 /* Do updates that use bb1, before deleting bb1. */
1598 release_last_vdef (bb1
);
1599 same_succ_flush_bb (bb1
);
1601 delete_basic_block (bb1
);
1604 /* Bbs for which update_debug_stmt need to be called. */
1606 static bitmap update_bbs
;
1608 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1609 number of bbs removed. */
1612 apply_clusters (void)
1614 basic_block bb1
, bb2
;
1618 int nr_bbs_removed
= 0;
1620 for (i
= 0; i
< all_clusters
.length (); ++i
)
1622 c
= all_clusters
[i
];
1627 bitmap_set_bit (update_bbs
, bb2
->index
);
1629 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1630 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1632 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1633 bitmap_clear_bit (update_bbs
, bb1
->index
);
1635 replace_block_by (bb1
, bb2
);
1640 return nr_bbs_removed
;
1643 /* Resets debug statement STMT if it has uses that are not dominated by their
1647 update_debug_stmt (gimple
*stmt
)
1649 use_operand_p use_p
;
1653 if (!gimple_debug_bind_p (stmt
))
1656 bbuse
= gimple_bb (stmt
);
1657 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1659 tree name
= USE_FROM_PTR (use_p
);
1660 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1661 basic_block bbdef
= gimple_bb (def_stmt
);
1662 if (bbdef
== NULL
|| bbuse
== bbdef
1663 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1666 gimple_debug_bind_reset_value (stmt
);
1672 /* Resets all debug statements that have uses that are not
1673 dominated by their defs. */
1676 update_debug_stmts (void)
1682 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1685 gimple_stmt_iterator gsi
;
1687 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1688 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1690 stmt
= gsi_stmt (gsi
);
1691 if (!is_gimple_debug (stmt
))
1693 update_debug_stmt (stmt
);
1698 /* Runs tail merge optimization. */
1701 tail_merge_optimize (unsigned int todo
)
1703 int nr_bbs_removed_total
= 0;
1705 bool loop_entered
= false;
1706 int iteration_nr
= 0;
1707 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1709 if (!flag_tree_tail_merge
1710 || max_iterations
== 0)
1713 timevar_push (TV_TREE_TAIL_MERGE
);
1715 if (!dom_info_available_p (CDI_DOMINATORS
))
1717 /* PRE can leave us with unreachable blocks, remove them now. */
1718 delete_unreachable_blocks ();
1719 calculate_dominance_info (CDI_DOMINATORS
);
1723 while (!worklist
.is_empty ())
1727 loop_entered
= true;
1728 alloc_cluster_vectors ();
1729 update_bbs
= BITMAP_ALLOC (NULL
);
1732 reset_cluster_vectors ();
1735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1736 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1739 gcc_assert (worklist
.is_empty ());
1740 if (all_clusters
.is_empty ())
1743 nr_bbs_removed
= apply_clusters ();
1744 nr_bbs_removed_total
+= nr_bbs_removed
;
1745 if (nr_bbs_removed
== 0)
1748 free_dominance_info (CDI_DOMINATORS
);
1750 if (iteration_nr
== max_iterations
)
1753 calculate_dominance_info (CDI_DOMINATORS
);
1757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 fprintf (dump_file
, "htab collision / search: %f\n",
1759 same_succ_htab
->collisions ());
1761 if (nr_bbs_removed_total
> 0)
1763 if (MAY_HAVE_DEBUG_STMTS
)
1765 calculate_dominance_info (CDI_DOMINATORS
);
1766 update_debug_stmts ();
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1771 fprintf (dump_file
, "Before TODOs.\n");
1772 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1775 mark_virtual_operands_for_renaming (cfun
);
1781 delete_cluster_vectors ();
1782 BITMAP_FREE (update_bbs
);
1785 timevar_pop (TV_TREE_TAIL_MERGE
);