1 /* Tail merging for gimple.
2 Copyright (C) 2011-2015 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"
195 #include "fold-const.h"
196 #include "stor-layout.h"
197 #include "trans-mem.h"
200 #include "hard-reg-set.h"
201 #include "function.h"
202 #include "dominance.h"
205 #include "cfgcleanup.h"
206 #include "basic-block.h"
208 #include "tree-ssa-alias.h"
209 #include "internal-fn.h"
211 #include "gimple-expr.h"
213 #include "gimple-iterator.h"
214 #include "gimple-ssa.h"
215 #include "tree-cfg.h"
216 #include "tree-phinodes.h"
217 #include "ssa-iterators.h"
218 #include "tree-into-ssa.h"
220 #include "gimple-pretty-print.h"
221 #include "tree-ssa-sccvn.h"
222 #include "tree-dump.h"
224 #include "tree-pass.h"
225 #include "trans-mem.h"
227 /* Describes a group of bbs with the same successors. The successor bbs are
228 cached in succs, and the successor edge flags are cached in succ_flags.
229 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
230 it's marked in inverse.
231 Additionally, the hash value for the struct is cached in hashval, and
232 in_worklist indicates whether it's currently part of worklist. */
236 /* The bbs that have the same successor bbs. */
238 /* The successor bbs. */
240 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
243 /* The edge flags for each of the successor bbs. */
245 /* Indicates whether the struct is currently in the worklist. */
247 /* The hash value of the struct. */
250 /* hash_table support. */
251 typedef same_succ_def
*value_type
;
252 typedef same_succ_def
*compare_type
;
253 static inline hashval_t
hash (const same_succ_def
*);
254 static int equal (const same_succ_def
*, const same_succ_def
*);
255 static void remove (same_succ_def
*);
257 typedef struct same_succ_def
*same_succ
;
258 typedef const struct same_succ_def
*const_same_succ
;
260 /* hash routine for hash_table support, returns hashval of E. */
263 same_succ_def::hash (const same_succ_def
*e
)
268 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
270 struct bb_cluster_def
272 /* The bbs in the cluster. */
274 /* The preds of the bbs in the cluster. */
276 /* Index in all_clusters vector. */
278 /* The bb to replace the cluster with. */
281 typedef struct bb_cluster_def
*bb_cluster
;
282 typedef const struct bb_cluster_def
*const_bb_cluster
;
288 /* The number of non-debug statements in the bb. */
290 /* The same_succ that this bb is a member of. */
291 same_succ bb_same_succ
;
292 /* The cluster that this bb is a member of. */
294 /* The vop state at the exit of a bb. This is shortlived data, used to
295 communicate data between update_block_by and update_vuses. */
297 /* The bb that either contains or is dominated by the dependencies of the
302 /* Macros to access the fields of struct aux_bb_info. */
304 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
305 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
306 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
307 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
308 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
310 /* Returns true if the only effect a statement STMT has, is to define locally
314 stmt_local_def (gimple stmt
)
316 basic_block bb
, def_bb
;
317 imm_use_iterator iter
;
322 if (gimple_vdef (stmt
) != NULL_TREE
323 || gimple_has_side_effects (stmt
)
324 || gimple_could_trap_p_1 (stmt
, false, false)
325 || gimple_vuse (stmt
) != NULL_TREE
)
328 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
332 val
= DEF_FROM_PTR (def_p
);
333 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
336 def_bb
= gimple_bb (stmt
);
338 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
340 if (is_gimple_debug (USE_STMT (use_p
)))
342 bb
= gimple_bb (USE_STMT (use_p
));
346 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
347 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
356 /* Let GSI skip forwards over local defs. */
359 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
365 if (gsi_end_p (*gsi
))
367 stmt
= gsi_stmt (*gsi
);
368 if (!stmt_local_def (stmt
))
370 gsi_next_nondebug (gsi
);
374 /* VAL1 and VAL2 are either:
375 - uses in BB1 and BB2, or
376 - phi alternatives for BB1 and BB2.
377 Return true if the uses have the same gvn value. */
380 gvn_uses_equal (tree val1
, tree val2
)
382 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
387 if (vn_valueize (val1
) != vn_valueize (val2
))
390 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
391 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
394 /* Prints E to FILE. */
397 same_succ_print (FILE *file
, const same_succ e
)
400 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
401 bitmap_print (file
, e
->succs
, "succs:", "\n");
402 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
403 fprintf (file
, "flags:");
404 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
405 fprintf (file
, " %x", e
->succ_flags
[i
]);
406 fprintf (file
, "\n");
409 /* Prints same_succ VE to VFILE. */
412 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
414 const same_succ e
= *pe
;
415 same_succ_print (file
, e
);
419 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
422 update_dep_bb (basic_block use_bb
, tree val
)
427 if (TREE_CODE (val
) != SSA_NAME
)
430 /* Skip use of global def. */
431 if (SSA_NAME_IS_DEFAULT_DEF (val
))
434 /* Skip use of local def. */
435 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
436 if (dep_bb
== use_bb
)
439 if (BB_DEP_BB (use_bb
) == NULL
440 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
441 BB_DEP_BB (use_bb
) = dep_bb
;
444 /* Update BB_DEP_BB, given the dependencies in STMT. */
447 stmt_update_dep_bb (gimple stmt
)
452 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
453 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
456 /* Calculates hash value for same_succ VE. */
459 same_succ_hash (const_same_succ e
)
461 inchash::hash
hstate (bitmap_hash (e
->succs
));
464 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
465 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
472 for (gimple_stmt_iterator gsi
= gsi_start_nondebug_bb (bb
);
473 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
475 stmt
= gsi_stmt (gsi
);
476 stmt_update_dep_bb (stmt
);
477 if (stmt_local_def (stmt
))
481 hstate
.add_int (gimple_code (stmt
));
482 if (is_gimple_assign (stmt
))
483 hstate
.add_int (gimple_assign_rhs_code (stmt
));
484 if (!is_gimple_call (stmt
))
486 if (gimple_call_internal_p (stmt
))
487 hstate
.add_int (gimple_call_internal_fn (stmt
));
490 inchash::add_expr (gimple_call_fn (stmt
), hstate
);
491 if (gimple_call_chain (stmt
))
492 inchash::add_expr (gimple_call_chain (stmt
), hstate
);
494 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
496 arg
= gimple_call_arg (stmt
, i
);
497 arg
= vn_valueize (arg
);
498 inchash::add_expr (arg
, hstate
);
502 hstate
.add_int (size
);
505 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
507 flags
= e
->succ_flags
[i
];
508 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
509 hstate
.add_int (flags
);
512 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
514 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
515 for (gphi_iterator gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
));
519 gphi
*phi
= gsi
.phi ();
520 tree lhs
= gimple_phi_result (phi
);
521 tree val
= gimple_phi_arg_def (phi
, n
);
523 if (virtual_operand_p (lhs
))
525 update_dep_bb (bb
, val
);
529 return hstate
.end ();
532 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
533 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
534 the other edge flags. */
537 inverse_flags (const_same_succ e1
, const_same_succ e2
)
539 int f1a
, f1b
, f2a
, f2b
;
540 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
542 if (e1
->succ_flags
.length () != 2)
545 f1a
= e1
->succ_flags
[0];
546 f1b
= e1
->succ_flags
[1];
547 f2a
= e2
->succ_flags
[0];
548 f2b
= e2
->succ_flags
[1];
550 if (f1a
== f2a
&& f1b
== f2b
)
553 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
556 /* Compares SAME_SUCCs E1 and E2. */
559 same_succ_def::equal (const same_succ_def
*e1
, const same_succ_def
*e2
)
561 unsigned int i
, first1
, first2
;
562 gimple_stmt_iterator gsi1
, gsi2
;
564 basic_block bb1
, bb2
;
566 if (e1
->hashval
!= e2
->hashval
)
569 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
572 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
575 if (!inverse_flags (e1
, e2
))
577 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
578 if (e1
->succ_flags
[i
] != e2
->succ_flags
[i
])
582 first1
= bitmap_first_set_bit (e1
->bbs
);
583 first2
= bitmap_first_set_bit (e2
->bbs
);
585 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
586 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
588 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
591 gsi1
= gsi_start_nondebug_bb (bb1
);
592 gsi2
= gsi_start_nondebug_bb (bb2
);
593 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
594 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
595 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
597 s1
= gsi_stmt (gsi1
);
598 s2
= gsi_stmt (gsi2
);
599 if (gimple_code (s1
) != gimple_code (s2
))
601 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
603 gsi_next_nondebug (&gsi1
);
604 gsi_next_nondebug (&gsi2
);
605 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
606 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
612 /* Alloc and init a new SAME_SUCC. */
615 same_succ_alloc (void)
617 same_succ same
= XNEW (struct same_succ_def
);
619 same
->bbs
= BITMAP_ALLOC (NULL
);
620 same
->succs
= BITMAP_ALLOC (NULL
);
621 same
->inverse
= BITMAP_ALLOC (NULL
);
622 same
->succ_flags
.create (10);
623 same
->in_worklist
= false;
628 /* Delete same_succ E. */
631 same_succ_def::remove (same_succ e
)
633 BITMAP_FREE (e
->bbs
);
634 BITMAP_FREE (e
->succs
);
635 BITMAP_FREE (e
->inverse
);
636 e
->succ_flags
.release ();
641 /* Reset same_succ SAME. */
644 same_succ_reset (same_succ same
)
646 bitmap_clear (same
->bbs
);
647 bitmap_clear (same
->succs
);
648 bitmap_clear (same
->inverse
);
649 same
->succ_flags
.truncate (0);
652 static hash_table
<same_succ_def
> *same_succ_htab
;
654 /* Array that is used to store the edge flags for a successor. */
656 static int *same_succ_edge_flags
;
658 /* Bitmap that is used to mark bbs that are recently deleted. */
660 static bitmap deleted_bbs
;
662 /* Bitmap that is used to mark predecessors of bbs that are
665 static bitmap deleted_bb_preds
;
667 /* Prints same_succ_htab to stderr. */
669 extern void debug_same_succ (void);
671 debug_same_succ ( void)
673 same_succ_htab
->traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
677 /* Vector of bbs to process. */
679 static vec
<same_succ
> worklist
;
681 /* Prints worklist to FILE. */
684 print_worklist (FILE *file
)
687 for (i
= 0; i
< worklist
.length (); ++i
)
688 same_succ_print (file
, worklist
[i
]);
691 /* Adds SAME to worklist. */
694 add_to_worklist (same_succ same
)
696 if (same
->in_worklist
)
699 if (bitmap_count_bits (same
->bbs
) < 2)
702 same
->in_worklist
= true;
703 worklist
.safe_push (same
);
706 /* Add BB to same_succ_htab. */
709 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
713 same_succ same
= *same_p
;
719 /* Be conservative with loop structure. It's not evident that this test
720 is sufficient. Before tail-merge, we've just called
721 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
722 set, so there's no guarantee that the loop->latch value is still valid.
723 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
724 start of pre, we've kept that property intact throughout pre, and are
725 keeping it throughout tail-merge using this test. */
726 || bb
->loop_father
->latch
== bb
)
728 bitmap_set_bit (same
->bbs
, bb
->index
);
729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
731 int index
= e
->dest
->index
;
732 bitmap_set_bit (same
->succs
, index
);
733 same_succ_edge_flags
[index
] = e
->flags
;
735 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
736 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
738 same
->hashval
= same_succ_hash (same
);
740 slot
= same_succ_htab
->find_slot_with_hash (same
, same
->hashval
, INSERT
);
744 BB_SAME_SUCC (bb
) = same
;
745 add_to_worklist (same
);
750 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
751 BB_SAME_SUCC (bb
) = *slot
;
752 add_to_worklist (*slot
);
753 if (inverse_flags (same
, *slot
))
754 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
755 same_succ_reset (same
);
759 /* Find bbs with same successors. */
762 find_same_succ (void)
764 same_succ same
= same_succ_alloc ();
767 FOR_EACH_BB_FN (bb
, cfun
)
769 find_same_succ_bb (bb
, &same
);
771 same
= same_succ_alloc ();
774 same_succ_def::remove (same
);
777 /* Initializes worklist administration. */
782 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
783 same_succ_htab
= new hash_table
<same_succ_def
> (n_basic_blocks_for_fn (cfun
));
784 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
785 deleted_bbs
= BITMAP_ALLOC (NULL
);
786 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
787 worklist
.create (n_basic_blocks_for_fn (cfun
));
790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
792 fprintf (dump_file
, "initial worklist:\n");
793 print_worklist (dump_file
);
797 /* Deletes worklist administration. */
800 delete_worklist (void)
802 free_aux_for_blocks ();
803 delete same_succ_htab
;
804 same_succ_htab
= NULL
;
805 XDELETEVEC (same_succ_edge_flags
);
806 same_succ_edge_flags
= NULL
;
807 BITMAP_FREE (deleted_bbs
);
808 BITMAP_FREE (deleted_bb_preds
);
812 /* Mark BB as deleted, and mark its predecessors. */
815 mark_basic_block_deleted (basic_block bb
)
820 bitmap_set_bit (deleted_bbs
, bb
->index
);
822 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
823 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
826 /* Removes BB from its corresponding same_succ. */
829 same_succ_flush_bb (basic_block bb
)
831 same_succ same
= BB_SAME_SUCC (bb
);
832 BB_SAME_SUCC (bb
) = NULL
;
833 if (bitmap_single_bit_set_p (same
->bbs
))
834 same_succ_htab
->remove_elt_with_hash (same
, same
->hashval
);
836 bitmap_clear_bit (same
->bbs
, bb
->index
);
839 /* Removes all bbs in BBS from their corresponding same_succ. */
842 same_succ_flush_bbs (bitmap bbs
)
847 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
848 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
851 /* Release the last vdef in BB, either normal or phi result. */
854 release_last_vdef (basic_block bb
)
856 for (gimple_stmt_iterator i
= gsi_last_bb (bb
); !gsi_end_p (i
);
857 gsi_prev_nondebug (&i
))
859 gimple stmt
= gsi_stmt (i
);
860 if (gimple_vdef (stmt
) == NULL_TREE
)
863 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
867 for (gphi_iterator i
= gsi_start_phis (bb
); !gsi_end_p (i
);
870 gphi
*phi
= i
.phi ();
871 tree res
= gimple_phi_result (phi
);
873 if (!virtual_operand_p (res
))
876 mark_virtual_phi_result_for_renaming (phi
);
881 /* For deleted_bb_preds, find bbs with same successors. */
884 update_worklist (void)
891 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
892 bitmap_clear (deleted_bbs
);
894 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
895 same_succ_flush_bbs (deleted_bb_preds
);
897 same
= same_succ_alloc ();
898 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
900 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
901 gcc_assert (bb
!= NULL
);
902 find_same_succ_bb (bb
, &same
);
904 same
= same_succ_alloc ();
906 same_succ_def::remove (same
);
907 bitmap_clear (deleted_bb_preds
);
910 /* Prints cluster C to FILE. */
913 print_cluster (FILE *file
, bb_cluster c
)
917 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
918 bitmap_print (file
, c
->preds
, "preds:", "\n");
921 /* Prints cluster C to stderr. */
923 extern void debug_cluster (bb_cluster
);
925 debug_cluster (bb_cluster c
)
927 print_cluster (stderr
, c
);
930 /* Update C->rep_bb, given that BB is added to the cluster. */
933 update_rep_bb (bb_cluster c
, basic_block bb
)
936 if (c
->rep_bb
== NULL
)
942 /* Current needs no deps, keep it. */
943 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
946 /* Bb needs no deps, change rep_bb. */
947 if (BB_DEP_BB (bb
) == NULL
)
953 /* Bb needs last deps earlier than current, change rep_bb. A potential
954 problem with this, is that the first deps might also be earlier, which
955 would mean we prefer longer lifetimes for the deps. To be able to check
956 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
957 BB_DEP_BB, which is really BB_LAST_DEP_BB.
958 The benefit of choosing the bb with last deps earlier, is that it can
959 potentially be used as replacement for more bbs. */
960 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
964 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
967 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
972 bitmap_set_bit (c
->bbs
, bb
->index
);
974 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
975 bitmap_set_bit (c
->preds
, e
->src
->index
);
977 update_rep_bb (c
, bb
);
980 /* Allocate and init new cluster. */
986 c
= XCNEW (struct bb_cluster_def
);
987 c
->bbs
= BITMAP_ALLOC (NULL
);
988 c
->preds
= BITMAP_ALLOC (NULL
);
993 /* Delete clusters. */
996 delete_cluster (bb_cluster c
)
1000 BITMAP_FREE (c
->bbs
);
1001 BITMAP_FREE (c
->preds
);
1006 /* Array that contains all clusters. */
1008 static vec
<bb_cluster
> all_clusters
;
1010 /* Allocate all cluster vectors. */
1013 alloc_cluster_vectors (void)
1015 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1018 /* Reset all cluster vectors. */
1021 reset_cluster_vectors (void)
1025 for (i
= 0; i
< all_clusters
.length (); ++i
)
1026 delete_cluster (all_clusters
[i
]);
1027 all_clusters
.truncate (0);
1028 FOR_EACH_BB_FN (bb
, cfun
)
1029 BB_CLUSTER (bb
) = NULL
;
1032 /* Delete all cluster vectors. */
1035 delete_cluster_vectors (void)
1038 for (i
= 0; i
< all_clusters
.length (); ++i
)
1039 delete_cluster (all_clusters
[i
]);
1040 all_clusters
.release ();
1043 /* Merge cluster C2 into C1. */
1046 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1048 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1049 bitmap_ior_into (c1
->preds
, c2
->preds
);
1052 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1053 all_clusters, or merge c with existing cluster. */
1056 set_cluster (basic_block bb1
, basic_block bb2
)
1058 basic_block merge_bb
, other_bb
;
1059 bb_cluster merge
, old
, c
;
1061 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1064 add_bb_to_cluster (c
, bb1
);
1065 add_bb_to_cluster (c
, bb2
);
1066 BB_CLUSTER (bb1
) = c
;
1067 BB_CLUSTER (bb2
) = c
;
1068 c
->index
= all_clusters
.length ();
1069 all_clusters
.safe_push (c
);
1071 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1073 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1074 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1075 merge
= BB_CLUSTER (merge_bb
);
1076 add_bb_to_cluster (merge
, other_bb
);
1077 BB_CLUSTER (other_bb
) = merge
;
1079 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1084 old
= BB_CLUSTER (bb2
);
1085 merge
= BB_CLUSTER (bb1
);
1086 merge_clusters (merge
, old
);
1087 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1088 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1089 all_clusters
[old
->index
] = NULL
;
1090 update_rep_bb (merge
, old
->rep_bb
);
1091 delete_cluster (old
);
1097 /* Return true if gimple operands T1 and T2 have the same value. */
1100 gimple_operand_equal_value_p (tree t1
, tree t2
)
1109 if (operand_equal_p (t1
, t2
, 0))
1112 return gvn_uses_equal (t1
, t2
);
1115 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1116 gimple_bb (s2) are members of SAME_SUCC. */
1119 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1123 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1126 enum tree_code code1
, code2
;
1128 if (gimple_code (s1
) != gimple_code (s2
))
1131 switch (gimple_code (s1
))
1134 if (!gimple_call_same_target_p (s1
, s2
))
1137 t1
= gimple_call_chain (s1
);
1138 t2
= gimple_call_chain (s2
);
1139 if (!gimple_operand_equal_value_p (t1
, t2
))
1142 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1145 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1147 t1
= gimple_call_arg (s1
, i
);
1148 t2
= gimple_call_arg (s2
, i
);
1149 if (!gimple_operand_equal_value_p (t1
, t2
))
1153 lhs1
= gimple_get_lhs (s1
);
1154 lhs2
= gimple_get_lhs (s2
);
1155 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1157 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1159 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1160 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1161 return operand_equal_p (lhs1
, lhs2
, 0);
1164 lhs1
= gimple_get_lhs (s1
);
1165 lhs2
= gimple_get_lhs (s2
);
1166 if (TREE_CODE (lhs1
) != SSA_NAME
1167 && TREE_CODE (lhs2
) != SSA_NAME
)
1168 return (operand_equal_p (lhs1
, lhs2
, 0)
1169 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1170 gimple_assign_rhs1 (s2
)));
1171 else if (TREE_CODE (lhs1
) == SSA_NAME
1172 && TREE_CODE (lhs2
) == SSA_NAME
)
1173 return operand_equal_p (gimple_assign_rhs1 (s1
),
1174 gimple_assign_rhs1 (s2
), 0);
1178 t1
= gimple_cond_lhs (s1
);
1179 t2
= gimple_cond_lhs (s2
);
1180 if (!gimple_operand_equal_value_p (t1
, t2
))
1183 t1
= gimple_cond_rhs (s1
);
1184 t2
= gimple_cond_rhs (s2
);
1185 if (!gimple_operand_equal_value_p (t1
, t2
))
1188 code1
= gimple_expr_code (s1
);
1189 code2
= gimple_expr_code (s2
);
1190 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1191 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1194 bool honor_nans
= HONOR_NANS (t1
);
1195 code2
= invert_tree_comparison (code2
, honor_nans
);
1197 return code1
== code2
;
1204 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1205 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1206 processed statements. */
1209 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1217 if (gsi_end_p (*gsi
))
1219 stmt
= gsi_stmt (*gsi
);
1221 lvuse
= gimple_vuse (stmt
);
1222 if (lvuse
!= NULL_TREE
)
1225 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1226 *vuse_escaped
= true;
1229 if (!stmt_local_def (stmt
))
1231 gsi_prev_nondebug (gsi
);
1235 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1239 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1241 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1242 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1243 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1244 bool vuse_escaped
= false;
1246 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1247 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1249 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1251 gimple stmt1
= gsi_stmt (gsi1
);
1252 gimple stmt2
= gsi_stmt (gsi2
);
1254 /* What could be better than to this this here is to blacklist the bb
1255 containing the stmt, when encountering the stmt f.i. in
1257 if (is_tm_ending (stmt1
)
1258 || is_tm_ending (stmt2
))
1261 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1264 gsi_prev_nondebug (&gsi1
);
1265 gsi_prev_nondebug (&gsi2
);
1266 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1267 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1270 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1273 /* If the incoming vuses are not the same, and the vuse escaped into an
1274 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1275 which potentially means the semantics of one of the blocks will be changed.
1276 TODO: make this check more precise. */
1277 if (vuse_escaped
&& vuse1
!= vuse2
)
1281 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1282 bb1
->index
, bb2
->index
);
1284 set_cluster (bb1
, bb2
);
1287 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1291 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1293 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1296 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1298 gphi
*phi
= gsi
.phi ();
1299 tree lhs
= gimple_phi_result (phi
);
1300 tree val1
= gimple_phi_arg_def (phi
, n1
);
1301 tree val2
= gimple_phi_arg_def (phi
, n2
);
1303 if (virtual_operand_p (lhs
))
1306 if (operand_equal_for_phi_arg_p (val1
, val2
))
1308 if (gvn_uses_equal (val1
, val2
))
1317 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1318 phi alternatives for BB1 and BB2 are equal. */
1321 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1328 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1330 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1331 e1
= find_edge (bb1
, succ
);
1332 e2
= find_edge (bb2
, succ
);
1333 if (e1
->flags
& EDGE_COMPLEX
1334 || e2
->flags
& EDGE_COMPLEX
)
1337 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1339 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1346 /* Return true if BB has non-vop phis. */
1349 bb_has_non_vop_phi (basic_block bb
)
1351 gimple_seq phis
= phi_nodes (bb
);
1357 if (!gimple_seq_singleton_p (phis
))
1360 phi
= gimple_seq_first_stmt (phis
);
1361 return !virtual_operand_p (gimple_phi_result (phi
));
1364 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1365 invariant that uses in FROM are dominates by their defs. */
1368 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1370 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1373 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1378 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1379 bitmap_set_bit (from_preds
, e
->src
->index
);
1380 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1381 BITMAP_FREE (from_preds
);
1383 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1386 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1387 replacement bb) and vice versa maintains the invariant that uses in the
1388 replacement are dominates by their defs. */
1391 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1393 if (BB_CLUSTER (bb1
) != NULL
)
1394 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1396 if (BB_CLUSTER (bb2
) != NULL
)
1397 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1399 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1400 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1403 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1406 find_clusters_1 (same_succ same_succ
)
1408 basic_block bb1
, bb2
;
1410 bitmap_iterator bi
, bj
;
1412 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1414 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1416 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1418 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1419 phi-nodes in bb1 and bb2, with the same alternatives for the same
1421 if (bb_has_non_vop_phi (bb1
))
1425 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1427 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1429 if (bb_has_non_vop_phi (bb2
))
1432 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1435 /* Limit quadratic behaviour. */
1437 if (nr_comparisons
> max_comparisons
)
1440 /* This is a conservative dependency check. We could test more
1441 precise for allowed replacement direction. */
1442 if (!deps_ok_for_redirect (bb1
, bb2
))
1445 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1448 find_duplicate (same_succ
, bb1
, bb2
);
1453 /* Find clusters of bbs which can be merged. */
1456 find_clusters (void)
1460 while (!worklist
.is_empty ())
1462 same
= worklist
.pop ();
1463 same
->in_worklist
= false;
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1466 fprintf (dump_file
, "processing worklist entry\n");
1467 same_succ_print (dump_file
, same
);
1469 find_clusters_1 (same
);
1473 /* Returns the vop phi of BB, if any. */
1476 vop_phi (basic_block bb
)
1480 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1483 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1490 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1493 replace_block_by (basic_block bb1
, basic_block bb2
)
1501 bb2_phi
= vop_phi (bb2
);
1503 /* Mark the basic block as deleted. */
1504 mark_basic_block_deleted (bb1
);
1506 /* Redirect the incoming edges of bb1 to bb2. */
1507 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1509 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1510 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1511 gcc_assert (pred_edge
!= NULL
);
1513 if (bb2_phi
== NULL
)
1516 /* The phi might have run out of capacity when the redirect added an
1517 argument, which means it could have been replaced. Refresh it. */
1518 bb2_phi
= vop_phi (bb2
);
1520 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1521 pred_edge
, UNKNOWN_LOCATION
);
1524 bb2
->frequency
+= bb1
->frequency
;
1525 if (bb2
->frequency
> BB_FREQ_MAX
)
1526 bb2
->frequency
= BB_FREQ_MAX
;
1528 bb2
->count
+= bb1
->count
;
1530 /* Merge the outgoing edge counts from bb1 onto bb2. */
1531 gcov_type out_sum
= 0;
1532 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1534 e2
= find_edge (bb2
, e1
->dest
);
1536 e2
->count
+= e1
->count
;
1537 out_sum
+= e2
->count
;
1539 /* Recompute the edge probabilities from the new merged edge count.
1540 Use the sum of the new merged edge counts computed above instead
1541 of bb2's merged count, in case there are profile count insanities
1542 making the bb count inconsistent with the edge weights. */
1543 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1545 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1548 /* Do updates that use bb1, before deleting bb1. */
1549 release_last_vdef (bb1
);
1550 same_succ_flush_bb (bb1
);
1552 delete_basic_block (bb1
);
1555 /* Bbs for which update_debug_stmt need to be called. */
1557 static bitmap update_bbs
;
1559 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1560 number of bbs removed. */
1563 apply_clusters (void)
1565 basic_block bb1
, bb2
;
1569 int nr_bbs_removed
= 0;
1571 for (i
= 0; i
< all_clusters
.length (); ++i
)
1573 c
= all_clusters
[i
];
1578 bitmap_set_bit (update_bbs
, bb2
->index
);
1580 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1581 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1583 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1584 bitmap_clear_bit (update_bbs
, bb1
->index
);
1586 replace_block_by (bb1
, bb2
);
1591 return nr_bbs_removed
;
1594 /* Resets debug statement STMT if it has uses that are not dominated by their
1598 update_debug_stmt (gimple stmt
)
1600 use_operand_p use_p
;
1604 if (!gimple_debug_bind_p (stmt
))
1607 bbuse
= gimple_bb (stmt
);
1608 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1610 tree name
= USE_FROM_PTR (use_p
);
1611 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
1612 basic_block 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
);
1623 /* Resets all debug statements that have uses that are not
1624 dominated by their defs. */
1627 update_debug_stmts (void)
1633 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1636 gimple_stmt_iterator gsi
;
1638 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1639 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1641 stmt
= gsi_stmt (gsi
);
1642 if (!is_gimple_debug (stmt
))
1644 update_debug_stmt (stmt
);
1649 /* Runs tail merge optimization. */
1652 tail_merge_optimize (unsigned int todo
)
1654 int nr_bbs_removed_total
= 0;
1656 bool loop_entered
= false;
1657 int iteration_nr
= 0;
1658 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1660 if (!flag_tree_tail_merge
1661 || max_iterations
== 0)
1664 timevar_push (TV_TREE_TAIL_MERGE
);
1666 if (!dom_info_available_p (CDI_DOMINATORS
))
1668 /* PRE can leave us with unreachable blocks, remove them now. */
1669 delete_unreachable_blocks ();
1670 calculate_dominance_info (CDI_DOMINATORS
);
1674 while (!worklist
.is_empty ())
1678 loop_entered
= true;
1679 alloc_cluster_vectors ();
1680 update_bbs
= BITMAP_ALLOC (NULL
);
1683 reset_cluster_vectors ();
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1687 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1690 gcc_assert (worklist
.is_empty ());
1691 if (all_clusters
.is_empty ())
1694 nr_bbs_removed
= apply_clusters ();
1695 nr_bbs_removed_total
+= nr_bbs_removed
;
1696 if (nr_bbs_removed
== 0)
1699 free_dominance_info (CDI_DOMINATORS
);
1701 if (iteration_nr
== max_iterations
)
1704 calculate_dominance_info (CDI_DOMINATORS
);
1708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1709 fprintf (dump_file
, "htab collision / search: %f\n",
1710 same_succ_htab
->collisions ());
1712 if (nr_bbs_removed_total
> 0)
1714 if (MAY_HAVE_DEBUG_STMTS
)
1716 calculate_dominance_info (CDI_DOMINATORS
);
1717 update_debug_stmts ();
1720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1722 fprintf (dump_file
, "Before TODOs.\n");
1723 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1726 mark_virtual_operands_for_renaming (cfun
);
1732 delete_cluster_vectors ();
1733 BITMAP_FREE (update_bbs
);
1736 timevar_pop (TV_TREE_TAIL_MERGE
);