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"
196 #include "fold-const.h"
197 #include "stor-layout.h"
198 #include "trans-mem.h"
201 #include "hard-reg-set.h"
203 #include "function.h"
204 #include "dominance.h"
207 #include "cfgcleanup.h"
208 #include "basic-block.h"
210 #include "tree-ssa-alias.h"
211 #include "internal-fn.h"
213 #include "gimple-expr.h"
216 #include "gimple-iterator.h"
217 #include "gimple-ssa.h"
218 #include "tree-cfg.h"
219 #include "tree-phinodes.h"
220 #include "ssa-iterators.h"
221 #include "tree-into-ssa.h"
223 #include "gimple-pretty-print.h"
224 #include "tree-ssa-sccvn.h"
225 #include "tree-dump.h"
227 #include "tree-pass.h"
228 #include "trans-mem.h"
230 /* Describes a group of bbs with the same successors. The successor bbs are
231 cached in succs, and the successor edge flags are cached in succ_flags.
232 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
233 it's marked in inverse.
234 Additionally, the hash value for the struct is cached in hashval, and
235 in_worklist indicates whether it's currently part of worklist. */
239 /* The bbs that have the same successor bbs. */
241 /* The successor bbs. */
243 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
246 /* The edge flags for each of the successor bbs. */
248 /* Indicates whether the struct is currently in the worklist. */
250 /* The hash value of the struct. */
253 /* hash_table support. */
254 typedef same_succ_def
*value_type
;
255 typedef same_succ_def
*compare_type
;
256 static inline hashval_t
hash (const same_succ_def
*);
257 static int equal (const same_succ_def
*, const same_succ_def
*);
258 static void remove (same_succ_def
*);
260 typedef struct same_succ_def
*same_succ
;
261 typedef const struct same_succ_def
*const_same_succ
;
263 /* hash routine for hash_table support, returns hashval of E. */
266 same_succ_def::hash (const same_succ_def
*e
)
271 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
273 struct bb_cluster_def
275 /* The bbs in the cluster. */
277 /* The preds of the bbs in the cluster. */
279 /* Index in all_clusters vector. */
281 /* The bb to replace the cluster with. */
284 typedef struct bb_cluster_def
*bb_cluster
;
285 typedef const struct bb_cluster_def
*const_bb_cluster
;
291 /* The number of non-debug statements in the bb. */
293 /* The same_succ that this bb is a member of. */
294 same_succ bb_same_succ
;
295 /* The cluster that this bb is a member of. */
297 /* The vop state at the exit of a bb. This is shortlived data, used to
298 communicate data between update_block_by and update_vuses. */
300 /* The bb that either contains or is dominated by the dependencies of the
305 /* Macros to access the fields of struct aux_bb_info. */
307 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
308 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
309 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
310 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
311 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
313 /* Returns true if the only effect a statement STMT has, is to define locally
317 stmt_local_def (gimple stmt
)
319 basic_block bb
, def_bb
;
320 imm_use_iterator iter
;
325 if (gimple_vdef (stmt
) != NULL_TREE
326 || gimple_has_side_effects (stmt
)
327 || gimple_could_trap_p_1 (stmt
, false, false)
328 || gimple_vuse (stmt
) != NULL_TREE
)
331 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
335 val
= DEF_FROM_PTR (def_p
);
336 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
339 def_bb
= gimple_bb (stmt
);
341 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
343 if (is_gimple_debug (USE_STMT (use_p
)))
345 bb
= gimple_bb (USE_STMT (use_p
));
349 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
350 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
359 /* Let GSI skip forwards over local defs. */
362 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
368 if (gsi_end_p (*gsi
))
370 stmt
= gsi_stmt (*gsi
);
371 if (!stmt_local_def (stmt
))
373 gsi_next_nondebug (gsi
);
377 /* VAL1 and VAL2 are either:
378 - uses in BB1 and BB2, or
379 - phi alternatives for BB1 and BB2.
380 Return true if the uses have the same gvn value. */
383 gvn_uses_equal (tree val1
, tree val2
)
385 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
390 if (vn_valueize (val1
) != vn_valueize (val2
))
393 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
394 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
397 /* Prints E to FILE. */
400 same_succ_print (FILE *file
, const same_succ e
)
403 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
404 bitmap_print (file
, e
->succs
, "succs:", "\n");
405 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
406 fprintf (file
, "flags:");
407 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
408 fprintf (file
, " %x", e
->succ_flags
[i
]);
409 fprintf (file
, "\n");
412 /* Prints same_succ VE to VFILE. */
415 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
417 const same_succ e
= *pe
;
418 same_succ_print (file
, e
);
422 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
425 update_dep_bb (basic_block use_bb
, tree val
)
430 if (TREE_CODE (val
) != SSA_NAME
)
433 /* Skip use of global def. */
434 if (SSA_NAME_IS_DEFAULT_DEF (val
))
437 /* Skip use of local def. */
438 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
439 if (dep_bb
== use_bb
)
442 if (BB_DEP_BB (use_bb
) == NULL
443 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
444 BB_DEP_BB (use_bb
) = dep_bb
;
447 /* Update BB_DEP_BB, given the dependencies in STMT. */
450 stmt_update_dep_bb (gimple stmt
)
455 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
456 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
459 /* Calculates hash value for same_succ VE. */
462 same_succ_hash (const_same_succ e
)
464 inchash::hash
hstate (bitmap_hash (e
->succs
));
467 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
468 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
475 for (gimple_stmt_iterator gsi
= gsi_start_nondebug_bb (bb
);
476 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
478 stmt
= gsi_stmt (gsi
);
479 stmt_update_dep_bb (stmt
);
480 if (stmt_local_def (stmt
))
484 hstate
.add_int (gimple_code (stmt
));
485 if (is_gimple_assign (stmt
))
486 hstate
.add_int (gimple_assign_rhs_code (stmt
));
487 if (!is_gimple_call (stmt
))
489 if (gimple_call_internal_p (stmt
))
490 hstate
.add_int (gimple_call_internal_fn (stmt
));
493 inchash::add_expr (gimple_call_fn (stmt
), hstate
);
494 if (gimple_call_chain (stmt
))
495 inchash::add_expr (gimple_call_chain (stmt
), hstate
);
497 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
499 arg
= gimple_call_arg (stmt
, i
);
500 arg
= vn_valueize (arg
);
501 inchash::add_expr (arg
, hstate
);
505 hstate
.add_int (size
);
508 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
510 flags
= e
->succ_flags
[i
];
511 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
512 hstate
.add_int (flags
);
515 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
517 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
518 for (gphi_iterator gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
));
522 gphi
*phi
= gsi
.phi ();
523 tree lhs
= gimple_phi_result (phi
);
524 tree val
= gimple_phi_arg_def (phi
, n
);
526 if (virtual_operand_p (lhs
))
528 update_dep_bb (bb
, val
);
532 return hstate
.end ();
535 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
536 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
537 the other edge flags. */
540 inverse_flags (const_same_succ e1
, const_same_succ e2
)
542 int f1a
, f1b
, f2a
, f2b
;
543 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
545 if (e1
->succ_flags
.length () != 2)
548 f1a
= e1
->succ_flags
[0];
549 f1b
= e1
->succ_flags
[1];
550 f2a
= e2
->succ_flags
[0];
551 f2b
= e2
->succ_flags
[1];
553 if (f1a
== f2a
&& f1b
== f2b
)
556 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
559 /* Compares SAME_SUCCs E1 and E2. */
562 same_succ_def::equal (const same_succ_def
*e1
, const same_succ_def
*e2
)
564 unsigned int i
, first1
, first2
;
565 gimple_stmt_iterator gsi1
, gsi2
;
567 basic_block bb1
, bb2
;
569 if (e1
->hashval
!= e2
->hashval
)
572 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
575 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
578 if (!inverse_flags (e1
, e2
))
580 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
581 if (e1
->succ_flags
[i
] != e2
->succ_flags
[i
])
585 first1
= bitmap_first_set_bit (e1
->bbs
);
586 first2
= bitmap_first_set_bit (e2
->bbs
);
588 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
589 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
591 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
594 gsi1
= gsi_start_nondebug_bb (bb1
);
595 gsi2
= gsi_start_nondebug_bb (bb2
);
596 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
597 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
598 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
600 s1
= gsi_stmt (gsi1
);
601 s2
= gsi_stmt (gsi2
);
602 if (gimple_code (s1
) != gimple_code (s2
))
604 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
606 gsi_next_nondebug (&gsi1
);
607 gsi_next_nondebug (&gsi2
);
608 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
609 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
615 /* Alloc and init a new SAME_SUCC. */
618 same_succ_alloc (void)
620 same_succ same
= XNEW (struct same_succ_def
);
622 same
->bbs
= BITMAP_ALLOC (NULL
);
623 same
->succs
= BITMAP_ALLOC (NULL
);
624 same
->inverse
= BITMAP_ALLOC (NULL
);
625 same
->succ_flags
.create (10);
626 same
->in_worklist
= false;
631 /* Delete same_succ E. */
634 same_succ_def::remove (same_succ e
)
636 BITMAP_FREE (e
->bbs
);
637 BITMAP_FREE (e
->succs
);
638 BITMAP_FREE (e
->inverse
);
639 e
->succ_flags
.release ();
644 /* Reset same_succ SAME. */
647 same_succ_reset (same_succ same
)
649 bitmap_clear (same
->bbs
);
650 bitmap_clear (same
->succs
);
651 bitmap_clear (same
->inverse
);
652 same
->succ_flags
.truncate (0);
655 static hash_table
<same_succ_def
> *same_succ_htab
;
657 /* Array that is used to store the edge flags for a successor. */
659 static int *same_succ_edge_flags
;
661 /* Bitmap that is used to mark bbs that are recently deleted. */
663 static bitmap deleted_bbs
;
665 /* Bitmap that is used to mark predecessors of bbs that are
668 static bitmap deleted_bb_preds
;
670 /* Prints same_succ_htab to stderr. */
672 extern void debug_same_succ (void);
674 debug_same_succ ( void)
676 same_succ_htab
->traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
680 /* Vector of bbs to process. */
682 static vec
<same_succ
> worklist
;
684 /* Prints worklist to FILE. */
687 print_worklist (FILE *file
)
690 for (i
= 0; i
< worklist
.length (); ++i
)
691 same_succ_print (file
, worklist
[i
]);
694 /* Adds SAME to worklist. */
697 add_to_worklist (same_succ same
)
699 if (same
->in_worklist
)
702 if (bitmap_count_bits (same
->bbs
) < 2)
705 same
->in_worklist
= true;
706 worklist
.safe_push (same
);
709 /* Add BB to same_succ_htab. */
712 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
716 same_succ same
= *same_p
;
722 /* Be conservative with loop structure. It's not evident that this test
723 is sufficient. Before tail-merge, we've just called
724 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
725 set, so there's no guarantee that the loop->latch value is still valid.
726 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
727 start of pre, we've kept that property intact throughout pre, and are
728 keeping it throughout tail-merge using this test. */
729 || bb
->loop_father
->latch
== bb
)
731 bitmap_set_bit (same
->bbs
, bb
->index
);
732 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
734 int index
= e
->dest
->index
;
735 bitmap_set_bit (same
->succs
, index
);
736 same_succ_edge_flags
[index
] = e
->flags
;
738 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
739 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
741 same
->hashval
= same_succ_hash (same
);
743 slot
= same_succ_htab
->find_slot_with_hash (same
, same
->hashval
, INSERT
);
747 BB_SAME_SUCC (bb
) = same
;
748 add_to_worklist (same
);
753 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
754 BB_SAME_SUCC (bb
) = *slot
;
755 add_to_worklist (*slot
);
756 if (inverse_flags (same
, *slot
))
757 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
758 same_succ_reset (same
);
762 /* Find bbs with same successors. */
765 find_same_succ (void)
767 same_succ same
= same_succ_alloc ();
770 FOR_EACH_BB_FN (bb
, cfun
)
772 find_same_succ_bb (bb
, &same
);
774 same
= same_succ_alloc ();
777 same_succ_def::remove (same
);
780 /* Initializes worklist administration. */
785 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
786 same_succ_htab
= new hash_table
<same_succ_def
> (n_basic_blocks_for_fn (cfun
));
787 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
788 deleted_bbs
= BITMAP_ALLOC (NULL
);
789 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
790 worklist
.create (n_basic_blocks_for_fn (cfun
));
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 fprintf (dump_file
, "initial worklist:\n");
796 print_worklist (dump_file
);
800 /* Deletes worklist administration. */
803 delete_worklist (void)
805 free_aux_for_blocks ();
806 delete same_succ_htab
;
807 same_succ_htab
= NULL
;
808 XDELETEVEC (same_succ_edge_flags
);
809 same_succ_edge_flags
= NULL
;
810 BITMAP_FREE (deleted_bbs
);
811 BITMAP_FREE (deleted_bb_preds
);
815 /* Mark BB as deleted, and mark its predecessors. */
818 mark_basic_block_deleted (basic_block bb
)
823 bitmap_set_bit (deleted_bbs
, bb
->index
);
825 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
826 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
829 /* Removes BB from its corresponding same_succ. */
832 same_succ_flush_bb (basic_block bb
)
834 same_succ same
= BB_SAME_SUCC (bb
);
835 BB_SAME_SUCC (bb
) = NULL
;
836 if (bitmap_single_bit_set_p (same
->bbs
))
837 same_succ_htab
->remove_elt_with_hash (same
, same
->hashval
);
839 bitmap_clear_bit (same
->bbs
, bb
->index
);
842 /* Removes all bbs in BBS from their corresponding same_succ. */
845 same_succ_flush_bbs (bitmap bbs
)
850 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
851 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
854 /* Release the last vdef in BB, either normal or phi result. */
857 release_last_vdef (basic_block bb
)
859 for (gimple_stmt_iterator i
= gsi_last_bb (bb
); !gsi_end_p (i
);
860 gsi_prev_nondebug (&i
))
862 gimple stmt
= gsi_stmt (i
);
863 if (gimple_vdef (stmt
) == NULL_TREE
)
866 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
870 for (gphi_iterator i
= gsi_start_phis (bb
); !gsi_end_p (i
);
873 gphi
*phi
= i
.phi ();
874 tree res
= gimple_phi_result (phi
);
876 if (!virtual_operand_p (res
))
879 mark_virtual_phi_result_for_renaming (phi
);
884 /* For deleted_bb_preds, find bbs with same successors. */
887 update_worklist (void)
894 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
895 bitmap_clear (deleted_bbs
);
897 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
898 same_succ_flush_bbs (deleted_bb_preds
);
900 same
= same_succ_alloc ();
901 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
903 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
904 gcc_assert (bb
!= NULL
);
905 find_same_succ_bb (bb
, &same
);
907 same
= same_succ_alloc ();
909 same_succ_def::remove (same
);
910 bitmap_clear (deleted_bb_preds
);
913 /* Prints cluster C to FILE. */
916 print_cluster (FILE *file
, bb_cluster c
)
920 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
921 bitmap_print (file
, c
->preds
, "preds:", "\n");
924 /* Prints cluster C to stderr. */
926 extern void debug_cluster (bb_cluster
);
928 debug_cluster (bb_cluster c
)
930 print_cluster (stderr
, c
);
933 /* Update C->rep_bb, given that BB is added to the cluster. */
936 update_rep_bb (bb_cluster c
, basic_block bb
)
939 if (c
->rep_bb
== NULL
)
945 /* Current needs no deps, keep it. */
946 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
949 /* Bb needs no deps, change rep_bb. */
950 if (BB_DEP_BB (bb
) == NULL
)
956 /* Bb needs last deps earlier than current, change rep_bb. A potential
957 problem with this, is that the first deps might also be earlier, which
958 would mean we prefer longer lifetimes for the deps. To be able to check
959 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
960 BB_DEP_BB, which is really BB_LAST_DEP_BB.
961 The benefit of choosing the bb with last deps earlier, is that it can
962 potentially be used as replacement for more bbs. */
963 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
967 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
970 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
975 bitmap_set_bit (c
->bbs
, bb
->index
);
977 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
978 bitmap_set_bit (c
->preds
, e
->src
->index
);
980 update_rep_bb (c
, bb
);
983 /* Allocate and init new cluster. */
989 c
= XCNEW (struct bb_cluster_def
);
990 c
->bbs
= BITMAP_ALLOC (NULL
);
991 c
->preds
= BITMAP_ALLOC (NULL
);
996 /* Delete clusters. */
999 delete_cluster (bb_cluster c
)
1003 BITMAP_FREE (c
->bbs
);
1004 BITMAP_FREE (c
->preds
);
1009 /* Array that contains all clusters. */
1011 static vec
<bb_cluster
> all_clusters
;
1013 /* Allocate all cluster vectors. */
1016 alloc_cluster_vectors (void)
1018 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1021 /* Reset all cluster vectors. */
1024 reset_cluster_vectors (void)
1028 for (i
= 0; i
< all_clusters
.length (); ++i
)
1029 delete_cluster (all_clusters
[i
]);
1030 all_clusters
.truncate (0);
1031 FOR_EACH_BB_FN (bb
, cfun
)
1032 BB_CLUSTER (bb
) = NULL
;
1035 /* Delete all cluster vectors. */
1038 delete_cluster_vectors (void)
1041 for (i
= 0; i
< all_clusters
.length (); ++i
)
1042 delete_cluster (all_clusters
[i
]);
1043 all_clusters
.release ();
1046 /* Merge cluster C2 into C1. */
1049 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1051 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1052 bitmap_ior_into (c1
->preds
, c2
->preds
);
1055 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1056 all_clusters, or merge c with existing cluster. */
1059 set_cluster (basic_block bb1
, basic_block bb2
)
1061 basic_block merge_bb
, other_bb
;
1062 bb_cluster merge
, old
, c
;
1064 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1067 add_bb_to_cluster (c
, bb1
);
1068 add_bb_to_cluster (c
, bb2
);
1069 BB_CLUSTER (bb1
) = c
;
1070 BB_CLUSTER (bb2
) = c
;
1071 c
->index
= all_clusters
.length ();
1072 all_clusters
.safe_push (c
);
1074 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1076 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1077 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1078 merge
= BB_CLUSTER (merge_bb
);
1079 add_bb_to_cluster (merge
, other_bb
);
1080 BB_CLUSTER (other_bb
) = merge
;
1082 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1087 old
= BB_CLUSTER (bb2
);
1088 merge
= BB_CLUSTER (bb1
);
1089 merge_clusters (merge
, old
);
1090 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1091 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1092 all_clusters
[old
->index
] = NULL
;
1093 update_rep_bb (merge
, old
->rep_bb
);
1094 delete_cluster (old
);
1100 /* Return true if gimple operands T1 and T2 have the same value. */
1103 gimple_operand_equal_value_p (tree t1
, tree t2
)
1112 if (operand_equal_p (t1
, t2
, 0))
1115 return gvn_uses_equal (t1
, t2
);
1118 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1119 gimple_bb (s2) are members of SAME_SUCC. */
1122 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1126 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1129 enum tree_code code1
, code2
;
1131 if (gimple_code (s1
) != gimple_code (s2
))
1134 switch (gimple_code (s1
))
1137 if (!gimple_call_same_target_p (s1
, s2
))
1140 t1
= gimple_call_chain (s1
);
1141 t2
= gimple_call_chain (s2
);
1142 if (!gimple_operand_equal_value_p (t1
, t2
))
1145 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1148 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1150 t1
= gimple_call_arg (s1
, i
);
1151 t2
= gimple_call_arg (s2
, i
);
1152 if (!gimple_operand_equal_value_p (t1
, t2
))
1156 lhs1
= gimple_get_lhs (s1
);
1157 lhs2
= gimple_get_lhs (s2
);
1158 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1160 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1162 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1163 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1164 return operand_equal_p (lhs1
, lhs2
, 0);
1167 lhs1
= gimple_get_lhs (s1
);
1168 lhs2
= gimple_get_lhs (s2
);
1169 if (TREE_CODE (lhs1
) != SSA_NAME
1170 && TREE_CODE (lhs2
) != SSA_NAME
)
1171 return (operand_equal_p (lhs1
, lhs2
, 0)
1172 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1173 gimple_assign_rhs1 (s2
)));
1174 else if (TREE_CODE (lhs1
) == SSA_NAME
1175 && TREE_CODE (lhs2
) == SSA_NAME
)
1176 return operand_equal_p (gimple_assign_rhs1 (s1
),
1177 gimple_assign_rhs1 (s2
), 0);
1181 t1
= gimple_cond_lhs (s1
);
1182 t2
= gimple_cond_lhs (s2
);
1183 if (!gimple_operand_equal_value_p (t1
, t2
))
1186 t1
= gimple_cond_rhs (s1
);
1187 t2
= gimple_cond_rhs (s2
);
1188 if (!gimple_operand_equal_value_p (t1
, t2
))
1191 code1
= gimple_expr_code (s1
);
1192 code2
= gimple_expr_code (s2
);
1193 inv_cond
= (bitmap_bit_p (same_succ
->inverse
, bb1
->index
)
1194 != bitmap_bit_p (same_succ
->inverse
, bb2
->index
));
1197 bool honor_nans
= HONOR_NANS (t1
);
1198 code2
= invert_tree_comparison (code2
, honor_nans
);
1200 return code1
== code2
;
1207 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1208 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1209 processed statements. */
1212 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1220 if (gsi_end_p (*gsi
))
1222 stmt
= gsi_stmt (*gsi
);
1224 lvuse
= gimple_vuse (stmt
);
1225 if (lvuse
!= NULL_TREE
)
1228 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1229 *vuse_escaped
= true;
1232 if (!stmt_local_def (stmt
))
1234 gsi_prev_nondebug (gsi
);
1238 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1242 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1244 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1245 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1246 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1247 bool vuse_escaped
= false;
1249 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1250 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1252 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1254 gimple stmt1
= gsi_stmt (gsi1
);
1255 gimple stmt2
= gsi_stmt (gsi2
);
1257 /* What could be better than to this this here is to blacklist the bb
1258 containing the stmt, when encountering the stmt f.i. in
1260 if (is_tm_ending (stmt1
)
1261 || is_tm_ending (stmt2
))
1264 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1267 gsi_prev_nondebug (&gsi1
);
1268 gsi_prev_nondebug (&gsi2
);
1269 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1270 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1273 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1276 /* If the incoming vuses are not the same, and the vuse escaped into an
1277 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1278 which potentially means the semantics of one of the blocks will be changed.
1279 TODO: make this check more precise. */
1280 if (vuse_escaped
&& vuse1
!= vuse2
)
1284 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1285 bb1
->index
, bb2
->index
);
1287 set_cluster (bb1
, bb2
);
1290 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1294 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1296 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1299 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1301 gphi
*phi
= gsi
.phi ();
1302 tree lhs
= gimple_phi_result (phi
);
1303 tree val1
= gimple_phi_arg_def (phi
, n1
);
1304 tree val2
= gimple_phi_arg_def (phi
, n2
);
1306 if (virtual_operand_p (lhs
))
1309 if (operand_equal_for_phi_arg_p (val1
, val2
))
1311 if (gvn_uses_equal (val1
, val2
))
1320 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1321 phi alternatives for BB1 and BB2 are equal. */
1324 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1331 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1333 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1334 e1
= find_edge (bb1
, succ
);
1335 e2
= find_edge (bb2
, succ
);
1336 if (e1
->flags
& EDGE_COMPLEX
1337 || e2
->flags
& EDGE_COMPLEX
)
1340 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1342 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1349 /* Return true if BB has non-vop phis. */
1352 bb_has_non_vop_phi (basic_block bb
)
1354 gimple_seq phis
= phi_nodes (bb
);
1360 if (!gimple_seq_singleton_p (phis
))
1363 phi
= gimple_seq_first_stmt (phis
);
1364 return !virtual_operand_p (gimple_phi_result (phi
));
1367 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1368 invariant that uses in FROM are dominates by their defs. */
1371 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1373 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1376 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1381 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1382 bitmap_set_bit (from_preds
, e
->src
->index
);
1383 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1384 BITMAP_FREE (from_preds
);
1386 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1389 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1390 replacement bb) and vice versa maintains the invariant that uses in the
1391 replacement are dominates by their defs. */
1394 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1396 if (BB_CLUSTER (bb1
) != NULL
)
1397 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1399 if (BB_CLUSTER (bb2
) != NULL
)
1400 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1402 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1403 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1406 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1409 find_clusters_1 (same_succ same_succ
)
1411 basic_block bb1
, bb2
;
1413 bitmap_iterator bi
, bj
;
1415 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1417 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1419 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1421 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1422 phi-nodes in bb1 and bb2, with the same alternatives for the same
1424 if (bb_has_non_vop_phi (bb1
))
1428 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1430 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1432 if (bb_has_non_vop_phi (bb2
))
1435 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1438 /* Limit quadratic behaviour. */
1440 if (nr_comparisons
> max_comparisons
)
1443 /* This is a conservative dependency check. We could test more
1444 precise for allowed replacement direction. */
1445 if (!deps_ok_for_redirect (bb1
, bb2
))
1448 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1451 find_duplicate (same_succ
, bb1
, bb2
);
1456 /* Find clusters of bbs which can be merged. */
1459 find_clusters (void)
1463 while (!worklist
.is_empty ())
1465 same
= worklist
.pop ();
1466 same
->in_worklist
= false;
1467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1469 fprintf (dump_file
, "processing worklist entry\n");
1470 same_succ_print (dump_file
, same
);
1472 find_clusters_1 (same
);
1476 /* Returns the vop phi of BB, if any. */
1479 vop_phi (basic_block bb
)
1483 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1486 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1493 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1496 replace_block_by (basic_block bb1
, basic_block bb2
)
1504 bb2_phi
= vop_phi (bb2
);
1506 /* Mark the basic block as deleted. */
1507 mark_basic_block_deleted (bb1
);
1509 /* Redirect the incoming edges of bb1 to bb2. */
1510 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1512 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1513 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1514 gcc_assert (pred_edge
!= NULL
);
1516 if (bb2_phi
== NULL
)
1519 /* The phi might have run out of capacity when the redirect added an
1520 argument, which means it could have been replaced. Refresh it. */
1521 bb2_phi
= vop_phi (bb2
);
1523 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1524 pred_edge
, UNKNOWN_LOCATION
);
1527 bb2
->frequency
+= bb1
->frequency
;
1528 if (bb2
->frequency
> BB_FREQ_MAX
)
1529 bb2
->frequency
= BB_FREQ_MAX
;
1531 bb2
->count
+= bb1
->count
;
1533 /* Merge the outgoing edge counts from bb1 onto bb2. */
1534 gcov_type out_sum
= 0;
1535 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1537 e2
= find_edge (bb2
, e1
->dest
);
1539 e2
->count
+= e1
->count
;
1540 out_sum
+= e2
->count
;
1542 /* Recompute the edge probabilities from the new merged edge count.
1543 Use the sum of the new merged edge counts computed above instead
1544 of bb2's merged count, in case there are profile count insanities
1545 making the bb count inconsistent with the edge weights. */
1546 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1548 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1551 /* Do updates that use bb1, before deleting bb1. */
1552 release_last_vdef (bb1
);
1553 same_succ_flush_bb (bb1
);
1555 delete_basic_block (bb1
);
1558 /* Bbs for which update_debug_stmt need to be called. */
1560 static bitmap update_bbs
;
1562 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1563 number of bbs removed. */
1566 apply_clusters (void)
1568 basic_block bb1
, bb2
;
1572 int nr_bbs_removed
= 0;
1574 for (i
= 0; i
< all_clusters
.length (); ++i
)
1576 c
= all_clusters
[i
];
1581 bitmap_set_bit (update_bbs
, bb2
->index
);
1583 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1584 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1586 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1587 bitmap_clear_bit (update_bbs
, bb1
->index
);
1589 replace_block_by (bb1
, bb2
);
1594 return nr_bbs_removed
;
1597 /* Resets debug statement STMT if it has uses that are not dominated by their
1601 update_debug_stmt (gimple stmt
)
1603 use_operand_p use_p
;
1607 if (!gimple_debug_bind_p (stmt
))
1610 bbuse
= gimple_bb (stmt
);
1611 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1613 tree name
= USE_FROM_PTR (use_p
);
1614 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
1615 basic_block bbdef
= gimple_bb (def_stmt
);
1616 if (bbdef
== NULL
|| bbuse
== bbdef
1617 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1620 gimple_debug_bind_reset_value (stmt
);
1626 /* Resets all debug statements that have uses that are not
1627 dominated by their defs. */
1630 update_debug_stmts (void)
1636 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1639 gimple_stmt_iterator gsi
;
1641 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1642 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1644 stmt
= gsi_stmt (gsi
);
1645 if (!is_gimple_debug (stmt
))
1647 update_debug_stmt (stmt
);
1652 /* Runs tail merge optimization. */
1655 tail_merge_optimize (unsigned int todo
)
1657 int nr_bbs_removed_total
= 0;
1659 bool loop_entered
= false;
1660 int iteration_nr
= 0;
1661 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1663 if (!flag_tree_tail_merge
1664 || max_iterations
== 0)
1667 timevar_push (TV_TREE_TAIL_MERGE
);
1669 if (!dom_info_available_p (CDI_DOMINATORS
))
1671 /* PRE can leave us with unreachable blocks, remove them now. */
1672 delete_unreachable_blocks ();
1673 calculate_dominance_info (CDI_DOMINATORS
);
1677 while (!worklist
.is_empty ())
1681 loop_entered
= true;
1682 alloc_cluster_vectors ();
1683 update_bbs
= BITMAP_ALLOC (NULL
);
1686 reset_cluster_vectors ();
1689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1690 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1693 gcc_assert (worklist
.is_empty ());
1694 if (all_clusters
.is_empty ())
1697 nr_bbs_removed
= apply_clusters ();
1698 nr_bbs_removed_total
+= nr_bbs_removed
;
1699 if (nr_bbs_removed
== 0)
1702 free_dominance_info (CDI_DOMINATORS
);
1704 if (iteration_nr
== max_iterations
)
1707 calculate_dominance_info (CDI_DOMINATORS
);
1711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1712 fprintf (dump_file
, "htab collision / search: %f\n",
1713 same_succ_htab
->collisions ());
1715 if (nr_bbs_removed_total
> 0)
1717 if (MAY_HAVE_DEBUG_STMTS
)
1719 calculate_dominance_info (CDI_DOMINATORS
);
1720 update_debug_stmts ();
1723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1725 fprintf (dump_file
, "Before TODOs.\n");
1726 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1729 mark_virtual_operands_for_renaming (cfun
);
1735 delete_cluster_vectors ();
1736 BITMAP_FREE (update_bbs
);
1739 timevar_pop (TV_TREE_TAIL_MERGE
);