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"
197 #include "basic-block.h"
199 #include "function.h"
200 #include "hash-table.h"
201 #include "tree-ssa-alias.h"
202 #include "internal-fn.h"
204 #include "gimple-expr.h"
207 #include "gimple-iterator.h"
208 #include "gimple-ssa.h"
209 #include "tree-cfg.h"
210 #include "tree-phinodes.h"
211 #include "ssa-iterators.h"
212 #include "tree-into-ssa.h"
214 #include "gimple-pretty-print.h"
215 #include "tree-ssa-sccvn.h"
216 #include "tree-dump.h"
218 #include "tree-pass.h"
219 #include "trans-mem.h"
221 /* Describes a group of bbs with the same successors. The successor bbs are
222 cached in succs, and the successor edge flags are cached in succ_flags.
223 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
224 it's marked in inverse.
225 Additionally, the hash value for the struct is cached in hashval, and
226 in_worklist indicates whether it's currently part of worklist. */
230 /* The bbs that have the same successor bbs. */
232 /* The successor bbs. */
234 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
237 /* The edge flags for each of the successor bbs. */
239 /* Indicates whether the struct is currently in the worklist. */
241 /* The hash value of the struct. */
244 /* hash_table support. */
245 typedef same_succ_def value_type
;
246 typedef same_succ_def compare_type
;
247 static inline hashval_t
hash (const value_type
*);
248 static int equal (const value_type
*, const compare_type
*);
249 static void remove (value_type
*);
251 typedef struct same_succ_def
*same_succ
;
252 typedef const struct same_succ_def
*const_same_succ
;
254 /* hash routine for hash_table support, returns hashval of E. */
257 same_succ_def::hash (const value_type
*e
)
262 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
264 struct bb_cluster_def
266 /* The bbs in the cluster. */
268 /* The preds of the bbs in the cluster. */
270 /* Index in all_clusters vector. */
272 /* The bb to replace the cluster with. */
275 typedef struct bb_cluster_def
*bb_cluster
;
276 typedef const struct bb_cluster_def
*const_bb_cluster
;
282 /* The number of non-debug statements in the bb. */
284 /* The same_succ that this bb is a member of. */
285 same_succ bb_same_succ
;
286 /* The cluster that this bb is a member of. */
288 /* The vop state at the exit of a bb. This is shortlived data, used to
289 communicate data between update_block_by and update_vuses. */
291 /* The bb that either contains or is dominated by the dependencies of the
296 /* Macros to access the fields of struct aux_bb_info. */
298 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
299 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
300 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
301 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
302 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
304 /* Returns true if the only effect a statement STMT has, is to define locally
308 stmt_local_def (gimple stmt
)
310 basic_block bb
, def_bb
;
311 imm_use_iterator iter
;
316 if (gimple_has_side_effects (stmt
)
317 || stmt_could_throw_p (stmt
)
318 || gimple_vdef (stmt
) != NULL_TREE
)
321 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
325 val
= DEF_FROM_PTR (def_p
);
326 if (val
== NULL_TREE
|| TREE_CODE (val
) != SSA_NAME
)
329 def_bb
= gimple_bb (stmt
);
331 FOR_EACH_IMM_USE_FAST (use_p
, iter
, val
)
333 if (is_gimple_debug (USE_STMT (use_p
)))
335 bb
= gimple_bb (USE_STMT (use_p
));
339 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
340 && EDGE_PRED (bb
, PHI_ARG_INDEX_FROM_USE (use_p
))->src
== def_bb
)
349 /* Let GSI skip forwards over local defs. */
352 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
)
358 if (gsi_end_p (*gsi
))
360 stmt
= gsi_stmt (*gsi
);
361 if (!stmt_local_def (stmt
))
363 gsi_next_nondebug (gsi
);
367 /* VAL1 and VAL2 are either:
368 - uses in BB1 and BB2, or
369 - phi alternatives for BB1 and BB2.
370 Return true if the uses have the same gvn value. */
373 gvn_uses_equal (tree val1
, tree val2
)
375 gcc_checking_assert (val1
!= NULL_TREE
&& val2
!= NULL_TREE
);
380 if (vn_valueize (val1
) != vn_valueize (val2
))
383 return ((TREE_CODE (val1
) == SSA_NAME
|| CONSTANT_CLASS_P (val1
))
384 && (TREE_CODE (val2
) == SSA_NAME
|| CONSTANT_CLASS_P (val2
)));
387 /* Prints E to FILE. */
390 same_succ_print (FILE *file
, const same_succ e
)
393 bitmap_print (file
, e
->bbs
, "bbs:", "\n");
394 bitmap_print (file
, e
->succs
, "succs:", "\n");
395 bitmap_print (file
, e
->inverse
, "inverse:", "\n");
396 fprintf (file
, "flags:");
397 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
398 fprintf (file
, " %x", e
->succ_flags
[i
]);
399 fprintf (file
, "\n");
402 /* Prints same_succ VE to VFILE. */
405 ssa_same_succ_print_traverse (same_succ
*pe
, FILE *file
)
407 const same_succ e
= *pe
;
408 same_succ_print (file
, e
);
412 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
415 update_dep_bb (basic_block use_bb
, tree val
)
420 if (TREE_CODE (val
) != SSA_NAME
)
423 /* Skip use of global def. */
424 if (SSA_NAME_IS_DEFAULT_DEF (val
))
427 /* Skip use of local def. */
428 dep_bb
= gimple_bb (SSA_NAME_DEF_STMT (val
));
429 if (dep_bb
== use_bb
)
432 if (BB_DEP_BB (use_bb
) == NULL
433 || dominated_by_p (CDI_DOMINATORS
, dep_bb
, BB_DEP_BB (use_bb
)))
434 BB_DEP_BB (use_bb
) = dep_bb
;
437 /* Update BB_DEP_BB, given the dependencies in STMT. */
440 stmt_update_dep_bb (gimple stmt
)
445 FOR_EACH_SSA_USE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
446 update_dep_bb (gimple_bb (stmt
), USE_FROM_PTR (use
));
449 /* Calculates hash value for same_succ VE. */
452 same_succ_hash (const_same_succ e
)
454 hashval_t hashval
= bitmap_hash (e
->succs
);
457 unsigned int first
= bitmap_first_set_bit (e
->bbs
);
458 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, first
);
460 gimple_stmt_iterator gsi
;
466 for (gsi
= gsi_start_nondebug_bb (bb
);
467 !gsi_end_p (gsi
); gsi_next_nondebug (&gsi
))
469 stmt
= gsi_stmt (gsi
);
470 stmt_update_dep_bb (stmt
);
471 if (stmt_local_def (stmt
))
475 hashval
= iterative_hash_hashval_t (gimple_code (stmt
), hashval
);
476 if (is_gimple_assign (stmt
))
477 hashval
= iterative_hash_hashval_t (gimple_assign_rhs_code (stmt
),
479 if (!is_gimple_call (stmt
))
481 if (gimple_call_internal_p (stmt
))
482 hashval
= iterative_hash_hashval_t
483 ((hashval_t
) gimple_call_internal_fn (stmt
), hashval
);
486 hashval
= iterative_hash_expr (gimple_call_fn (stmt
), hashval
);
487 if (gimple_call_chain (stmt
))
488 hashval
= iterative_hash_expr (gimple_call_chain (stmt
), hashval
);
490 for (i
= 0; i
< gimple_call_num_args (stmt
); i
++)
492 arg
= gimple_call_arg (stmt
, i
);
493 arg
= vn_valueize (arg
);
494 hashval
= iterative_hash_expr (arg
, hashval
);
498 hashval
= iterative_hash_hashval_t (size
, hashval
);
501 for (i
= 0; i
< e
->succ_flags
.length (); ++i
)
503 flags
= e
->succ_flags
[i
];
504 flags
= flags
& ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
505 hashval
= iterative_hash_hashval_t (flags
, hashval
);
508 EXECUTE_IF_SET_IN_BITMAP (e
->succs
, 0, s
, bs
)
510 int n
= find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, s
))->dest_idx
;
511 for (gsi
= gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun
, s
)); !gsi_end_p (gsi
);
514 gimple phi
= gsi_stmt (gsi
);
515 tree lhs
= gimple_phi_result (phi
);
516 tree val
= gimple_phi_arg_def (phi
, n
);
518 if (virtual_operand_p (lhs
))
520 update_dep_bb (bb
, val
);
527 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
528 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
529 the other edge flags. */
532 inverse_flags (const_same_succ e1
, const_same_succ e2
)
534 int f1a
, f1b
, f2a
, f2b
;
535 int mask
= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
537 if (e1
->succ_flags
.length () != 2)
540 f1a
= e1
->succ_flags
[0];
541 f1b
= e1
->succ_flags
[1];
542 f2a
= e2
->succ_flags
[0];
543 f2b
= e2
->succ_flags
[1];
545 if (f1a
== f2a
&& f1b
== f2b
)
548 return (f1a
& mask
) == (f2a
& mask
) && (f1b
& mask
) == (f2b
& mask
);
551 /* Compares SAME_SUCCs E1 and E2. */
554 same_succ_def::equal (const value_type
*e1
, const compare_type
*e2
)
556 unsigned int i
, first1
, first2
;
557 gimple_stmt_iterator gsi1
, gsi2
;
559 basic_block bb1
, bb2
;
561 if (e1
->hashval
!= e2
->hashval
)
564 if (e1
->succ_flags
.length () != e2
->succ_flags
.length ())
567 if (!bitmap_equal_p (e1
->succs
, e2
->succs
))
570 if (!inverse_flags (e1
, e2
))
572 for (i
= 0; i
< e1
->succ_flags
.length (); ++i
)
573 if (e1
->succ_flags
[i
] != e1
->succ_flags
[i
])
577 first1
= bitmap_first_set_bit (e1
->bbs
);
578 first2
= bitmap_first_set_bit (e2
->bbs
);
580 bb1
= BASIC_BLOCK_FOR_FN (cfun
, first1
);
581 bb2
= BASIC_BLOCK_FOR_FN (cfun
, first2
);
583 if (BB_SIZE (bb1
) != BB_SIZE (bb2
))
586 gsi1
= gsi_start_nondebug_bb (bb1
);
587 gsi2
= gsi_start_nondebug_bb (bb2
);
588 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
589 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
590 while (!(gsi_end_p (gsi1
) || gsi_end_p (gsi2
)))
592 s1
= gsi_stmt (gsi1
);
593 s2
= gsi_stmt (gsi2
);
594 if (gimple_code (s1
) != gimple_code (s2
))
596 if (is_gimple_call (s1
) && !gimple_call_same_target_p (s1
, s2
))
598 gsi_next_nondebug (&gsi1
);
599 gsi_next_nondebug (&gsi2
);
600 gsi_advance_fw_nondebug_nonlocal (&gsi1
);
601 gsi_advance_fw_nondebug_nonlocal (&gsi2
);
607 /* Alloc and init a new SAME_SUCC. */
610 same_succ_alloc (void)
612 same_succ same
= XNEW (struct same_succ_def
);
614 same
->bbs
= BITMAP_ALLOC (NULL
);
615 same
->succs
= BITMAP_ALLOC (NULL
);
616 same
->inverse
= BITMAP_ALLOC (NULL
);
617 same
->succ_flags
.create (10);
618 same
->in_worklist
= false;
623 /* Delete same_succ E. */
626 same_succ_def::remove (same_succ e
)
628 BITMAP_FREE (e
->bbs
);
629 BITMAP_FREE (e
->succs
);
630 BITMAP_FREE (e
->inverse
);
631 e
->succ_flags
.release ();
636 /* Reset same_succ SAME. */
639 same_succ_reset (same_succ same
)
641 bitmap_clear (same
->bbs
);
642 bitmap_clear (same
->succs
);
643 bitmap_clear (same
->inverse
);
644 same
->succ_flags
.truncate (0);
647 static hash_table
<same_succ_def
> *same_succ_htab
;
649 /* Array that is used to store the edge flags for a successor. */
651 static int *same_succ_edge_flags
;
653 /* Bitmap that is used to mark bbs that are recently deleted. */
655 static bitmap deleted_bbs
;
657 /* Bitmap that is used to mark predecessors of bbs that are
660 static bitmap deleted_bb_preds
;
662 /* Prints same_succ_htab to stderr. */
664 extern void debug_same_succ (void);
666 debug_same_succ ( void)
668 same_succ_htab
->traverse
<FILE *, ssa_same_succ_print_traverse
> (stderr
);
672 /* Vector of bbs to process. */
674 static vec
<same_succ
> worklist
;
676 /* Prints worklist to FILE. */
679 print_worklist (FILE *file
)
682 for (i
= 0; i
< worklist
.length (); ++i
)
683 same_succ_print (file
, worklist
[i
]);
686 /* Adds SAME to worklist. */
689 add_to_worklist (same_succ same
)
691 if (same
->in_worklist
)
694 if (bitmap_count_bits (same
->bbs
) < 2)
697 same
->in_worklist
= true;
698 worklist
.safe_push (same
);
701 /* Add BB to same_succ_htab. */
704 find_same_succ_bb (basic_block bb
, same_succ
*same_p
)
708 same_succ same
= *same_p
;
714 /* Be conservative with loop structure. It's not evident that this test
715 is sufficient. Before tail-merge, we've just called
716 loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
717 set, so there's no guarantee that the loop->latch value is still valid.
718 But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
719 start of pre, we've kept that property intact throughout pre, and are
720 keeping it throughout tail-merge using this test. */
721 || bb
->loop_father
->latch
== bb
)
723 bitmap_set_bit (same
->bbs
, bb
->index
);
724 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
726 int index
= e
->dest
->index
;
727 bitmap_set_bit (same
->succs
, index
);
728 same_succ_edge_flags
[index
] = e
->flags
;
730 EXECUTE_IF_SET_IN_BITMAP (same
->succs
, 0, j
, bj
)
731 same
->succ_flags
.safe_push (same_succ_edge_flags
[j
]);
733 same
->hashval
= same_succ_hash (same
);
735 slot
= same_succ_htab
->find_slot_with_hash (same
, same
->hashval
, INSERT
);
739 BB_SAME_SUCC (bb
) = same
;
740 add_to_worklist (same
);
745 bitmap_set_bit ((*slot
)->bbs
, bb
->index
);
746 BB_SAME_SUCC (bb
) = *slot
;
747 add_to_worklist (*slot
);
748 if (inverse_flags (same
, *slot
))
749 bitmap_set_bit ((*slot
)->inverse
, bb
->index
);
750 same_succ_reset (same
);
754 /* Find bbs with same successors. */
757 find_same_succ (void)
759 same_succ same
= same_succ_alloc ();
762 FOR_EACH_BB_FN (bb
, cfun
)
764 find_same_succ_bb (bb
, &same
);
766 same
= same_succ_alloc ();
769 same_succ_def::remove (same
);
772 /* Initializes worklist administration. */
777 alloc_aux_for_blocks (sizeof (struct aux_bb_info
));
778 same_succ_htab
= new hash_table
<same_succ_def
> (n_basic_blocks_for_fn (cfun
));
779 same_succ_edge_flags
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
780 deleted_bbs
= BITMAP_ALLOC (NULL
);
781 deleted_bb_preds
= BITMAP_ALLOC (NULL
);
782 worklist
.create (n_basic_blocks_for_fn (cfun
));
785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 fprintf (dump_file
, "initial worklist:\n");
788 print_worklist (dump_file
);
792 /* Deletes worklist administration. */
795 delete_worklist (void)
797 free_aux_for_blocks ();
798 delete same_succ_htab
;
799 same_succ_htab
= NULL
;
800 XDELETEVEC (same_succ_edge_flags
);
801 same_succ_edge_flags
= NULL
;
802 BITMAP_FREE (deleted_bbs
);
803 BITMAP_FREE (deleted_bb_preds
);
807 /* Mark BB as deleted, and mark its predecessors. */
810 mark_basic_block_deleted (basic_block bb
)
815 bitmap_set_bit (deleted_bbs
, bb
->index
);
817 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
818 bitmap_set_bit (deleted_bb_preds
, e
->src
->index
);
821 /* Removes BB from its corresponding same_succ. */
824 same_succ_flush_bb (basic_block bb
)
826 same_succ same
= BB_SAME_SUCC (bb
);
827 BB_SAME_SUCC (bb
) = NULL
;
828 if (bitmap_single_bit_set_p (same
->bbs
))
829 same_succ_htab
->remove_elt_with_hash (same
, same
->hashval
);
831 bitmap_clear_bit (same
->bbs
, bb
->index
);
834 /* Removes all bbs in BBS from their corresponding same_succ. */
837 same_succ_flush_bbs (bitmap bbs
)
842 EXECUTE_IF_SET_IN_BITMAP (bbs
, 0, i
, bi
)
843 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun
, i
));
846 /* Release the last vdef in BB, either normal or phi result. */
849 release_last_vdef (basic_block bb
)
851 gimple_stmt_iterator i
;
853 for (i
= gsi_last_bb (bb
); !gsi_end_p (i
); gsi_prev_nondebug (&i
))
855 gimple stmt
= gsi_stmt (i
);
856 if (gimple_vdef (stmt
) == NULL_TREE
)
859 mark_virtual_operand_for_renaming (gimple_vdef (stmt
));
863 for (i
= gsi_start_phis (bb
); !gsi_end_p (i
); gsi_next (&i
))
865 gimple phi
= gsi_stmt (i
);
866 tree res
= gimple_phi_result (phi
);
868 if (!virtual_operand_p (res
))
871 mark_virtual_phi_result_for_renaming (phi
);
877 /* For deleted_bb_preds, find bbs with same successors. */
880 update_worklist (void)
887 bitmap_and_compl_into (deleted_bb_preds
, deleted_bbs
);
888 bitmap_clear (deleted_bbs
);
890 bitmap_clear_bit (deleted_bb_preds
, ENTRY_BLOCK
);
891 same_succ_flush_bbs (deleted_bb_preds
);
893 same
= same_succ_alloc ();
894 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds
, 0, i
, bi
)
896 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
897 gcc_assert (bb
!= NULL
);
898 find_same_succ_bb (bb
, &same
);
900 same
= same_succ_alloc ();
902 same_succ_def::remove (same
);
903 bitmap_clear (deleted_bb_preds
);
906 /* Prints cluster C to FILE. */
909 print_cluster (FILE *file
, bb_cluster c
)
913 bitmap_print (file
, c
->bbs
, "bbs:", "\n");
914 bitmap_print (file
, c
->preds
, "preds:", "\n");
917 /* Prints cluster C to stderr. */
919 extern void debug_cluster (bb_cluster
);
921 debug_cluster (bb_cluster c
)
923 print_cluster (stderr
, c
);
926 /* Update C->rep_bb, given that BB is added to the cluster. */
929 update_rep_bb (bb_cluster c
, basic_block bb
)
932 if (c
->rep_bb
== NULL
)
938 /* Current needs no deps, keep it. */
939 if (BB_DEP_BB (c
->rep_bb
) == NULL
)
942 /* Bb needs no deps, change rep_bb. */
943 if (BB_DEP_BB (bb
) == NULL
)
949 /* Bb needs last deps earlier than current, change rep_bb. A potential
950 problem with this, is that the first deps might also be earlier, which
951 would mean we prefer longer lifetimes for the deps. To be able to check
952 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
953 BB_DEP_BB, which is really BB_LAST_DEP_BB.
954 The benefit of choosing the bb with last deps earlier, is that it can
955 potentially be used as replacement for more bbs. */
956 if (dominated_by_p (CDI_DOMINATORS
, BB_DEP_BB (c
->rep_bb
), BB_DEP_BB (bb
)))
960 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
963 add_bb_to_cluster (bb_cluster c
, basic_block bb
)
968 bitmap_set_bit (c
->bbs
, bb
->index
);
970 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
971 bitmap_set_bit (c
->preds
, e
->src
->index
);
973 update_rep_bb (c
, bb
);
976 /* Allocate and init new cluster. */
982 c
= XCNEW (struct bb_cluster_def
);
983 c
->bbs
= BITMAP_ALLOC (NULL
);
984 c
->preds
= BITMAP_ALLOC (NULL
);
989 /* Delete clusters. */
992 delete_cluster (bb_cluster c
)
996 BITMAP_FREE (c
->bbs
);
997 BITMAP_FREE (c
->preds
);
1002 /* Array that contains all clusters. */
1004 static vec
<bb_cluster
> all_clusters
;
1006 /* Allocate all cluster vectors. */
1009 alloc_cluster_vectors (void)
1011 all_clusters
.create (n_basic_blocks_for_fn (cfun
));
1014 /* Reset all cluster vectors. */
1017 reset_cluster_vectors (void)
1021 for (i
= 0; i
< all_clusters
.length (); ++i
)
1022 delete_cluster (all_clusters
[i
]);
1023 all_clusters
.truncate (0);
1024 FOR_EACH_BB_FN (bb
, cfun
)
1025 BB_CLUSTER (bb
) = NULL
;
1028 /* Delete all cluster vectors. */
1031 delete_cluster_vectors (void)
1034 for (i
= 0; i
< all_clusters
.length (); ++i
)
1035 delete_cluster (all_clusters
[i
]);
1036 all_clusters
.release ();
1039 /* Merge cluster C2 into C1. */
1042 merge_clusters (bb_cluster c1
, bb_cluster c2
)
1044 bitmap_ior_into (c1
->bbs
, c2
->bbs
);
1045 bitmap_ior_into (c1
->preds
, c2
->preds
);
1048 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1049 all_clusters, or merge c with existing cluster. */
1052 set_cluster (basic_block bb1
, basic_block bb2
)
1054 basic_block merge_bb
, other_bb
;
1055 bb_cluster merge
, old
, c
;
1057 if (BB_CLUSTER (bb1
) == NULL
&& BB_CLUSTER (bb2
) == NULL
)
1060 add_bb_to_cluster (c
, bb1
);
1061 add_bb_to_cluster (c
, bb2
);
1062 BB_CLUSTER (bb1
) = c
;
1063 BB_CLUSTER (bb2
) = c
;
1064 c
->index
= all_clusters
.length ();
1065 all_clusters
.safe_push (c
);
1067 else if (BB_CLUSTER (bb1
) == NULL
|| BB_CLUSTER (bb2
) == NULL
)
1069 merge_bb
= BB_CLUSTER (bb1
) == NULL
? bb2
: bb1
;
1070 other_bb
= BB_CLUSTER (bb1
) == NULL
? bb1
: bb2
;
1071 merge
= BB_CLUSTER (merge_bb
);
1072 add_bb_to_cluster (merge
, other_bb
);
1073 BB_CLUSTER (other_bb
) = merge
;
1075 else if (BB_CLUSTER (bb1
) != BB_CLUSTER (bb2
))
1080 old
= BB_CLUSTER (bb2
);
1081 merge
= BB_CLUSTER (bb1
);
1082 merge_clusters (merge
, old
);
1083 EXECUTE_IF_SET_IN_BITMAP (old
->bbs
, 0, i
, bi
)
1084 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun
, i
)) = merge
;
1085 all_clusters
[old
->index
] = NULL
;
1086 update_rep_bb (merge
, old
->rep_bb
);
1087 delete_cluster (old
);
1093 /* Return true if gimple operands T1 and T2 have the same value. */
1096 gimple_operand_equal_value_p (tree t1
, tree t2
)
1105 if (operand_equal_p (t1
, t2
, 0))
1108 return gvn_uses_equal (t1
, t2
);
1111 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1112 gimple_bb (s2) are members of SAME_SUCC. */
1115 gimple_equal_p (same_succ same_succ
, gimple s1
, gimple s2
)
1119 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1122 enum tree_code code1
, code2
;
1124 if (gimple_code (s1
) != gimple_code (s2
))
1127 switch (gimple_code (s1
))
1130 if (!gimple_call_same_target_p (s1
, s2
))
1133 t1
= gimple_call_chain (s1
);
1134 t2
= gimple_call_chain (s2
);
1135 if (!gimple_operand_equal_value_p (t1
, t2
))
1138 if (gimple_call_num_args (s1
) != gimple_call_num_args (s2
))
1141 for (i
= 0; i
< gimple_call_num_args (s1
); ++i
)
1143 t1
= gimple_call_arg (s1
, i
);
1144 t2
= gimple_call_arg (s2
, i
);
1145 if (!gimple_operand_equal_value_p (t1
, t2
))
1149 lhs1
= gimple_get_lhs (s1
);
1150 lhs2
= gimple_get_lhs (s2
);
1151 if (lhs1
== NULL_TREE
&& lhs2
== NULL_TREE
)
1153 if (lhs1
== NULL_TREE
|| lhs2
== NULL_TREE
)
1155 if (TREE_CODE (lhs1
) == SSA_NAME
&& TREE_CODE (lhs2
) == SSA_NAME
)
1156 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
1157 return operand_equal_p (lhs1
, lhs2
, 0);
1160 lhs1
= gimple_get_lhs (s1
);
1161 lhs2
= gimple_get_lhs (s2
);
1162 if (TREE_CODE (lhs1
) != SSA_NAME
1163 && TREE_CODE (lhs2
) != SSA_NAME
)
1165 /* If the vdef is the same, it's the same statement. */
1166 if (vn_valueize (gimple_vdef (s1
))
1167 == vn_valueize (gimple_vdef (s2
)))
1170 /* Test for structural equality. */
1171 return (operand_equal_p (lhs1
, lhs2
, 0)
1172 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1
),
1173 gimple_assign_rhs1 (s2
)));
1175 else if (TREE_CODE (lhs1
) == SSA_NAME
1176 && TREE_CODE (lhs2
) == SSA_NAME
)
1177 return vn_valueize (lhs1
) == vn_valueize (lhs2
);
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
));
1198 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1
))));
1199 code2
= invert_tree_comparison (code2
, honor_nans
);
1201 return code1
== code2
;
1208 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1209 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1210 processed statements. */
1213 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator
*gsi
, tree
*vuse
,
1221 if (gsi_end_p (*gsi
))
1223 stmt
= gsi_stmt (*gsi
);
1225 lvuse
= gimple_vuse (stmt
);
1226 if (lvuse
!= NULL_TREE
)
1229 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_DEF
))
1230 *vuse_escaped
= true;
1233 if (!stmt_local_def (stmt
))
1235 gsi_prev_nondebug (gsi
);
1239 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1243 find_duplicate (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1245 gimple_stmt_iterator gsi1
= gsi_last_nondebug_bb (bb1
);
1246 gimple_stmt_iterator gsi2
= gsi_last_nondebug_bb (bb2
);
1247 tree vuse1
= NULL_TREE
, vuse2
= NULL_TREE
;
1248 bool vuse_escaped
= false;
1250 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1251 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1253 while (!gsi_end_p (gsi1
) && !gsi_end_p (gsi2
))
1255 gimple stmt1
= gsi_stmt (gsi1
);
1256 gimple stmt2
= gsi_stmt (gsi2
);
1258 /* What could be better than to this this here is to blacklist the bb
1259 containing the stmt, when encountering the stmt f.i. in
1261 if (is_tm_ending (stmt1
)
1262 || is_tm_ending (stmt2
))
1265 if (!gimple_equal_p (same_succ
, stmt1
, stmt2
))
1268 gsi_prev_nondebug (&gsi1
);
1269 gsi_prev_nondebug (&gsi2
);
1270 gsi_advance_bw_nondebug_nonlocal (&gsi1
, &vuse1
, &vuse_escaped
);
1271 gsi_advance_bw_nondebug_nonlocal (&gsi2
, &vuse2
, &vuse_escaped
);
1274 if (!(gsi_end_p (gsi1
) && gsi_end_p (gsi2
)))
1277 /* If the incoming vuses are not the same, and the vuse escaped into an
1278 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1279 which potentially means the semantics of one of the blocks will be changed.
1280 TODO: make this check more precise. */
1281 if (vuse_escaped
&& vuse1
!= vuse2
)
1285 fprintf (dump_file
, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1286 bb1
->index
, bb2
->index
);
1288 set_cluster (bb1
, bb2
);
1291 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1295 same_phi_alternatives_1 (basic_block dest
, edge e1
, edge e2
)
1297 int n1
= e1
->dest_idx
, n2
= e2
->dest_idx
;
1298 gimple_stmt_iterator gsi
;
1300 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1302 gimple phi
= gsi_stmt (gsi
);
1303 tree lhs
= gimple_phi_result (phi
);
1304 tree val1
= gimple_phi_arg_def (phi
, n1
);
1305 tree val2
= gimple_phi_arg_def (phi
, n2
);
1307 if (virtual_operand_p (lhs
))
1310 if (operand_equal_for_phi_arg_p (val1
, val2
))
1312 if (gvn_uses_equal (val1
, val2
))
1321 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1322 phi alternatives for BB1 and BB2 are equal. */
1325 same_phi_alternatives (same_succ same_succ
, basic_block bb1
, basic_block bb2
)
1332 EXECUTE_IF_SET_IN_BITMAP (same_succ
->succs
, 0, s
, bs
)
1334 succ
= BASIC_BLOCK_FOR_FN (cfun
, s
);
1335 e1
= find_edge (bb1
, succ
);
1336 e2
= find_edge (bb2
, succ
);
1337 if (e1
->flags
& EDGE_COMPLEX
1338 || e2
->flags
& EDGE_COMPLEX
)
1341 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1343 if (!same_phi_alternatives_1 (succ
, e1
, e2
))
1350 /* Return true if BB has non-vop phis. */
1353 bb_has_non_vop_phi (basic_block bb
)
1355 gimple_seq phis
= phi_nodes (bb
);
1361 if (!gimple_seq_singleton_p (phis
))
1364 phi
= gimple_seq_first_stmt (phis
);
1365 return !virtual_operand_p (gimple_phi_result (phi
));
1368 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1369 invariant that uses in FROM are dominates by their defs. */
1372 deps_ok_for_redirect_from_bb_to_bb (basic_block from
, basic_block to
)
1374 basic_block cd
, dep_bb
= BB_DEP_BB (to
);
1377 bitmap from_preds
= BITMAP_ALLOC (NULL
);
1382 FOR_EACH_EDGE (e
, ei
, from
->preds
)
1383 bitmap_set_bit (from_preds
, e
->src
->index
);
1384 cd
= nearest_common_dominator_for_set (CDI_DOMINATORS
, from_preds
);
1385 BITMAP_FREE (from_preds
);
1387 return dominated_by_p (CDI_DOMINATORS
, dep_bb
, cd
);
1390 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1391 replacement bb) and vice versa maintains the invariant that uses in the
1392 replacement are dominates by their defs. */
1395 deps_ok_for_redirect (basic_block bb1
, basic_block bb2
)
1397 if (BB_CLUSTER (bb1
) != NULL
)
1398 bb1
= BB_CLUSTER (bb1
)->rep_bb
;
1400 if (BB_CLUSTER (bb2
) != NULL
)
1401 bb2
= BB_CLUSTER (bb2
)->rep_bb
;
1403 return (deps_ok_for_redirect_from_bb_to_bb (bb1
, bb2
)
1404 && deps_ok_for_redirect_from_bb_to_bb (bb2
, bb1
));
1407 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1410 find_clusters_1 (same_succ same_succ
)
1412 basic_block bb1
, bb2
;
1414 bitmap_iterator bi
, bj
;
1416 int max_comparisons
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS
);
1418 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, 0, i
, bi
)
1420 bb1
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1422 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1423 phi-nodes in bb1 and bb2, with the same alternatives for the same
1425 if (bb_has_non_vop_phi (bb1
))
1429 EXECUTE_IF_SET_IN_BITMAP (same_succ
->bbs
, i
+ 1, j
, bj
)
1431 bb2
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1433 if (bb_has_non_vop_phi (bb2
))
1436 if (BB_CLUSTER (bb1
) != NULL
&& BB_CLUSTER (bb1
) == BB_CLUSTER (bb2
))
1439 /* Limit quadratic behaviour. */
1441 if (nr_comparisons
> max_comparisons
)
1444 /* This is a conservative dependency check. We could test more
1445 precise for allowed replacement direction. */
1446 if (!deps_ok_for_redirect (bb1
, bb2
))
1449 if (!(same_phi_alternatives (same_succ
, bb1
, bb2
)))
1452 find_duplicate (same_succ
, bb1
, bb2
);
1457 /* Find clusters of bbs which can be merged. */
1460 find_clusters (void)
1464 while (!worklist
.is_empty ())
1466 same
= worklist
.pop ();
1467 same
->in_worklist
= false;
1468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1470 fprintf (dump_file
, "processing worklist entry\n");
1471 same_succ_print (dump_file
, same
);
1473 find_clusters_1 (same
);
1477 /* Returns the vop phi of BB, if any. */
1480 vop_phi (basic_block bb
)
1483 gimple_stmt_iterator gsi
;
1484 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1486 stmt
= gsi_stmt (gsi
);
1487 if (! virtual_operand_p (gimple_phi_result (stmt
)))
1494 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1497 replace_block_by (basic_block bb1
, basic_block bb2
)
1505 bb2_phi
= vop_phi (bb2
);
1507 /* Mark the basic block as deleted. */
1508 mark_basic_block_deleted (bb1
);
1510 /* Redirect the incoming edges of bb1 to bb2. */
1511 for (i
= EDGE_COUNT (bb1
->preds
); i
> 0 ; --i
)
1513 pred_edge
= EDGE_PRED (bb1
, i
- 1);
1514 pred_edge
= redirect_edge_and_branch (pred_edge
, bb2
);
1515 gcc_assert (pred_edge
!= NULL
);
1517 if (bb2_phi
== NULL
)
1520 /* The phi might have run out of capacity when the redirect added an
1521 argument, which means it could have been replaced. Refresh it. */
1522 bb2_phi
= vop_phi (bb2
);
1524 add_phi_arg (bb2_phi
, SSA_NAME_VAR (gimple_phi_result (bb2_phi
)),
1525 pred_edge
, UNKNOWN_LOCATION
);
1528 bb2
->frequency
+= bb1
->frequency
;
1529 if (bb2
->frequency
> BB_FREQ_MAX
)
1530 bb2
->frequency
= BB_FREQ_MAX
;
1532 bb2
->count
+= bb1
->count
;
1534 /* Merge the outgoing edge counts from bb1 onto bb2. */
1535 gcov_type out_sum
= 0;
1536 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1538 e2
= find_edge (bb2
, e1
->dest
);
1540 e2
->count
+= e1
->count
;
1541 out_sum
+= e2
->count
;
1543 /* Recompute the edge probabilities from the new merged edge count.
1544 Use the sum of the new merged edge counts computed above instead
1545 of bb2's merged count, in case there are profile count insanities
1546 making the bb count inconsistent with the edge weights. */
1547 FOR_EACH_EDGE (e2
, ei
, bb2
->succs
)
1549 e2
->probability
= GCOV_COMPUTE_SCALE (e2
->count
, out_sum
);
1552 /* Do updates that use bb1, before deleting bb1. */
1553 release_last_vdef (bb1
);
1554 same_succ_flush_bb (bb1
);
1556 delete_basic_block (bb1
);
1559 /* Bbs for which update_debug_stmt need to be called. */
1561 static bitmap update_bbs
;
1563 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1564 number of bbs removed. */
1567 apply_clusters (void)
1569 basic_block bb1
, bb2
;
1573 int nr_bbs_removed
= 0;
1575 for (i
= 0; i
< all_clusters
.length (); ++i
)
1577 c
= all_clusters
[i
];
1582 bitmap_set_bit (update_bbs
, bb2
->index
);
1584 bitmap_clear_bit (c
->bbs
, bb2
->index
);
1585 EXECUTE_IF_SET_IN_BITMAP (c
->bbs
, 0, j
, bj
)
1587 bb1
= BASIC_BLOCK_FOR_FN (cfun
, j
);
1588 bitmap_clear_bit (update_bbs
, bb1
->index
);
1590 replace_block_by (bb1
, bb2
);
1595 return nr_bbs_removed
;
1598 /* Resets debug statement STMT if it has uses that are not dominated by their
1602 update_debug_stmt (gimple stmt
)
1604 use_operand_p use_p
;
1606 basic_block bbdef
, bbuse
;
1610 if (!gimple_debug_bind_p (stmt
))
1613 bbuse
= gimple_bb (stmt
);
1614 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
1616 name
= USE_FROM_PTR (use_p
);
1617 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1619 def_stmt
= SSA_NAME_DEF_STMT (name
);
1620 gcc_assert (def_stmt
!= NULL
);
1622 bbdef
= gimple_bb (def_stmt
);
1623 if (bbdef
== NULL
|| bbuse
== bbdef
1624 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
))
1627 gimple_debug_bind_reset_value (stmt
);
1632 /* Resets all debug statements that have uses that are not
1633 dominated by their defs. */
1636 update_debug_stmts (void)
1642 EXECUTE_IF_SET_IN_BITMAP (update_bbs
, 0, i
, bi
)
1645 gimple_stmt_iterator gsi
;
1647 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1648 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1650 stmt
= gsi_stmt (gsi
);
1651 if (!is_gimple_debug (stmt
))
1653 update_debug_stmt (stmt
);
1658 /* Runs tail merge optimization. */
1661 tail_merge_optimize (unsigned int todo
)
1663 int nr_bbs_removed_total
= 0;
1665 bool loop_entered
= false;
1666 int iteration_nr
= 0;
1667 int max_iterations
= PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS
);
1669 if (!flag_tree_tail_merge
1670 || max_iterations
== 0)
1673 timevar_push (TV_TREE_TAIL_MERGE
);
1675 if (!dom_info_available_p (CDI_DOMINATORS
))
1677 /* PRE can leave us with unreachable blocks, remove them now. */
1678 delete_unreachable_blocks ();
1679 calculate_dominance_info (CDI_DOMINATORS
);
1683 while (!worklist
.is_empty ())
1687 loop_entered
= true;
1688 alloc_cluster_vectors ();
1689 update_bbs
= BITMAP_ALLOC (NULL
);
1692 reset_cluster_vectors ();
1695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1696 fprintf (dump_file
, "worklist iteration #%d\n", iteration_nr
);
1699 gcc_assert (worklist
.is_empty ());
1700 if (all_clusters
.is_empty ())
1703 nr_bbs_removed
= apply_clusters ();
1704 nr_bbs_removed_total
+= nr_bbs_removed
;
1705 if (nr_bbs_removed
== 0)
1708 free_dominance_info (CDI_DOMINATORS
);
1710 if (iteration_nr
== max_iterations
)
1713 calculate_dominance_info (CDI_DOMINATORS
);
1717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1718 fprintf (dump_file
, "htab collision / search: %f\n",
1719 same_succ_htab
->collisions ());
1721 if (nr_bbs_removed_total
> 0)
1723 if (MAY_HAVE_DEBUG_STMTS
)
1725 calculate_dominance_info (CDI_DOMINATORS
);
1726 update_debug_stmts ();
1729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1731 fprintf (dump_file
, "Before TODOs.\n");
1732 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
1735 mark_virtual_operands_for_renaming (cfun
);
1741 delete_cluster_vectors ();
1742 BITMAP_FREE (update_bbs
);
1745 timevar_pop (TV_TREE_TAIL_MERGE
);