OSDN Git Service

a501b0778a20709a719898863b3cd875d54ee251
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-tail-merge.c
1 /* Tail merging for gimple.
2    Copyright (C) 2011 Free Software Foundation, Inc.
3    Contributed by Tom de Vries (tom@codesourcery.com)
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>.  */
20
21 /* Pass overview.
22
23
24    MOTIVATIONAL EXAMPLE
25
26    gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
27
28    hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
29    {
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;
34
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)
53
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)
62
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)
75
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)
84
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)
92
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
97
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%]
104    }
105
106    bb 3 and bb 5 can be merged.  The blocks have different predecessors, but the
107    same successors, and the same operations.
108
109
110    CONTEXT
111
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.
119
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.
126
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.
132
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.
136
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.
143
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.
151
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.
155
156
157    IMPLEMENTATION
158
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.
165
166
167    LIMITATIONS/TODO
168
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.
177
178
179    SWITCHES
180
181    - ftree-tail-merge.  On at -O2.  We may have to enable it only at -Os.  */
182
183 #include "config.h"
184 #include "system.h"
185 #include "coretypes.h"
186 #include "tm.h"
187 #include "tree.h"
188 #include "tm_p.h"
189 #include "basic-block.h"
190 #include "output.h"
191 #include "flags.h"
192 #include "function.h"
193 #include "tree-flow.h"
194 #include "timevar.h"
195 #include "bitmap.h"
196 #include "tree-ssa-alias.h"
197 #include "params.h"
198 #include "tree-pretty-print.h"
199 #include "hashtab.h"
200 #include "gimple-pretty-print.h"
201 #include "tree-ssa-sccvn.h"
202 #include "tree-dump.h"
203
204 /* Describes a group of bbs with the same successors.  The successor bbs are
205    cached in succs, and the successor edge flags are cached in succ_flags.
206    If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
207    it's marked in inverse.
208    Additionally, the hash value for the struct is cached in hashval, and
209    in_worklist indicates whether it's currently part of worklist.  */
210
211 struct same_succ_def
212 {
213   /* The bbs that have the same successor bbs.  */
214   bitmap bbs;
215   /* The successor bbs.  */
216   bitmap succs;
217   /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
218      bb.  */
219   bitmap inverse;
220   /* The edge flags for each of the successor bbs.  */
221   VEC (int, heap) *succ_flags;
222   /* Indicates whether the struct is currently in the worklist.  */
223   bool in_worklist;
224   /* The hash value of the struct.  */
225   hashval_t hashval;
226 };
227 typedef struct same_succ_def *same_succ;
228 typedef const struct same_succ_def *const_same_succ;
229
230 /* A group of bbs where 1 bb from bbs can replace the other bbs.  */
231
232 struct bb_cluster_def
233 {
234   /* The bbs in the cluster.  */
235   bitmap bbs;
236   /* The preds of the bbs in the cluster.  */
237   bitmap preds;
238   /* Index in all_clusters vector.  */
239   int index;
240   /* The bb to replace the cluster with.  */
241   basic_block rep_bb;
242 };
243 typedef struct bb_cluster_def *bb_cluster;
244 typedef const struct bb_cluster_def *const_bb_cluster;
245
246 /* Per bb-info.  */
247
248 struct aux_bb_info
249 {
250   /* The number of non-debug statements in the bb.  */
251   int size;
252   /* The same_succ that this bb is a member of.  */
253   same_succ bb_same_succ;
254   /* The cluster that this bb is a member of.  */
255   bb_cluster cluster;
256   /* The vop state at the exit of a bb.  This is shortlived data, used to
257      communicate data between update_block_by and update_vuses.  */
258   tree vop_at_exit;
259   /* The bb that either contains or is dominated by the dependencies of the
260      bb.  */
261   basic_block dep_bb;
262 };
263
264 /* Macros to access the fields of struct aux_bb_info.  */
265
266 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
267 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
268 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
269 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
270 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
271
272 /* VAL1 and VAL2 are either:
273    - uses in BB1 and BB2, or
274    - phi alternatives for BB1 and BB2.
275    Return true if the uses have the same gvn value.  */
276
277 static bool
278 gvn_uses_equal (tree val1, tree val2)
279 {
280   gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
281
282   if (val1 == val2)
283     return true;
284
285   if (vn_valueize (val1) != vn_valueize (val2))
286     return false;
287
288   return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
289           && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
290 }
291
292 /* Prints E to FILE.  */
293
294 static void
295 same_succ_print (FILE *file, const same_succ e)
296 {
297   unsigned int i;
298   bitmap_print (file, e->bbs, "bbs:", "\n");
299   bitmap_print (file, e->succs, "succs:", "\n");
300   bitmap_print (file, e->inverse, "inverse:", "\n");
301   fprintf (file, "flags:");
302   for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
303     fprintf (file, " %x", VEC_index (int, e->succ_flags, i));
304   fprintf (file, "\n");
305 }
306
307 /* Prints same_succ VE to VFILE.  */
308
309 static int
310 same_succ_print_traverse (void **ve, void *vfile)
311 {
312   const same_succ e = *((const same_succ *)ve);
313   FILE *file = ((FILE*)vfile);
314   same_succ_print (file, e);
315   return 1;
316 }
317
318 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB.  */
319
320 static void
321 update_dep_bb (basic_block use_bb, tree val)
322 {
323   basic_block dep_bb;
324
325   /* Not a dep.  */
326   if (TREE_CODE (val) != SSA_NAME)
327     return;
328
329   /* Skip use of global def.  */
330   if (SSA_NAME_IS_DEFAULT_DEF (val))
331     return;
332
333   /* Skip use of local def.  */
334   dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
335   if (dep_bb == use_bb)
336     return;
337
338   if (BB_DEP_BB (use_bb) == NULL
339       || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
340     BB_DEP_BB (use_bb) = dep_bb;
341 }
342
343 /* Update BB_DEP_BB, given the dependencies in STMT.  */
344
345 static void
346 stmt_update_dep_bb (gimple stmt)
347 {
348   ssa_op_iter iter;
349   use_operand_p use;
350
351   FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
352     update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
353 }
354
355 /* Returns whether VAL is used in the same bb as in which it is defined, or
356    in the phi of a successor bb.  */
357
358 static bool
359 local_def (tree val)
360 {
361   gimple stmt, def_stmt;
362   basic_block bb, def_bb;
363   imm_use_iterator iter;
364   bool res;
365
366   if (TREE_CODE (val) != SSA_NAME)
367     return false;
368   def_stmt = SSA_NAME_DEF_STMT (val);
369   def_bb = gimple_bb (def_stmt);
370
371   res = true;
372   FOR_EACH_IMM_USE_STMT (stmt, iter, val)
373     {
374       bb = gimple_bb (stmt);
375       if (bb == def_bb)
376         continue;
377       if (gimple_code (stmt) == GIMPLE_PHI
378           && find_edge (def_bb, bb))
379         continue;
380       res = false;
381       BREAK_FROM_IMM_USE_STMT (iter);
382     }
383   return res;
384 }
385
386 /* Calculates hash value for same_succ VE.  */
387
388 static hashval_t
389 same_succ_hash (const void *ve)
390 {
391   const_same_succ e = (const_same_succ)ve;
392   hashval_t hashval = bitmap_hash (e->succs);
393   int flags;
394   unsigned int i;
395   unsigned int first = bitmap_first_set_bit (e->bbs);
396   basic_block bb = BASIC_BLOCK (first);
397   int size = 0;
398   gimple_stmt_iterator gsi;
399   gimple stmt;
400   tree arg;
401   unsigned int s;
402   bitmap_iterator bs;
403
404   for (gsi = gsi_start_nondebug_bb (bb);
405        !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
406     {
407       stmt = gsi_stmt (gsi);
408       stmt_update_dep_bb (stmt);
409       if (is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
410           && !gimple_has_side_effects (stmt))
411         continue;
412       size++;
413
414       hashval = iterative_hash_hashval_t (gimple_code (stmt), hashval);
415       if (is_gimple_assign (stmt))
416         hashval = iterative_hash_hashval_t (gimple_assign_rhs_code (stmt),
417                                             hashval);
418       if (!is_gimple_call (stmt))
419         continue;
420       if (gimple_call_internal_p (stmt))
421         hashval = iterative_hash_hashval_t
422           ((hashval_t) gimple_call_internal_fn (stmt), hashval);
423       else
424         hashval = iterative_hash_expr (gimple_call_fn (stmt), hashval);
425       for (i = 0; i < gimple_call_num_args (stmt); i++)
426         {
427           arg = gimple_call_arg (stmt, i);
428           arg = vn_valueize (arg);
429           hashval = iterative_hash_expr (arg, hashval);
430         }
431     }
432
433   hashval = iterative_hash_hashval_t (size, hashval);
434   BB_SIZE (bb) = size;
435
436   for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
437     {
438       flags = VEC_index (int, e->succ_flags, i);
439       flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
440       hashval = iterative_hash_hashval_t (flags, hashval);
441     }
442
443   EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
444     {
445       int n = find_edge (bb, BASIC_BLOCK (s))->dest_idx;
446       for (gsi = gsi_start_phis (BASIC_BLOCK (s)); !gsi_end_p (gsi);
447            gsi_next (&gsi))
448         {
449           gimple phi = gsi_stmt (gsi);
450           tree lhs = gimple_phi_result (phi);
451           tree val = gimple_phi_arg_def (phi, n);
452
453           if (!is_gimple_reg (lhs))
454             continue;
455           update_dep_bb (bb, val);
456         }
457     }
458
459   return hashval;
460 }
461
462 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
463    are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
464    the other edge flags.  */
465
466 static bool
467 inverse_flags (const_same_succ e1, const_same_succ e2)
468 {
469   int f1a, f1b, f2a, f2b;
470   int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
471
472   if (VEC_length (int, e1->succ_flags) != 2)
473     return false;
474
475   f1a = VEC_index (int, e1->succ_flags, 0);
476   f1b = VEC_index (int, e1->succ_flags, 1);
477   f2a = VEC_index (int, e2->succ_flags, 0);
478   f2b = VEC_index (int, e2->succ_flags, 1);
479
480   if (f1a == f2a && f1b == f2b)
481     return false;
482
483   return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
484 }
485
486 /* Compares SAME_SUCCs VE1 and VE2.  */
487
488 static int
489 same_succ_equal (const void *ve1, const void *ve2)
490 {
491   const_same_succ e1 = (const_same_succ)ve1;
492   const_same_succ e2 = (const_same_succ)ve2;
493   unsigned int i, first1, first2;
494   gimple_stmt_iterator gsi1, gsi2;
495   gimple s1, s2;
496   basic_block bb1, bb2;
497
498   if (e1->hashval != e2->hashval)
499     return 0;
500
501   if (VEC_length (int, e1->succ_flags) != VEC_length (int, e2->succ_flags))
502     return 0;
503
504   if (!bitmap_equal_p (e1->succs, e2->succs))
505     return 0;
506
507   if (!inverse_flags (e1, e2))
508     {
509       for (i = 0; i < VEC_length (int, e1->succ_flags); ++i)
510         if (VEC_index (int, e1->succ_flags, i)
511             != VEC_index (int, e1->succ_flags, i))
512           return 0;
513     }
514
515   first1 = bitmap_first_set_bit (e1->bbs);
516   first2 = bitmap_first_set_bit (e2->bbs);
517
518   bb1 = BASIC_BLOCK (first1);
519   bb2 = BASIC_BLOCK (first2);
520
521   if (BB_SIZE (bb1) != BB_SIZE (bb2))
522     return 0;
523
524   gsi1 = gsi_start_nondebug_bb (bb1);
525   gsi2 = gsi_start_nondebug_bb (bb2);
526   while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
527     {
528       s1 = gsi_stmt (gsi1);
529       s2 = gsi_stmt (gsi2);
530       if (gimple_code (s1) != gimple_code (s2))
531         return 0;
532       if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
533         return 0;
534       gsi_next_nondebug (&gsi1);
535       gsi_next_nondebug (&gsi2);
536     }
537
538   return 1;
539 }
540
541 /* Alloc and init a new SAME_SUCC.  */
542
543 static same_succ
544 same_succ_alloc (void)
545 {
546   same_succ same = XNEW (struct same_succ_def);
547
548   same->bbs = BITMAP_ALLOC (NULL);
549   same->succs = BITMAP_ALLOC (NULL);
550   same->inverse = BITMAP_ALLOC (NULL);
551   same->succ_flags = VEC_alloc (int, heap, 10);
552   same->in_worklist = false;
553
554   return same;
555 }
556
557 /* Delete same_succ VE.  */
558
559 static void
560 same_succ_delete (void *ve)
561 {
562   same_succ e = (same_succ)ve;
563
564   BITMAP_FREE (e->bbs);
565   BITMAP_FREE (e->succs);
566   BITMAP_FREE (e->inverse);
567   VEC_free (int, heap, e->succ_flags);
568
569   XDELETE (ve);
570 }
571
572 /* Reset same_succ SAME.  */
573
574 static void
575 same_succ_reset (same_succ same)
576 {
577   bitmap_clear (same->bbs);
578   bitmap_clear (same->succs);
579   bitmap_clear (same->inverse);
580   VEC_truncate (int, same->succ_flags, 0);
581 }
582
583 /* Hash table with all same_succ entries.  */
584
585 static htab_t same_succ_htab;
586
587 /* Array that is used to store the edge flags for a successor.  */
588
589 static int *same_succ_edge_flags;
590
591 /* Bitmap that is used to mark bbs that are recently deleted.  */
592
593 static bitmap deleted_bbs;
594
595 /* Bitmap that is used to mark predecessors of bbs that are
596    deleted.  */
597
598 static bitmap deleted_bb_preds;
599
600 /* Prints same_succ_htab to stderr.  */
601
602 extern void debug_same_succ (void);
603 DEBUG_FUNCTION void
604 debug_same_succ ( void)
605 {
606   htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
607 }
608
609 DEF_VEC_P (same_succ);
610 DEF_VEC_ALLOC_P (same_succ, heap);
611
612 /* Vector of bbs to process.  */
613
614 static VEC (same_succ, heap) *worklist;
615
616 /* Prints worklist to FILE.  */
617
618 static void
619 print_worklist (FILE *file)
620 {
621   unsigned int i;
622   for (i = 0; i < VEC_length (same_succ, worklist); ++i)
623     same_succ_print (file, VEC_index (same_succ, worklist, i));
624 }
625
626 /* Adds SAME to worklist.  */
627
628 static void
629 add_to_worklist (same_succ same)
630 {
631   if (same->in_worklist)
632     return;
633
634   if (bitmap_count_bits (same->bbs) < 2)
635     return;
636
637   same->in_worklist = true;
638   VEC_safe_push (same_succ, heap, worklist, same);
639 }
640
641 /* Add BB to same_succ_htab.  */
642
643 static void
644 find_same_succ_bb (basic_block bb, same_succ *same_p)
645 {
646   unsigned int j;
647   bitmap_iterator bj;
648   same_succ same = *same_p;
649   same_succ *slot;
650   edge_iterator ei;
651   edge e;
652
653   if (bb == NULL)
654     return;
655   bitmap_set_bit (same->bbs, bb->index);
656   FOR_EACH_EDGE (e, ei, bb->succs)
657     {
658       int index = e->dest->index;
659       bitmap_set_bit (same->succs, index);
660       same_succ_edge_flags[index] = e->flags;
661     }
662   EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
663     VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
664
665   same->hashval = same_succ_hash (same);
666
667   slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
668                                                    same->hashval, INSERT);
669   if (*slot == NULL)
670     {
671       *slot = same;
672       BB_SAME_SUCC (bb) = same;
673       add_to_worklist (same);
674       *same_p = NULL;
675     }
676   else
677     {
678       bitmap_set_bit ((*slot)->bbs, bb->index);
679       BB_SAME_SUCC (bb) = *slot;
680       add_to_worklist (*slot);
681       if (inverse_flags (same, *slot))
682         bitmap_set_bit ((*slot)->inverse, bb->index);
683       same_succ_reset (same);
684     }
685 }
686
687 /* Find bbs with same successors.  */
688
689 static void
690 find_same_succ (void)
691 {
692   same_succ same = same_succ_alloc ();
693   basic_block bb;
694
695   FOR_EACH_BB (bb)
696     {
697       find_same_succ_bb (bb, &same);
698       if (same == NULL)
699         same = same_succ_alloc ();
700     }
701
702   same_succ_delete (same);
703 }
704
705 /* Initializes worklist administration.  */
706
707 static void
708 init_worklist (void)
709 {
710   alloc_aux_for_blocks (sizeof (struct aux_bb_info));
711   same_succ_htab
712     = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
713                    same_succ_delete);
714   same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
715   deleted_bbs = BITMAP_ALLOC (NULL);
716   deleted_bb_preds = BITMAP_ALLOC (NULL);
717   worklist = VEC_alloc (same_succ, heap, n_basic_blocks);
718   find_same_succ ();
719
720   if (dump_file && (dump_flags & TDF_DETAILS))
721     {
722       fprintf (dump_file, "initial worklist:\n");
723       print_worklist (dump_file);
724     }
725 }
726
727 /* Deletes worklist administration.  */
728
729 static void
730 delete_worklist (void)
731 {
732   free_aux_for_blocks ();
733   htab_delete (same_succ_htab);
734   same_succ_htab = NULL;
735   XDELETEVEC (same_succ_edge_flags);
736   same_succ_edge_flags = NULL;
737   BITMAP_FREE (deleted_bbs);
738   BITMAP_FREE (deleted_bb_preds);
739   VEC_free (same_succ, heap, worklist);
740 }
741
742 /* Mark BB as deleted, and mark its predecessors.  */
743
744 static void
745 mark_basic_block_deleted (basic_block bb)
746 {
747   edge e;
748   edge_iterator ei;
749
750   bitmap_set_bit (deleted_bbs, bb->index);
751
752   FOR_EACH_EDGE (e, ei, bb->preds)
753     bitmap_set_bit (deleted_bb_preds, e->src->index);
754 }
755
756 /* Removes BB from its corresponding same_succ.  */
757
758 static void
759 same_succ_flush_bb (basic_block bb)
760 {
761   same_succ same = BB_SAME_SUCC (bb);
762   BB_SAME_SUCC (bb) = NULL;
763   if (bitmap_single_bit_set_p (same->bbs))
764     htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
765   else
766     bitmap_clear_bit (same->bbs, bb->index);
767 }
768
769 /* Removes all bbs in BBS from their corresponding same_succ.  */
770
771 static void
772 same_succ_flush_bbs (bitmap bbs)
773 {
774   unsigned int i;
775   bitmap_iterator bi;
776
777   EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
778     same_succ_flush_bb (BASIC_BLOCK (i));
779 }
780
781 /* Release the last vdef in BB, either normal or phi result.  */
782
783 static void
784 release_last_vdef (basic_block bb)
785 {
786   gimple_stmt_iterator i;
787
788   for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
789     {
790       gimple stmt = gsi_stmt (i);
791       if (gimple_vdef (stmt) == NULL_TREE)
792         continue;
793
794       mark_virtual_operand_for_renaming (gimple_vdef (stmt));
795       return;
796     }
797
798   for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
799     {
800       gimple phi = gsi_stmt (i);
801       tree res = gimple_phi_result (phi);
802
803       if (is_gimple_reg (res))
804         continue;
805
806       mark_virtual_phi_result_for_renaming (phi);
807       return;
808     }
809   
810 }
811
812 /* For deleted_bb_preds, find bbs with same successors.  */
813
814 static void
815 update_worklist (void)
816 {
817   unsigned int i;
818   bitmap_iterator bi;
819   basic_block bb;
820   same_succ same;
821
822   bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
823   bitmap_clear (deleted_bbs);
824
825   bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
826   same_succ_flush_bbs (deleted_bb_preds);
827
828   same = same_succ_alloc ();
829   EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
830     {
831       bb = BASIC_BLOCK (i);
832       gcc_assert (bb != NULL);
833       find_same_succ_bb (bb, &same);
834       if (same == NULL)
835         same = same_succ_alloc ();
836     }
837   same_succ_delete (same);
838   bitmap_clear (deleted_bb_preds);
839 }
840
841 /* Prints cluster C to FILE.  */
842
843 static void
844 print_cluster (FILE *file, bb_cluster c)
845 {
846   if (c == NULL)
847     return;
848   bitmap_print (file, c->bbs, "bbs:", "\n");
849   bitmap_print (file, c->preds, "preds:", "\n");
850 }
851
852 /* Prints cluster C to stderr.  */
853
854 extern void debug_cluster (bb_cluster);
855 DEBUG_FUNCTION void
856 debug_cluster (bb_cluster c)
857 {
858   print_cluster (stderr, c);
859 }
860
861 /* Update C->rep_bb, given that BB is added to the cluster.  */
862
863 static void
864 update_rep_bb (bb_cluster c, basic_block bb)
865 {
866   /* Initial.  */
867   if (c->rep_bb == NULL)
868     {
869       c->rep_bb = bb;
870       return;
871     }
872
873   /* Current needs no deps, keep it.  */
874   if (BB_DEP_BB (c->rep_bb) == NULL)
875     return;
876
877   /* Bb needs no deps, change rep_bb.  */
878   if (BB_DEP_BB (bb) == NULL)
879     {
880       c->rep_bb = bb;
881       return;
882     }
883
884   /* Bb needs last deps earlier than current, change rep_bb.  A potential
885      problem with this, is that the first deps might also be earlier, which
886      would mean we prefer longer lifetimes for the deps.  To be able to check
887      for this, we would have to trace BB_FIRST_DEP_BB as well, besides
888      BB_DEP_BB, which is really BB_LAST_DEP_BB.
889      The benefit of choosing the bb with last deps earlier, is that it can
890      potentially be used as replacement for more bbs.  */
891   if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
892     c->rep_bb = bb;
893 }
894
895 /* Add BB to cluster C.  Sets BB in C->bbs, and preds of BB in C->preds.  */
896
897 static void
898 add_bb_to_cluster (bb_cluster c, basic_block bb)
899 {
900   edge e;
901   edge_iterator ei;
902
903   bitmap_set_bit (c->bbs, bb->index);
904
905   FOR_EACH_EDGE (e, ei, bb->preds)
906     bitmap_set_bit (c->preds, e->src->index);
907
908   update_rep_bb (c, bb);
909 }
910
911 /* Allocate and init new cluster.  */
912
913 static bb_cluster
914 new_cluster (void)
915 {
916   bb_cluster c;
917   c = XCNEW (struct bb_cluster_def);
918   c->bbs = BITMAP_ALLOC (NULL);
919   c->preds = BITMAP_ALLOC (NULL);
920   c->rep_bb = NULL;
921   return c;
922 }
923
924 /* Delete clusters.  */
925
926 static void
927 delete_cluster (bb_cluster c)
928 {
929   if (c == NULL)
930     return;
931   BITMAP_FREE (c->bbs);
932   BITMAP_FREE (c->preds);
933   XDELETE (c);
934 }
935
936 DEF_VEC_P (bb_cluster);
937 DEF_VEC_ALLOC_P (bb_cluster, heap);
938
939 /* Array that contains all clusters.  */
940
941 static VEC (bb_cluster, heap) *all_clusters;
942
943 /* Allocate all cluster vectors.  */
944
945 static void
946 alloc_cluster_vectors (void)
947 {
948   all_clusters = VEC_alloc (bb_cluster, heap, n_basic_blocks);
949 }
950
951 /* Reset all cluster vectors.  */
952
953 static void
954 reset_cluster_vectors (void)
955 {
956   unsigned int i;
957   basic_block bb;
958   for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
959     delete_cluster (VEC_index (bb_cluster, all_clusters, i));
960   VEC_truncate (bb_cluster, all_clusters, 0);
961   FOR_EACH_BB (bb)
962     BB_CLUSTER (bb) = NULL;
963 }
964
965 /* Delete all cluster vectors.  */
966
967 static void
968 delete_cluster_vectors (void)
969 {
970   unsigned int i;
971   for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
972     delete_cluster (VEC_index (bb_cluster, all_clusters, i));
973   VEC_free (bb_cluster, heap, all_clusters);
974 }
975
976 /* Merge cluster C2 into C1.  */
977
978 static void
979 merge_clusters (bb_cluster c1, bb_cluster c2)
980 {
981   bitmap_ior_into (c1->bbs, c2->bbs);
982   bitmap_ior_into (c1->preds, c2->preds);
983 }
984
985 /* Register equivalence of BB1 and BB2 (members of cluster C).  Store c in
986    all_clusters, or merge c with existing cluster.  */
987
988 static void
989 set_cluster (basic_block bb1, basic_block bb2)
990 {
991   basic_block merge_bb, other_bb;
992   bb_cluster merge, old, c;
993
994   if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
995     {
996       c = new_cluster ();
997       add_bb_to_cluster (c, bb1);
998       add_bb_to_cluster (c, bb2);
999       BB_CLUSTER (bb1) = c;
1000       BB_CLUSTER (bb2) = c;
1001       c->index = VEC_length (bb_cluster, all_clusters);
1002       VEC_safe_push (bb_cluster, heap, all_clusters, c);
1003     }
1004   else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1005     {
1006       merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1007       other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1008       merge = BB_CLUSTER (merge_bb);
1009       add_bb_to_cluster (merge, other_bb);
1010       BB_CLUSTER (other_bb) = merge;
1011     }
1012   else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1013     {
1014       unsigned int i;
1015       bitmap_iterator bi;
1016
1017       old = BB_CLUSTER (bb2);
1018       merge = BB_CLUSTER (bb1);
1019       merge_clusters (merge, old);
1020       EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1021         BB_CLUSTER (BASIC_BLOCK (i)) = merge;
1022       VEC_replace (bb_cluster, all_clusters, old->index, NULL);
1023       update_rep_bb (merge, old->rep_bb);
1024       delete_cluster (old);
1025     }
1026   else
1027     gcc_unreachable ();
1028 }
1029
1030 /* Return true if gimple statements S1 and S2 are equal.  Gimple_bb (s1) and
1031    gimple_bb (s2) are members of SAME_SUCC.  */
1032
1033 static bool
1034 gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
1035 {
1036   unsigned int i;
1037   tree lhs1, lhs2;
1038   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1039   tree t1, t2;
1040   bool equal, inv_cond;
1041   enum tree_code code1, code2;
1042
1043   if (gimple_code (s1) != gimple_code (s2))
1044     return false;
1045
1046   switch (gimple_code (s1))
1047     {
1048     case GIMPLE_CALL:
1049       if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1050         return false;
1051       if (!gimple_call_same_target_p (s1, s2))
1052         return false;
1053
1054       equal = true;
1055       for (i = 0; i < gimple_call_num_args (s1); ++i)
1056         {
1057           t1 = gimple_call_arg (s1, i);
1058           t2 = gimple_call_arg (s2, i);
1059           if (operand_equal_p (t1, t2, 0))
1060             continue;
1061           if (gvn_uses_equal (t1, t2))
1062             continue;
1063           equal = false;
1064           break;
1065         }
1066       if (equal)
1067         return true;
1068
1069       lhs1 = gimple_get_lhs (s1);
1070       lhs2 = gimple_get_lhs (s2);
1071       return (lhs1 != NULL_TREE && lhs2 != NULL_TREE
1072               && TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME
1073               && vn_valueize (lhs1) == vn_valueize (lhs2));
1074
1075     case GIMPLE_ASSIGN:
1076       lhs1 = gimple_get_lhs (s1);
1077       lhs2 = gimple_get_lhs (s2);
1078       return (TREE_CODE (lhs1) == SSA_NAME
1079               && TREE_CODE (lhs2) == SSA_NAME
1080               && vn_valueize (lhs1) == vn_valueize (lhs2));
1081
1082     case GIMPLE_COND:
1083       t1 = gimple_cond_lhs (s1);
1084       t2 = gimple_cond_lhs (s2);
1085       if (!operand_equal_p (t1, t2, 0)
1086           && !gvn_uses_equal (t1, t2))
1087         return false;
1088
1089       t1 = gimple_cond_rhs (s1);
1090       t2 = gimple_cond_rhs (s2);
1091       if (!operand_equal_p (t1, t2, 0)
1092           && !gvn_uses_equal (t1, t2))
1093         return false;
1094
1095       code1 = gimple_expr_code (s1);
1096       code2 = gimple_expr_code (s2);
1097       inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1098                   != bitmap_bit_p (same_succ->inverse, bb2->index));
1099       if (inv_cond)
1100         {
1101           bool honor_nans
1102             = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
1103           code2 = invert_tree_comparison (code2, honor_nans);
1104         }
1105       return code1 == code2;
1106
1107     default:
1108       return false;
1109     }
1110 }
1111
1112 /* Let GSI skip backwards over local defs.  */
1113
1114 static void
1115 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
1116 {
1117   gimple stmt;
1118
1119   while (true)
1120     {
1121       if (gsi_end_p (*gsi))
1122         return;
1123       stmt = gsi_stmt (*gsi);
1124       if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
1125             && !gimple_has_side_effects (stmt)))
1126         return;
1127       gsi_prev_nondebug (gsi);
1128     }
1129 }
1130
1131 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates.  If so,
1132    clusters them.  */
1133
1134 static void
1135 find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
1136 {
1137   gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1138   gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1139
1140   gsi_advance_bw_nondebug_nonlocal (&gsi1);
1141   gsi_advance_bw_nondebug_nonlocal (&gsi2);
1142
1143   while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1144     {
1145       if (!gimple_equal_p (same_succ, gsi_stmt (gsi1), gsi_stmt (gsi2)))
1146         return;
1147
1148       gsi_prev_nondebug (&gsi1);
1149       gsi_prev_nondebug (&gsi2);
1150       gsi_advance_bw_nondebug_nonlocal (&gsi1);
1151       gsi_advance_bw_nondebug_nonlocal (&gsi2);
1152     }
1153
1154   if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1155     return;
1156
1157   if (dump_file)
1158     fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1159              bb1->index, bb2->index);
1160
1161   set_cluster (bb1, bb2);
1162 }
1163
1164 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1165    E2 are equal.  */
1166
1167 static bool
1168 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1169 {
1170   int n1 = e1->dest_idx, n2 = e2->dest_idx;
1171   gimple_stmt_iterator gsi;
1172
1173   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1174     {
1175       gimple phi = gsi_stmt (gsi);
1176       tree lhs = gimple_phi_result (phi);
1177       tree val1 = gimple_phi_arg_def (phi, n1);
1178       tree val2 = gimple_phi_arg_def (phi, n2);
1179
1180       if (!is_gimple_reg (lhs))
1181         continue;
1182
1183       if (operand_equal_for_phi_arg_p (val1, val2))
1184         continue;
1185       if (gvn_uses_equal (val1, val2))
1186         continue;
1187
1188       return false;
1189     }
1190
1191   return true;
1192 }
1193
1194 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1195    phi alternatives for BB1 and BB2 are equal.  */
1196
1197 static bool
1198 same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
1199 {
1200   unsigned int s;
1201   bitmap_iterator bs;
1202   edge e1, e2;
1203   basic_block succ;
1204
1205   EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1206     {
1207       succ = BASIC_BLOCK (s);
1208       e1 = find_edge (bb1, succ);
1209       e2 = find_edge (bb2, succ);
1210       if (e1->flags & EDGE_COMPLEX
1211           || e2->flags & EDGE_COMPLEX)
1212         return false;
1213
1214       /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1215          the same value.  */
1216       if (!same_phi_alternatives_1 (succ, e1, e2))
1217         return false;
1218     }
1219
1220   return true;
1221 }
1222
1223 /* Return true if BB has non-vop phis.  */
1224
1225 static bool
1226 bb_has_non_vop_phi (basic_block bb)
1227 {
1228   gimple_seq phis = phi_nodes (bb);
1229   gimple phi;
1230
1231   if (phis == NULL)
1232     return false;
1233
1234   if (!gimple_seq_singleton_p (phis))
1235     return true;
1236
1237   phi = gimple_seq_first_stmt (phis);
1238   return is_gimple_reg (gimple_phi_result (phi));
1239 }
1240
1241 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1242    invariant that uses in FROM are dominates by their defs.  */
1243
1244 static bool
1245 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1246 {
1247   basic_block cd, dep_bb = BB_DEP_BB (to);
1248   edge_iterator ei;
1249   edge e;
1250   bitmap from_preds = BITMAP_ALLOC (NULL);
1251
1252   if (dep_bb == NULL)
1253     return true;
1254
1255   FOR_EACH_EDGE (e, ei, from->preds)
1256     bitmap_set_bit (from_preds, e->src->index);
1257   cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1258   BITMAP_FREE (from_preds);
1259
1260   return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1261 }
1262
1263 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1264    replacement bb) and vice versa maintains the invariant that uses in the
1265    replacement are dominates by their defs.  */
1266
1267 static bool
1268 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1269 {
1270   if (BB_CLUSTER (bb1) != NULL)
1271     bb1 = BB_CLUSTER (bb1)->rep_bb;
1272
1273   if (BB_CLUSTER (bb2) != NULL)
1274     bb2 = BB_CLUSTER (bb2)->rep_bb;
1275
1276   return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1277           && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1278 }
1279
1280 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged.  */
1281
1282 static void
1283 find_clusters_1 (same_succ same_succ)
1284 {
1285   basic_block bb1, bb2;
1286   unsigned int i, j;
1287   bitmap_iterator bi, bj;
1288   int nr_comparisons;
1289   int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1290
1291   EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1292     {
1293       bb1 = BASIC_BLOCK (i);
1294
1295       /* TODO: handle blocks with phi-nodes.  We'll have to find corresponding
1296          phi-nodes in bb1 and bb2, with the same alternatives for the same
1297          preds.  */
1298       if (bb_has_non_vop_phi (bb1))
1299         continue;
1300
1301       nr_comparisons = 0;
1302       EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1303         {
1304           bb2 = BASIC_BLOCK (j);
1305
1306           if (bb_has_non_vop_phi (bb2))
1307             continue;
1308
1309           if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1310             continue;
1311
1312           /* Limit quadratic behaviour.  */
1313           nr_comparisons++;
1314           if (nr_comparisons > max_comparisons)
1315             break;
1316
1317           /* This is a conservative dependency check.  We could test more
1318              precise for allowed replacement direction.  */
1319           if (!deps_ok_for_redirect (bb1, bb2))
1320             continue;
1321
1322           if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1323             continue;
1324
1325           find_duplicate (same_succ, bb1, bb2);
1326         }
1327     }
1328 }
1329
1330 /* Find clusters of bbs which can be merged.  */
1331
1332 static void
1333 find_clusters (void)
1334 {
1335   same_succ same;
1336
1337   while (!VEC_empty (same_succ, worklist))
1338     {
1339       same = VEC_pop (same_succ, worklist);
1340       same->in_worklist = false;
1341       if (dump_file && (dump_flags & TDF_DETAILS))
1342         {
1343           fprintf (dump_file, "processing worklist entry\n");
1344           same_succ_print (dump_file, same);
1345         }
1346       find_clusters_1 (same);
1347     }
1348 }
1349
1350 /* Returns the vop phi of BB, if any.  */
1351
1352 static gimple
1353 vop_phi (basic_block bb)
1354 {
1355   gimple stmt;
1356   gimple_stmt_iterator gsi;
1357   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1358     {
1359       stmt = gsi_stmt (gsi);
1360       if (is_gimple_reg (gimple_phi_result (stmt)))
1361         continue;
1362       return stmt;
1363     }
1364   return NULL;
1365 }
1366
1367 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed.  */
1368
1369 static void
1370 replace_block_by (basic_block bb1, basic_block bb2)
1371 {
1372   edge pred_edge;
1373   unsigned int i;
1374   gimple bb2_phi;
1375
1376   bb2_phi = vop_phi (bb2);
1377
1378   /* Mark the basic block as deleted.  */
1379   mark_basic_block_deleted (bb1);
1380
1381   /* Redirect the incoming edges of bb1 to bb2.  */
1382   for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1383     {
1384       pred_edge = EDGE_PRED (bb1, i - 1);
1385       pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1386       gcc_assert (pred_edge != NULL);
1387
1388       if (bb2_phi == NULL)
1389         continue;
1390
1391       /* The phi might have run out of capacity when the redirect added an
1392          argument, which means it could have been replaced.  Refresh it.  */
1393       bb2_phi = vop_phi (bb2);
1394
1395       add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1396                    pred_edge, UNKNOWN_LOCATION);
1397     }
1398
1399   bb2->frequency += bb1->frequency;
1400   if (bb2->frequency > BB_FREQ_MAX)
1401     bb2->frequency = BB_FREQ_MAX;
1402   bb1->frequency = 0;
1403
1404   /* Do updates that use bb1, before deleting bb1.  */
1405   release_last_vdef (bb1);
1406   same_succ_flush_bb (bb1);
1407
1408   delete_basic_block (bb1);
1409 }
1410
1411 /* Bbs for which update_debug_stmt need to be called.  */
1412
1413 static bitmap update_bbs;
1414
1415 /* For each cluster in all_clusters, merge all cluster->bbs.  Returns
1416    number of bbs removed.  */
1417
1418 static int
1419 apply_clusters (void)
1420 {
1421   basic_block bb1, bb2;
1422   bb_cluster c;
1423   unsigned int i, j;
1424   bitmap_iterator bj;
1425   int nr_bbs_removed = 0;
1426
1427   for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
1428     {
1429       c = VEC_index (bb_cluster, all_clusters, i);
1430       if (c == NULL)
1431         continue;
1432
1433       bb2 = c->rep_bb;
1434       bitmap_set_bit (update_bbs, bb2->index);
1435
1436       bitmap_clear_bit (c->bbs, bb2->index);
1437       EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1438         {
1439           bb1 = BASIC_BLOCK (j);
1440           bitmap_clear_bit (update_bbs, bb1->index);
1441
1442           replace_block_by (bb1, bb2);
1443           nr_bbs_removed++;
1444         }
1445     }
1446
1447   return nr_bbs_removed;
1448 }
1449
1450 /* Resets debug statement STMT if it has uses that are not dominated by their
1451    defs.  */
1452
1453 static void
1454 update_debug_stmt (gimple stmt)
1455 {
1456   use_operand_p use_p;
1457   ssa_op_iter oi;
1458   basic_block bbdef, bbuse;
1459   gimple def_stmt;
1460   tree name;
1461
1462   if (!gimple_debug_bind_p (stmt))
1463     return;
1464
1465   bbuse = gimple_bb (stmt);
1466   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1467     {
1468       name = USE_FROM_PTR (use_p);
1469       gcc_assert (TREE_CODE (name) == SSA_NAME);
1470
1471       def_stmt = SSA_NAME_DEF_STMT (name);
1472       gcc_assert (def_stmt != NULL);
1473
1474       bbdef = gimple_bb (def_stmt);
1475       if (bbdef == NULL || bbuse == bbdef
1476           || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1477         continue;
1478
1479       gimple_debug_bind_reset_value (stmt);
1480       update_stmt (stmt);
1481     }
1482 }
1483
1484 /* Resets all debug statements that have uses that are not
1485    dominated by their defs.  */
1486
1487 static void
1488 update_debug_stmts (void)
1489 {
1490   basic_block bb;
1491   bitmap_iterator bi;
1492   unsigned int i;
1493
1494   EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1495     {
1496       gimple stmt;
1497       gimple_stmt_iterator gsi;
1498
1499       bb = BASIC_BLOCK (i);
1500       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1501         {
1502           stmt = gsi_stmt (gsi);
1503           if (!is_gimple_debug (stmt))
1504             continue;
1505           update_debug_stmt (stmt);
1506         }
1507     }
1508 }
1509
1510 /* Runs tail merge optimization.  */
1511
1512 unsigned int
1513 tail_merge_optimize (unsigned int todo)
1514 {
1515   int nr_bbs_removed_total = 0;
1516   int nr_bbs_removed;
1517   bool loop_entered = false;
1518   int iteration_nr = 0;
1519   int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1520
1521   if (!flag_tree_tail_merge || max_iterations == 0)
1522     return 0;
1523
1524   timevar_push (TV_TREE_TAIL_MERGE);
1525
1526   calculate_dominance_info (CDI_DOMINATORS);
1527   init_worklist ();
1528
1529   while (!VEC_empty (same_succ, worklist))
1530     {
1531       if (!loop_entered)
1532         {
1533           loop_entered = true;
1534           alloc_cluster_vectors ();
1535           update_bbs = BITMAP_ALLOC (NULL);
1536         }
1537       else
1538         reset_cluster_vectors ();
1539
1540       iteration_nr++;
1541       if (dump_file && (dump_flags & TDF_DETAILS))
1542         fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1543
1544       find_clusters ();
1545       gcc_assert (VEC_empty (same_succ, worklist));
1546       if (VEC_empty (bb_cluster, all_clusters))
1547         break;
1548
1549       nr_bbs_removed = apply_clusters ();
1550       nr_bbs_removed_total += nr_bbs_removed;
1551       if (nr_bbs_removed == 0)
1552         break;
1553
1554       free_dominance_info (CDI_DOMINATORS);
1555
1556       if (iteration_nr == max_iterations)
1557         break;
1558
1559       calculate_dominance_info (CDI_DOMINATORS);
1560       update_worklist ();
1561     }
1562
1563   if (dump_file && (dump_flags & TDF_DETAILS))
1564     fprintf (dump_file, "htab collision / search: %f\n",
1565              htab_collisions (same_succ_htab));
1566
1567   if (nr_bbs_removed_total > 0)
1568     {
1569       if (MAY_HAVE_DEBUG_STMTS)
1570         {
1571           calculate_dominance_info (CDI_DOMINATORS);
1572           update_debug_stmts ();
1573         }
1574
1575       if (dump_file && (dump_flags & TDF_DETAILS))
1576         {
1577           fprintf (dump_file, "Before TODOs.\n");
1578           dump_function_to_file (current_function_decl, dump_file, dump_flags);
1579         }
1580
1581       todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
1582                | TODO_dump_func);
1583       mark_sym_for_renaming (gimple_vop (cfun));
1584     }
1585
1586   delete_worklist ();
1587   if (loop_entered)
1588     {
1589       delete_cluster_vectors ();
1590       BITMAP_FREE (update_bbs);
1591     }
1592
1593   timevar_pop (TV_TREE_TAIL_MERGE);
1594
1595   return todo;
1596 }