Daily bump.
[official-gcc.git] / gcc / tree-ssa-tail-merge.c
blob6efe02ed4957ec5b62a4c5788f3c3d62cac0c870
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)
10 any later version.
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/>. */
21 /* Pass overview.
24 MOTIVATIONAL EXAMPLE
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];
32 intD.0 D.3915;
33 const charD.1 * restrict outputFileName.0D.3914;
35 # BLOCK 2 freq:10000
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);
48 if (D.3915_4 == 0)
49 goto <bb 3>;
50 else
51 goto <bb 4>;
52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
54 # BLOCK 3 freq:1000
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));
60 goto <bb 7>;
61 # SUCC: 7 [100.0%] (fallthru,exec)
63 # BLOCK 4 freq:9000
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);
70 if (fpD.2605_8 == 0B)
71 goto <bb 5>;
72 else
73 goto <bb 6>;
74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
76 # BLOCK 5 freq:173
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));
82 goto <bb 7>;
83 # SUCC: 7 [100.0%] (fallthru,exec)
85 # BLOCK 6 freq:8827
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)
93 # BLOCK 7 freq:10000
94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
95 6 [100.0%] (fallthru,exec)
96 # PT = nonlocal null
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),
100 .MEMD.3923_18(6)>
101 # VUSE <.MEMD.3923_11>
102 return ctxD.2601_1;
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.
110 CONTEXT
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
150 to merge the blocks.
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.
157 IMPLEMENTATION
159 1. The pass first determines all groups of blocks with the same successor
160 blocks.
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.
167 LIMITATIONS/TODO
169 - block only
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.
179 PASS PLACEMENT
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.
184 SWITCHES
186 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
188 #include "config.h"
189 #include "system.h"
190 #include "coretypes.h"
191 #include "tm.h"
192 #include "tree.h"
193 #include "stor-layout.h"
194 #include "trans-mem.h"
195 #include "tm_p.h"
196 #include "basic-block.h"
197 #include "flags.h"
198 #include "function.h"
199 #include "hash-table.h"
200 #include "tree-ssa-alias.h"
201 #include "internal-fn.h"
202 #include "tree-eh.h"
203 #include "gimple-expr.h"
204 #include "is-a.h"
205 #include "gimple.h"
206 #include "gimple-iterator.h"
207 #include "gimple-ssa.h"
208 #include "tree-cfg.h"
209 #include "tree-phinodes.h"
210 #include "ssa-iterators.h"
211 #include "tree-into-ssa.h"
212 #include "params.h"
213 #include "gimple-pretty-print.h"
214 #include "tree-ssa-sccvn.h"
215 #include "tree-dump.h"
216 #include "cfgloop.h"
217 #include "tree-pass.h"
218 #include "trans-mem.h"
220 /* Describes a group of bbs with the same successors. The successor bbs are
221 cached in succs, and the successor edge flags are cached in succ_flags.
222 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
223 it's marked in inverse.
224 Additionally, the hash value for the struct is cached in hashval, and
225 in_worklist indicates whether it's currently part of worklist. */
227 struct same_succ_def
229 /* The bbs that have the same successor bbs. */
230 bitmap bbs;
231 /* The successor bbs. */
232 bitmap succs;
233 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
234 bb. */
235 bitmap inverse;
236 /* The edge flags for each of the successor bbs. */
237 vec<int> succ_flags;
238 /* Indicates whether the struct is currently in the worklist. */
239 bool in_worklist;
240 /* The hash value of the struct. */
241 hashval_t hashval;
243 /* hash_table support. */
244 typedef same_succ_def value_type;
245 typedef same_succ_def compare_type;
246 static inline hashval_t hash (const value_type *);
247 static int equal (const value_type *, const compare_type *);
248 static void remove (value_type *);
250 typedef struct same_succ_def *same_succ;
251 typedef const struct same_succ_def *const_same_succ;
253 /* hash routine for hash_table support, returns hashval of E. */
255 inline hashval_t
256 same_succ_def::hash (const value_type *e)
258 return e->hashval;
261 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
263 struct bb_cluster_def
265 /* The bbs in the cluster. */
266 bitmap bbs;
267 /* The preds of the bbs in the cluster. */
268 bitmap preds;
269 /* Index in all_clusters vector. */
270 int index;
271 /* The bb to replace the cluster with. */
272 basic_block rep_bb;
274 typedef struct bb_cluster_def *bb_cluster;
275 typedef const struct bb_cluster_def *const_bb_cluster;
277 /* Per bb-info. */
279 struct aux_bb_info
281 /* The number of non-debug statements in the bb. */
282 int size;
283 /* The same_succ that this bb is a member of. */
284 same_succ bb_same_succ;
285 /* The cluster that this bb is a member of. */
286 bb_cluster cluster;
287 /* The vop state at the exit of a bb. This is shortlived data, used to
288 communicate data between update_block_by and update_vuses. */
289 tree vop_at_exit;
290 /* The bb that either contains or is dominated by the dependencies of the
291 bb. */
292 basic_block dep_bb;
295 /* Macros to access the fields of struct aux_bb_info. */
297 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
298 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
299 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
300 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
301 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
303 /* Returns true if the only effect a statement STMT has, is to define locally
304 used SSA_NAMEs. */
306 static bool
307 stmt_local_def (gimple stmt)
309 basic_block bb, def_bb;
310 imm_use_iterator iter;
311 use_operand_p use_p;
312 tree val;
313 def_operand_p def_p;
315 if (gimple_vdef (stmt) != NULL_TREE
316 || gimple_has_side_effects (stmt)
317 || gimple_could_trap_p_1 (stmt, false, false)
318 || gimple_vuse (stmt) != NULL_TREE)
319 return false;
321 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
322 if (def_p == NULL)
323 return false;
325 val = DEF_FROM_PTR (def_p);
326 if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
327 return false;
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)))
334 continue;
335 bb = gimple_bb (USE_STMT (use_p));
336 if (bb == def_bb)
337 continue;
339 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
340 && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
341 continue;
343 return false;
346 return true;
349 /* Let GSI skip forwards over local defs. */
351 static void
352 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
354 gimple stmt;
356 while (true)
358 if (gsi_end_p (*gsi))
359 return;
360 stmt = gsi_stmt (*gsi);
361 if (!stmt_local_def (stmt))
362 return;
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. */
372 static bool
373 gvn_uses_equal (tree val1, tree val2)
375 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
377 if (val1 == val2)
378 return true;
380 if (vn_valueize (val1) != vn_valueize (val2))
381 return false;
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. */
389 static void
390 same_succ_print (FILE *file, const same_succ e)
392 unsigned int i;
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. */
404 inline int
405 ssa_same_succ_print_traverse (same_succ *pe, FILE *file)
407 const same_succ e = *pe;
408 same_succ_print (file, e);
409 return 1;
412 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
414 static void
415 update_dep_bb (basic_block use_bb, tree val)
417 basic_block dep_bb;
419 /* Not a dep. */
420 if (TREE_CODE (val) != SSA_NAME)
421 return;
423 /* Skip use of global def. */
424 if (SSA_NAME_IS_DEFAULT_DEF (val))
425 return;
427 /* Skip use of local def. */
428 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
429 if (dep_bb == use_bb)
430 return;
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. */
439 static void
440 stmt_update_dep_bb (gimple stmt)
442 ssa_op_iter iter;
443 use_operand_p use;
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. */
451 static hashval_t
452 same_succ_hash (const_same_succ e)
454 hashval_t hashval = bitmap_hash (e->succs);
455 int flags;
456 unsigned int i;
457 unsigned int first = bitmap_first_set_bit (e->bbs);
458 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
459 int size = 0;
460 gimple_stmt_iterator gsi;
461 gimple stmt;
462 tree arg;
463 unsigned int s;
464 bitmap_iterator bs;
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))
472 continue;
473 size++;
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),
478 hashval);
479 if (!is_gimple_call (stmt))
480 continue;
481 if (gimple_call_internal_p (stmt))
482 hashval = iterative_hash_hashval_t
483 ((hashval_t) gimple_call_internal_fn (stmt), hashval);
484 else
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);
499 BB_SIZE (bb) = size;
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);
512 gsi_next (&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))
519 continue;
520 update_dep_bb (bb, val);
524 return hashval;
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. */
531 static bool
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)
538 return false;
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)
546 return false;
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;
558 gimple s1, s2;
559 basic_block bb1, bb2;
561 if (e1->hashval != e2->hashval)
562 return 0;
564 if (e1->succ_flags.length () != e2->succ_flags.length ())
565 return 0;
567 if (!bitmap_equal_p (e1->succs, e2->succs))
568 return 0;
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])
574 return 0;
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))
584 return 0;
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))
595 return 0;
596 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
597 return 0;
598 gsi_next_nondebug (&gsi1);
599 gsi_next_nondebug (&gsi2);
600 gsi_advance_fw_nondebug_nonlocal (&gsi1);
601 gsi_advance_fw_nondebug_nonlocal (&gsi2);
604 return 1;
607 /* Alloc and init a new SAME_SUCC. */
609 static 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;
620 return same;
623 /* Delete same_succ E. */
625 void
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 ();
633 XDELETE (e);
636 /* Reset same_succ SAME. */
638 static void
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
658 deleted. */
660 static bitmap deleted_bb_preds;
662 /* Prints same_succ_htab to stderr. */
664 extern void debug_same_succ (void);
665 DEBUG_FUNCTION 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. */
678 static void
679 print_worklist (FILE *file)
681 unsigned int i;
682 for (i = 0; i < worklist.length (); ++i)
683 same_succ_print (file, worklist[i]);
686 /* Adds SAME to worklist. */
688 static void
689 add_to_worklist (same_succ same)
691 if (same->in_worklist)
692 return;
694 if (bitmap_count_bits (same->bbs) < 2)
695 return;
697 same->in_worklist = true;
698 worklist.safe_push (same);
701 /* Add BB to same_succ_htab. */
703 static void
704 find_same_succ_bb (basic_block bb, same_succ *same_p)
706 unsigned int j;
707 bitmap_iterator bj;
708 same_succ same = *same_p;
709 same_succ *slot;
710 edge_iterator ei;
711 edge e;
713 if (bb == NULL
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)
722 return;
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);
736 if (*slot == NULL)
738 *slot = same;
739 BB_SAME_SUCC (bb) = same;
740 add_to_worklist (same);
741 *same_p = NULL;
743 else
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. */
756 static void
757 find_same_succ (void)
759 same_succ same = same_succ_alloc ();
760 basic_block bb;
762 FOR_EACH_BB_FN (bb, cfun)
764 find_same_succ_bb (bb, &same);
765 if (same == NULL)
766 same = same_succ_alloc ();
769 same_succ_def::remove (same);
772 /* Initializes worklist administration. */
774 static void
775 init_worklist (void)
777 alloc_aux_for_blocks (sizeof (struct aux_bb_info));
778 same_succ_htab.create (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));
783 find_same_succ ();
785 if (dump_file && (dump_flags & TDF_DETAILS))
787 fprintf (dump_file, "initial worklist:\n");
788 print_worklist (dump_file);
792 /* Deletes worklist administration. */
794 static void
795 delete_worklist (void)
797 free_aux_for_blocks ();
798 same_succ_htab.dispose ();
799 XDELETEVEC (same_succ_edge_flags);
800 same_succ_edge_flags = NULL;
801 BITMAP_FREE (deleted_bbs);
802 BITMAP_FREE (deleted_bb_preds);
803 worklist.release ();
806 /* Mark BB as deleted, and mark its predecessors. */
808 static void
809 mark_basic_block_deleted (basic_block bb)
811 edge e;
812 edge_iterator ei;
814 bitmap_set_bit (deleted_bbs, bb->index);
816 FOR_EACH_EDGE (e, ei, bb->preds)
817 bitmap_set_bit (deleted_bb_preds, e->src->index);
820 /* Removes BB from its corresponding same_succ. */
822 static void
823 same_succ_flush_bb (basic_block bb)
825 same_succ same = BB_SAME_SUCC (bb);
826 BB_SAME_SUCC (bb) = NULL;
827 if (bitmap_single_bit_set_p (same->bbs))
828 same_succ_htab.remove_elt_with_hash (same, same->hashval);
829 else
830 bitmap_clear_bit (same->bbs, bb->index);
833 /* Removes all bbs in BBS from their corresponding same_succ. */
835 static void
836 same_succ_flush_bbs (bitmap bbs)
838 unsigned int i;
839 bitmap_iterator bi;
841 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
842 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
845 /* Release the last vdef in BB, either normal or phi result. */
847 static void
848 release_last_vdef (basic_block bb)
850 gimple_stmt_iterator i;
852 for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
854 gimple stmt = gsi_stmt (i);
855 if (gimple_vdef (stmt) == NULL_TREE)
856 continue;
858 mark_virtual_operand_for_renaming (gimple_vdef (stmt));
859 return;
862 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
864 gimple phi = gsi_stmt (i);
865 tree res = gimple_phi_result (phi);
867 if (!virtual_operand_p (res))
868 continue;
870 mark_virtual_phi_result_for_renaming (phi);
871 return;
876 /* For deleted_bb_preds, find bbs with same successors. */
878 static void
879 update_worklist (void)
881 unsigned int i;
882 bitmap_iterator bi;
883 basic_block bb;
884 same_succ same;
886 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
887 bitmap_clear (deleted_bbs);
889 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
890 same_succ_flush_bbs (deleted_bb_preds);
892 same = same_succ_alloc ();
893 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
895 bb = BASIC_BLOCK_FOR_FN (cfun, i);
896 gcc_assert (bb != NULL);
897 find_same_succ_bb (bb, &same);
898 if (same == NULL)
899 same = same_succ_alloc ();
901 same_succ_def::remove (same);
902 bitmap_clear (deleted_bb_preds);
905 /* Prints cluster C to FILE. */
907 static void
908 print_cluster (FILE *file, bb_cluster c)
910 if (c == NULL)
911 return;
912 bitmap_print (file, c->bbs, "bbs:", "\n");
913 bitmap_print (file, c->preds, "preds:", "\n");
916 /* Prints cluster C to stderr. */
918 extern void debug_cluster (bb_cluster);
919 DEBUG_FUNCTION void
920 debug_cluster (bb_cluster c)
922 print_cluster (stderr, c);
925 /* Update C->rep_bb, given that BB is added to the cluster. */
927 static void
928 update_rep_bb (bb_cluster c, basic_block bb)
930 /* Initial. */
931 if (c->rep_bb == NULL)
933 c->rep_bb = bb;
934 return;
937 /* Current needs no deps, keep it. */
938 if (BB_DEP_BB (c->rep_bb) == NULL)
939 return;
941 /* Bb needs no deps, change rep_bb. */
942 if (BB_DEP_BB (bb) == NULL)
944 c->rep_bb = bb;
945 return;
948 /* Bb needs last deps earlier than current, change rep_bb. A potential
949 problem with this, is that the first deps might also be earlier, which
950 would mean we prefer longer lifetimes for the deps. To be able to check
951 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
952 BB_DEP_BB, which is really BB_LAST_DEP_BB.
953 The benefit of choosing the bb with last deps earlier, is that it can
954 potentially be used as replacement for more bbs. */
955 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
956 c->rep_bb = bb;
959 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
961 static void
962 add_bb_to_cluster (bb_cluster c, basic_block bb)
964 edge e;
965 edge_iterator ei;
967 bitmap_set_bit (c->bbs, bb->index);
969 FOR_EACH_EDGE (e, ei, bb->preds)
970 bitmap_set_bit (c->preds, e->src->index);
972 update_rep_bb (c, bb);
975 /* Allocate and init new cluster. */
977 static bb_cluster
978 new_cluster (void)
980 bb_cluster c;
981 c = XCNEW (struct bb_cluster_def);
982 c->bbs = BITMAP_ALLOC (NULL);
983 c->preds = BITMAP_ALLOC (NULL);
984 c->rep_bb = NULL;
985 return c;
988 /* Delete clusters. */
990 static void
991 delete_cluster (bb_cluster c)
993 if (c == NULL)
994 return;
995 BITMAP_FREE (c->bbs);
996 BITMAP_FREE (c->preds);
997 XDELETE (c);
1001 /* Array that contains all clusters. */
1003 static vec<bb_cluster> all_clusters;
1005 /* Allocate all cluster vectors. */
1007 static void
1008 alloc_cluster_vectors (void)
1010 all_clusters.create (n_basic_blocks_for_fn (cfun));
1013 /* Reset all cluster vectors. */
1015 static void
1016 reset_cluster_vectors (void)
1018 unsigned int i;
1019 basic_block bb;
1020 for (i = 0; i < all_clusters.length (); ++i)
1021 delete_cluster (all_clusters[i]);
1022 all_clusters.truncate (0);
1023 FOR_EACH_BB_FN (bb, cfun)
1024 BB_CLUSTER (bb) = NULL;
1027 /* Delete all cluster vectors. */
1029 static void
1030 delete_cluster_vectors (void)
1032 unsigned int i;
1033 for (i = 0; i < all_clusters.length (); ++i)
1034 delete_cluster (all_clusters[i]);
1035 all_clusters.release ();
1038 /* Merge cluster C2 into C1. */
1040 static void
1041 merge_clusters (bb_cluster c1, bb_cluster c2)
1043 bitmap_ior_into (c1->bbs, c2->bbs);
1044 bitmap_ior_into (c1->preds, c2->preds);
1047 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1048 all_clusters, or merge c with existing cluster. */
1050 static void
1051 set_cluster (basic_block bb1, basic_block bb2)
1053 basic_block merge_bb, other_bb;
1054 bb_cluster merge, old, c;
1056 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1058 c = new_cluster ();
1059 add_bb_to_cluster (c, bb1);
1060 add_bb_to_cluster (c, bb2);
1061 BB_CLUSTER (bb1) = c;
1062 BB_CLUSTER (bb2) = c;
1063 c->index = all_clusters.length ();
1064 all_clusters.safe_push (c);
1066 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1068 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1069 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1070 merge = BB_CLUSTER (merge_bb);
1071 add_bb_to_cluster (merge, other_bb);
1072 BB_CLUSTER (other_bb) = merge;
1074 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1076 unsigned int i;
1077 bitmap_iterator bi;
1079 old = BB_CLUSTER (bb2);
1080 merge = BB_CLUSTER (bb1);
1081 merge_clusters (merge, old);
1082 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1083 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
1084 all_clusters[old->index] = NULL;
1085 update_rep_bb (merge, old->rep_bb);
1086 delete_cluster (old);
1088 else
1089 gcc_unreachable ();
1092 /* Return true if gimple operands T1 and T2 have the same value. */
1094 static bool
1095 gimple_operand_equal_value_p (tree t1, tree t2)
1097 if (t1 == t2)
1098 return true;
1100 if (t1 == NULL_TREE
1101 || t2 == NULL_TREE)
1102 return false;
1104 if (operand_equal_p (t1, t2, 0))
1105 return true;
1107 return gvn_uses_equal (t1, t2);
1110 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1111 gimple_bb (s2) are members of SAME_SUCC. */
1113 static bool
1114 gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
1116 unsigned int i;
1117 tree lhs1, lhs2;
1118 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1119 tree t1, t2;
1120 bool inv_cond;
1121 enum tree_code code1, code2;
1123 if (gimple_code (s1) != gimple_code (s2))
1124 return false;
1126 switch (gimple_code (s1))
1128 case GIMPLE_CALL:
1129 if (!gimple_call_same_target_p (s1, s2))
1130 return false;
1132 t1 = gimple_call_chain (s1);
1133 t2 = gimple_call_chain (s2);
1134 if (!gimple_operand_equal_value_p (t1, t2))
1135 return false;
1137 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1138 return false;
1140 for (i = 0; i < gimple_call_num_args (s1); ++i)
1142 t1 = gimple_call_arg (s1, i);
1143 t2 = gimple_call_arg (s2, i);
1144 if (!gimple_operand_equal_value_p (t1, t2))
1145 return false;
1148 lhs1 = gimple_get_lhs (s1);
1149 lhs2 = gimple_get_lhs (s2);
1150 if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1151 return true;
1152 if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1153 return false;
1154 if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1155 return vn_valueize (lhs1) == vn_valueize (lhs2);
1156 return operand_equal_p (lhs1, lhs2, 0);
1158 case GIMPLE_ASSIGN:
1159 lhs1 = gimple_get_lhs (s1);
1160 lhs2 = gimple_get_lhs (s2);
1161 if (TREE_CODE (lhs1) != SSA_NAME
1162 && TREE_CODE (lhs2) != SSA_NAME)
1163 return (operand_equal_p (lhs1, lhs2, 0)
1164 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1165 gimple_assign_rhs1 (s2)));
1166 else if (TREE_CODE (lhs1) == SSA_NAME
1167 && TREE_CODE (lhs2) == SSA_NAME)
1168 return operand_equal_p (gimple_assign_rhs1 (s1),
1169 gimple_assign_rhs1 (s2), 0);
1170 return false;
1172 case GIMPLE_COND:
1173 t1 = gimple_cond_lhs (s1);
1174 t2 = gimple_cond_lhs (s2);
1175 if (!gimple_operand_equal_value_p (t1, t2))
1176 return false;
1178 t1 = gimple_cond_rhs (s1);
1179 t2 = gimple_cond_rhs (s2);
1180 if (!gimple_operand_equal_value_p (t1, t2))
1181 return false;
1183 code1 = gimple_expr_code (s1);
1184 code2 = gimple_expr_code (s2);
1185 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1186 != bitmap_bit_p (same_succ->inverse, bb2->index));
1187 if (inv_cond)
1189 bool honor_nans
1190 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
1191 code2 = invert_tree_comparison (code2, honor_nans);
1193 return code1 == code2;
1195 default:
1196 return false;
1200 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1201 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1202 processed statements. */
1204 static void
1205 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1206 bool *vuse_escaped)
1208 gimple stmt;
1209 tree lvuse;
1211 while (true)
1213 if (gsi_end_p (*gsi))
1214 return;
1215 stmt = gsi_stmt (*gsi);
1217 lvuse = gimple_vuse (stmt);
1218 if (lvuse != NULL_TREE)
1220 *vuse = lvuse;
1221 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1222 *vuse_escaped = true;
1225 if (!stmt_local_def (stmt))
1226 return;
1227 gsi_prev_nondebug (gsi);
1231 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1232 clusters them. */
1234 static void
1235 find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
1237 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1238 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1239 tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1240 bool vuse_escaped = false;
1242 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1243 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1245 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1247 gimple stmt1 = gsi_stmt (gsi1);
1248 gimple stmt2 = gsi_stmt (gsi2);
1250 /* What could be better than to this this here is to blacklist the bb
1251 containing the stmt, when encountering the stmt f.i. in
1252 same_succ_hash. */
1253 if (is_tm_ending (stmt1)
1254 || is_tm_ending (stmt2))
1255 return;
1257 if (!gimple_equal_p (same_succ, stmt1, stmt2))
1258 return;
1260 gsi_prev_nondebug (&gsi1);
1261 gsi_prev_nondebug (&gsi2);
1262 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1263 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1266 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1267 return;
1269 /* If the incoming vuses are not the same, and the vuse escaped into an
1270 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1271 which potentially means the semantics of one of the blocks will be changed.
1272 TODO: make this check more precise. */
1273 if (vuse_escaped && vuse1 != vuse2)
1274 return;
1276 if (dump_file)
1277 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1278 bb1->index, bb2->index);
1280 set_cluster (bb1, bb2);
1283 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1284 E2 are equal. */
1286 static bool
1287 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1289 int n1 = e1->dest_idx, n2 = e2->dest_idx;
1290 gimple_stmt_iterator gsi;
1292 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1294 gimple phi = gsi_stmt (gsi);
1295 tree lhs = gimple_phi_result (phi);
1296 tree val1 = gimple_phi_arg_def (phi, n1);
1297 tree val2 = gimple_phi_arg_def (phi, n2);
1299 if (virtual_operand_p (lhs))
1300 continue;
1302 if (operand_equal_for_phi_arg_p (val1, val2))
1303 continue;
1304 if (gvn_uses_equal (val1, val2))
1305 continue;
1307 return false;
1310 return true;
1313 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1314 phi alternatives for BB1 and BB2 are equal. */
1316 static bool
1317 same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
1319 unsigned int s;
1320 bitmap_iterator bs;
1321 edge e1, e2;
1322 basic_block succ;
1324 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1326 succ = BASIC_BLOCK_FOR_FN (cfun, s);
1327 e1 = find_edge (bb1, succ);
1328 e2 = find_edge (bb2, succ);
1329 if (e1->flags & EDGE_COMPLEX
1330 || e2->flags & EDGE_COMPLEX)
1331 return false;
1333 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1334 the same value. */
1335 if (!same_phi_alternatives_1 (succ, e1, e2))
1336 return false;
1339 return true;
1342 /* Return true if BB has non-vop phis. */
1344 static bool
1345 bb_has_non_vop_phi (basic_block bb)
1347 gimple_seq phis = phi_nodes (bb);
1348 gimple phi;
1350 if (phis == NULL)
1351 return false;
1353 if (!gimple_seq_singleton_p (phis))
1354 return true;
1356 phi = gimple_seq_first_stmt (phis);
1357 return !virtual_operand_p (gimple_phi_result (phi));
1360 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1361 invariant that uses in FROM are dominates by their defs. */
1363 static bool
1364 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1366 basic_block cd, dep_bb = BB_DEP_BB (to);
1367 edge_iterator ei;
1368 edge e;
1369 bitmap from_preds = BITMAP_ALLOC (NULL);
1371 if (dep_bb == NULL)
1372 return true;
1374 FOR_EACH_EDGE (e, ei, from->preds)
1375 bitmap_set_bit (from_preds, e->src->index);
1376 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1377 BITMAP_FREE (from_preds);
1379 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1382 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1383 replacement bb) and vice versa maintains the invariant that uses in the
1384 replacement are dominates by their defs. */
1386 static bool
1387 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1389 if (BB_CLUSTER (bb1) != NULL)
1390 bb1 = BB_CLUSTER (bb1)->rep_bb;
1392 if (BB_CLUSTER (bb2) != NULL)
1393 bb2 = BB_CLUSTER (bb2)->rep_bb;
1395 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1396 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1399 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1401 static void
1402 find_clusters_1 (same_succ same_succ)
1404 basic_block bb1, bb2;
1405 unsigned int i, j;
1406 bitmap_iterator bi, bj;
1407 int nr_comparisons;
1408 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1410 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1412 bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
1414 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1415 phi-nodes in bb1 and bb2, with the same alternatives for the same
1416 preds. */
1417 if (bb_has_non_vop_phi (bb1))
1418 continue;
1420 nr_comparisons = 0;
1421 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1423 bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1425 if (bb_has_non_vop_phi (bb2))
1426 continue;
1428 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1429 continue;
1431 /* Limit quadratic behaviour. */
1432 nr_comparisons++;
1433 if (nr_comparisons > max_comparisons)
1434 break;
1436 /* This is a conservative dependency check. We could test more
1437 precise for allowed replacement direction. */
1438 if (!deps_ok_for_redirect (bb1, bb2))
1439 continue;
1441 if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1442 continue;
1444 find_duplicate (same_succ, bb1, bb2);
1449 /* Find clusters of bbs which can be merged. */
1451 static void
1452 find_clusters (void)
1454 same_succ same;
1456 while (!worklist.is_empty ())
1458 same = worklist.pop ();
1459 same->in_worklist = false;
1460 if (dump_file && (dump_flags & TDF_DETAILS))
1462 fprintf (dump_file, "processing worklist entry\n");
1463 same_succ_print (dump_file, same);
1465 find_clusters_1 (same);
1469 /* Returns the vop phi of BB, if any. */
1471 static gimple
1472 vop_phi (basic_block bb)
1474 gimple stmt;
1475 gimple_stmt_iterator gsi;
1476 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1478 stmt = gsi_stmt (gsi);
1479 if (! virtual_operand_p (gimple_phi_result (stmt)))
1480 continue;
1481 return stmt;
1483 return NULL;
1486 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1488 static void
1489 replace_block_by (basic_block bb1, basic_block bb2)
1491 edge pred_edge;
1492 edge e1, e2;
1493 edge_iterator ei;
1494 unsigned int i;
1495 gimple bb2_phi;
1497 bb2_phi = vop_phi (bb2);
1499 /* Mark the basic block as deleted. */
1500 mark_basic_block_deleted (bb1);
1502 /* Redirect the incoming edges of bb1 to bb2. */
1503 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1505 pred_edge = EDGE_PRED (bb1, i - 1);
1506 pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1507 gcc_assert (pred_edge != NULL);
1509 if (bb2_phi == NULL)
1510 continue;
1512 /* The phi might have run out of capacity when the redirect added an
1513 argument, which means it could have been replaced. Refresh it. */
1514 bb2_phi = vop_phi (bb2);
1516 add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1517 pred_edge, UNKNOWN_LOCATION);
1520 bb2->frequency += bb1->frequency;
1521 if (bb2->frequency > BB_FREQ_MAX)
1522 bb2->frequency = BB_FREQ_MAX;
1524 bb2->count += bb1->count;
1526 /* Merge the outgoing edge counts from bb1 onto bb2. */
1527 gcov_type out_sum = 0;
1528 FOR_EACH_EDGE (e1, ei, bb1->succs)
1530 e2 = find_edge (bb2, e1->dest);
1531 gcc_assert (e2);
1532 e2->count += e1->count;
1533 out_sum += e2->count;
1535 /* Recompute the edge probabilities from the new merged edge count.
1536 Use the sum of the new merged edge counts computed above instead
1537 of bb2's merged count, in case there are profile count insanities
1538 making the bb count inconsistent with the edge weights. */
1539 FOR_EACH_EDGE (e2, ei, bb2->succs)
1541 e2->probability = GCOV_COMPUTE_SCALE (e2->count, out_sum);
1544 /* Do updates that use bb1, before deleting bb1. */
1545 release_last_vdef (bb1);
1546 same_succ_flush_bb (bb1);
1548 delete_basic_block (bb1);
1551 /* Bbs for which update_debug_stmt need to be called. */
1553 static bitmap update_bbs;
1555 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1556 number of bbs removed. */
1558 static int
1559 apply_clusters (void)
1561 basic_block bb1, bb2;
1562 bb_cluster c;
1563 unsigned int i, j;
1564 bitmap_iterator bj;
1565 int nr_bbs_removed = 0;
1567 for (i = 0; i < all_clusters.length (); ++i)
1569 c = all_clusters[i];
1570 if (c == NULL)
1571 continue;
1573 bb2 = c->rep_bb;
1574 bitmap_set_bit (update_bbs, bb2->index);
1576 bitmap_clear_bit (c->bbs, bb2->index);
1577 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1579 bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1580 bitmap_clear_bit (update_bbs, bb1->index);
1582 replace_block_by (bb1, bb2);
1583 nr_bbs_removed++;
1587 return nr_bbs_removed;
1590 /* Resets debug statement STMT if it has uses that are not dominated by their
1591 defs. */
1593 static void
1594 update_debug_stmt (gimple stmt)
1596 use_operand_p use_p;
1597 ssa_op_iter oi;
1598 basic_block bbdef, bbuse;
1599 gimple def_stmt;
1600 tree name;
1602 if (!gimple_debug_bind_p (stmt))
1603 return;
1605 bbuse = gimple_bb (stmt);
1606 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1608 name = USE_FROM_PTR (use_p);
1609 gcc_assert (TREE_CODE (name) == SSA_NAME);
1611 def_stmt = SSA_NAME_DEF_STMT (name);
1612 gcc_assert (def_stmt != NULL);
1614 bbdef = gimple_bb (def_stmt);
1615 if (bbdef == NULL || bbuse == bbdef
1616 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1617 continue;
1619 gimple_debug_bind_reset_value (stmt);
1620 update_stmt (stmt);
1624 /* Resets all debug statements that have uses that are not
1625 dominated by their defs. */
1627 static void
1628 update_debug_stmts (void)
1630 basic_block bb;
1631 bitmap_iterator bi;
1632 unsigned int i;
1634 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1636 gimple stmt;
1637 gimple_stmt_iterator gsi;
1639 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1640 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1642 stmt = gsi_stmt (gsi);
1643 if (!is_gimple_debug (stmt))
1644 continue;
1645 update_debug_stmt (stmt);
1650 /* Runs tail merge optimization. */
1652 unsigned int
1653 tail_merge_optimize (unsigned int todo)
1655 int nr_bbs_removed_total = 0;
1656 int nr_bbs_removed;
1657 bool loop_entered = false;
1658 int iteration_nr = 0;
1659 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1661 if (!flag_tree_tail_merge
1662 || max_iterations == 0
1663 /* We try to be conservative with respect to loop structure, since:
1664 - the cases where tail-merging could both affect loop structure and be
1665 beneficial are rare,
1666 - it prevents us from having to fixup the loops using
1667 loops_state_set (LOOPS_NEED_FIXUP), and
1668 - keeping loop structure may allow us to simplify the pass.
1669 In order to be conservative, we need loop information. In rare cases
1670 (about 7 test-cases in the g++ testsuite) there is none (because
1671 loop_optimizer_finalize has been called before tail-merge, and
1672 PROP_loops is not set), so we bail out. */
1673 || current_loops == NULL)
1674 return 0;
1676 timevar_push (TV_TREE_TAIL_MERGE);
1678 if (!dom_info_available_p (CDI_DOMINATORS))
1680 /* PRE can leave us with unreachable blocks, remove them now. */
1681 delete_unreachable_blocks ();
1682 calculate_dominance_info (CDI_DOMINATORS);
1684 init_worklist ();
1686 while (!worklist.is_empty ())
1688 if (!loop_entered)
1690 loop_entered = true;
1691 alloc_cluster_vectors ();
1692 update_bbs = BITMAP_ALLOC (NULL);
1694 else
1695 reset_cluster_vectors ();
1697 iteration_nr++;
1698 if (dump_file && (dump_flags & TDF_DETAILS))
1699 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1701 find_clusters ();
1702 gcc_assert (worklist.is_empty ());
1703 if (all_clusters.is_empty ())
1704 break;
1706 nr_bbs_removed = apply_clusters ();
1707 nr_bbs_removed_total += nr_bbs_removed;
1708 if (nr_bbs_removed == 0)
1709 break;
1711 free_dominance_info (CDI_DOMINATORS);
1713 if (iteration_nr == max_iterations)
1714 break;
1716 calculate_dominance_info (CDI_DOMINATORS);
1717 update_worklist ();
1720 if (dump_file && (dump_flags & TDF_DETAILS))
1721 fprintf (dump_file, "htab collision / search: %f\n",
1722 same_succ_htab.collisions ());
1724 if (nr_bbs_removed_total > 0)
1726 if (MAY_HAVE_DEBUG_STMTS)
1728 calculate_dominance_info (CDI_DOMINATORS);
1729 update_debug_stmts ();
1732 if (dump_file && (dump_flags & TDF_DETAILS))
1734 fprintf (dump_file, "Before TODOs.\n");
1735 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1738 todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow);
1739 mark_virtual_operands_for_renaming (cfun);
1742 delete_worklist ();
1743 if (loop_entered)
1745 delete_cluster_vectors ();
1746 BITMAP_FREE (update_bbs);
1749 timevar_pop (TV_TREE_TAIL_MERGE);
1751 return todo;