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_has_side_effects (stmt
)
316 || stmt_could_throw_p (stmt
)
317 || gimple_vdef (stmt
) != NULL_TREE
)
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
)
1163 /* If the vdef is the same, it's the same statement. */
1164 if (vn_valueize (gimple_vdef (s1
))
1165 == vn_valueize (gimple_vdef (s2
)))
1168 /* Test for structural equality. */
1169 return (operand_equal_p (lhs1
, lhs2
, 0)
1170 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1171 gimple_assign_rhs1 (s2
)));
1173 else if (TREE_CODE (lhs1
) == SSA_NAME
1174 && TREE_CODE (lhs2
) == SSA_NAME
)
1175 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1179 t1
= gimple_cond_lhs (s1
);
1180 t2
= gimple_cond_lhs (s2
);
1181 if (!gimple_operand_equal_value_p (t1
, t2
))
1184 t1
= gimple_cond_rhs (s1
);
1185 t2
= gimple_cond_rhs (s2
);
1186 if (!gimple_operand_equal_value_p (t1
, t2
))
1189 code1
= gimple_expr_code (s1
);
1190 code2
= gimple_expr_code (s2
);
1191 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1192 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1196 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1197 code2
= invert_tree_comparison (code2
, honor_nans
);
1199 return code1
== code2
;
1206 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1207 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1208 processed statements. */
1211 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1219 if (gsi_end_p (*gsi
))
1221 stmt
= gsi_stmt (*gsi
);
1223 lvuse
= gimple_vuse (stmt
);
1224 if (lvuse
!= NULL_TREE
)
1227 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1228 *vuse_escaped
= true;
1231 if (!stmt_local_def (stmt
))
1233 gsi_prev_nondebug (gsi
);
1237 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1241 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1243 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1244 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1245 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1246 bool vuse_escaped
= false;
1248 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1249 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1251 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1253 gimple stmt1
= gsi_stmt (gsi1
);
1254 gimple stmt2
= gsi_stmt (gsi2
);
1256 /* What could be better than to this this here is to blacklist the bb
1257 containing the stmt, when encountering the stmt f.i. in
1259 if (is_tm_ending (stmt1
)
1260 || is_tm_ending (stmt2
))
1263 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1266 gsi_prev_nondebug (&gsi1
);
1267 gsi_prev_nondebug (&gsi2
);
1268 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1269 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1272 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1275 /* If the incoming vuses are not the same, and the vuse escaped into an
1276 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1277 which potentially means the semantics of one of the blocks will be changed.
1278 TODO: make this check more precise. */
1279 if (vuse_escaped
&& vuse1
!= vuse2
)
1283 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1284 bb1
->index
, bb2
->index
);
1286 set_cluster (bb1
, bb2
);
1289 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1293 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1295 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1296 gimple_stmt_iterator gsi
;
1298 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1300 gimple phi
= gsi_stmt (gsi
);
1301 tree lhs
= gimple_phi_result (phi
);
1302 tree val1
= gimple_phi_arg_def (phi
, n1
);
1303 tree val2
= gimple_phi_arg_def (phi
, n2
);
1305 if (virtual_operand_p (lhs
))
1308 if (operand_equal_for_phi_arg_p (val1
, val2
))
1310 if (gvn_uses_equal (val1
, val2
))
1319 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1320 phi alternatives for BB1 and BB2 are equal. */
1323 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1330 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1332 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1333 e1
= find_edge (bb1
, succ
);
1334 e2
= find_edge (bb2
, succ
);
1335 if (e1
->flags
& EDGE_COMPLEX
1336 || e2
->flags
& EDGE_COMPLEX
)
1339 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1341 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1348 /* Return true if BB has non-vop phis. */
1351 bb_has_non_vop_phi (basic_block bb
)
1353 gimple_seq phis
= phi_nodes (bb
);
1359 if (!gimple_seq_singleton_p (phis
))
1362 phi
= gimple_seq_first_stmt (phis
);
1363 return !virtual_operand_p (gimple_phi_result (phi
));
1366 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1367 invariant that uses in FROM are dominates by their defs. */
1370 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1372 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1375 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1380 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1381 bitmap_set_bit (from_preds
, e
->src
->index
);
1382 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1383 BITMAP_FREE (from_preds
);
1385 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1388 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1389 replacement bb) and vice versa maintains the invariant that uses in the
1390 replacement are dominates by their defs. */
1393 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1395 if (BB_CLUSTER (bb1
) != NULL
)
1396 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1398 if (BB_CLUSTER (bb2
) != NULL
)
1399 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1401 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1402 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1405 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1408 find_clusters_1 (same_succ same_succ
)
1410 basic_block bb1
, bb2
;
1412 bitmap_iterator bi
, bj
;
1414 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1416 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1418 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1420 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1421 phi-nodes in bb1 and bb2, with the same alternatives for the same
1423 if (bb_has_non_vop_phi (bb1
))
1427 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1429 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1431 if (bb_has_non_vop_phi (bb2
))
1434 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1437 /* Limit quadratic behaviour. */
1439 if (nr_comparisons
> max_comparisons
)
1442 /* This is a conservative dependency check. We could test more
1443 precise for allowed replacement direction. */
1444 if (!deps_ok_for_redirect (bb1
, bb2
))
1447 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1450 find_duplicate (same_succ
, bb1
, bb2
);
1455 /* Find clusters of bbs which can be merged. */
1458 find_clusters (void)
1462 while (!worklist
.is_empty ())
1464 same
= worklist
.pop ();
1465 same
->in_worklist
= false;
1466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1468 fprintf (dump_file
, "processing worklist entry\n");
1469 same_succ_print (dump_file
, same
);
1471 find_clusters_1 (same
);
1475 /* Returns the vop phi of BB, if any. */
1478 vop_phi (basic_block bb
)
1481 gimple_stmt_iterator gsi
;
1482 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1484 stmt
= gsi_stmt (gsi
);
1485 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1492 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1495 replace_block_by (basic_block bb1
, basic_block bb2
)
1503 bb2_phi
= vop_phi (bb2
);
1505 /* Mark the basic block as deleted. */
1506 mark_basic_block_deleted (bb1
);
1508 /* Redirect the incoming edges of bb1 to bb2. */
1509 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1511 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1512 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1513 gcc_assert (pred_edge
!= NULL
);
1515 if (bb2_phi
== NULL
)
1518 /* The phi might have run out of capacity when the redirect added an
1519 argument, which means it could have been replaced. Refresh it. */
1520 bb2_phi
= vop_phi (bb2
);
1522 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1523 pred_edge
, UNKNOWN_LOCATION
);
1526 bb2
->frequency
+= bb1
->frequency
;
1527 if (bb2
->frequency
> BB_FREQ_MAX
)
1528 bb2
->frequency
= BB_FREQ_MAX
;
1530 bb2
->count
+= bb1
->count
;
1532 /* Merge the outgoing edge counts from bb1 onto bb2. */
1533 gcov_type out_sum
= 0;
1534 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1536 e2
= find_edge (bb2
, e1
->dest
);
1538 e2
->count
+= e1
->count
;
1539 out_sum
+= e2
->count
;
1541 /* Recompute the edge probabilities from the new merged edge count.
1542 Use the sum of the new merged edge counts computed above instead
1543 of bb2's merged count, in case there are profile count insanities
1544 making the bb count inconsistent with the edge weights. */
1545 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1547 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1550 /* Do updates that use bb1, before deleting bb1. */
1551 release_last_vdef (bb1
);
1552 same_succ_flush_bb (bb1
);
1554 delete_basic_block (bb1
);
1557 /* Bbs for which update_debug_stmt need to be called. */
1559 static bitmap update_bbs
;
1561 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1562 number of bbs removed. */
1565 apply_clusters (void)
1567 basic_block bb1
, bb2
;
1571 int nr_bbs_removed
= 0;
1573 for (i
= 0; i
< all_clusters
.length (); ++i
)
1575 c
= all_clusters
[i
];
1580 bitmap_set_bit (update_bbs
, bb2
->index
);
1582 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1583 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1585 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1586 bitmap_clear_bit (update_bbs
, bb1
->index
);
1588 replace_block_by (bb1
, bb2
);
1593 return nr_bbs_removed
;
1596 /* Resets debug statement STMT if it has uses that are not dominated by their
1600 update_debug_stmt (gimple stmt
)
1602 use_operand_p use_p
;
1604 basic_block bbdef
, bbuse
;
1608 if (!gimple_debug_bind_p (stmt
))
1611 bbuse
= gimple_bb (stmt
);
1612 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1614 name
= USE_FROM_PTR (use_p
);
1615 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1617 def_stmt
= SSA_NAME_DEF_STMT (name
);
1618 gcc_assert (def_stmt
!= NULL
);
1620 bbdef
= gimple_bb (def_stmt
);
1621 if (bbdef
== NULL
|| bbuse
== bbdef
1622 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1625 gimple_debug_bind_reset_value (stmt
);
1630 /* Resets all debug statements that have uses that are not
1631 dominated by their defs. */
1634 update_debug_stmts (void)
1640 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1643 gimple_stmt_iterator gsi
;
1645 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1646 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1648 stmt
= gsi_stmt (gsi
);
1649 if (!is_gimple_debug (stmt
))
1651 update_debug_stmt (stmt
);
1656 /* Runs tail merge optimization. */
1659 tail_merge_optimize (unsigned int todo
)
1661 int nr_bbs_removed_total
= 0;
1663 bool loop_entered
= false;
1664 int iteration_nr
= 0;
1665 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1667 if (!flag_tree_tail_merge
1668 || max_iterations
== 0)
1671 timevar_push (TV_TREE_TAIL_MERGE
);
1673 if (!dom_info_available_p (CDI_DOMINATORS
))
1675 /* PRE can leave us with unreachable blocks, remove them now. */
1676 delete_unreachable_blocks ();
1677 calculate_dominance_info (CDI_DOMINATORS
);
1681 while (!worklist
.is_empty ())
1685 loop_entered
= true;
1686 alloc_cluster_vectors ();
1687 update_bbs
= BITMAP_ALLOC (NULL
);
1690 reset_cluster_vectors ();
1693 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1694 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1697 gcc_assert (worklist
.is_empty ());
1698 if (all_clusters
.is_empty ())
1701 nr_bbs_removed
= apply_clusters ();
1702 nr_bbs_removed_total
+= nr_bbs_removed
;
1703 if (nr_bbs_removed
== 0)
1706 free_dominance_info (CDI_DOMINATORS
);
1708 if (iteration_nr
== max_iterations
)
1711 calculate_dominance_info (CDI_DOMINATORS
);
1715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1716 fprintf (dump_file
, "htab collision / search: %f\n",
1717 same_succ_htab
.collisions ());
1719 if (nr_bbs_removed_total
> 0)
1721 if (MAY_HAVE_DEBUG_STMTS
)
1723 calculate_dominance_info (CDI_DOMINATORS
);
1724 update_debug_stmts ();
1727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1729 fprintf (dump_file
, "Before TODOs.\n");
1730 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1733 mark_virtual_operands_for_renaming (cfun
);
1739 delete_cluster_vectors ();
1740 BITMAP_FREE (update_bbs
);
1743 timevar_pop (TV_TREE_TAIL_MERGE
);