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   /* Do updates that use bb1, before deleting bb1.  */
1400   release_last_vdef (bb1);
1401   same_succ_flush_bb (bb1);
1402
1403   delete_basic_block (bb1);
1404 }
1405
1406 /* Bbs for which update_debug_stmt need to be called.  */
1407
1408 static bitmap update_bbs;
1409
1410 /* For each cluster in all_clusters, merge all cluster->bbs.  Returns
1411    number of bbs removed.  */
1412
1413 static int
1414 apply_clusters (void)
1415 {
1416   basic_block bb1, bb2;
1417   bb_cluster c;
1418   unsigned int i, j;
1419   bitmap_iterator bj;
1420   int nr_bbs_removed = 0;
1421
1422   for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
1423     {
1424       c = VEC_index (bb_cluster, all_clusters, i);
1425       if (c == NULL)
1426         continue;
1427
1428       bb2 = c->rep_bb;
1429       bitmap_set_bit (update_bbs, bb2->index);
1430
1431       bitmap_clear_bit (c->bbs, bb2->index);
1432       EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1433         {
1434           bb1 = BASIC_BLOCK (j);
1435           bitmap_clear_bit (update_bbs, bb1->index);
1436
1437           replace_block_by (bb1, bb2);
1438           nr_bbs_removed++;
1439         }
1440     }
1441
1442   return nr_bbs_removed;
1443 }
1444
1445 /* Resets debug statement STMT if it has uses that are not dominated by their
1446    defs.  */
1447
1448 static void
1449 update_debug_stmt (gimple stmt)
1450 {
1451   use_operand_p use_p;
1452   ssa_op_iter oi;
1453   basic_block bbdef, bbuse;
1454   gimple def_stmt;
1455   tree name;
1456
1457   if (!gimple_debug_bind_p (stmt))
1458     return;
1459
1460   bbuse = gimple_bb (stmt);
1461   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1462     {
1463       name = USE_FROM_PTR (use_p);
1464       gcc_assert (TREE_CODE (name) == SSA_NAME);
1465
1466       def_stmt = SSA_NAME_DEF_STMT (name);
1467       gcc_assert (def_stmt != NULL);
1468
1469       bbdef = gimple_bb (def_stmt);
1470       if (bbdef == NULL || bbuse == bbdef
1471           || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1472         continue;
1473
1474       gimple_debug_bind_reset_value (stmt);
1475       update_stmt (stmt);
1476     }
1477 }
1478
1479 /* Resets all debug statements that have uses that are not
1480    dominated by their defs.  */
1481
1482 static void
1483 update_debug_stmts (void)
1484 {
1485   basic_block bb;
1486   bitmap_iterator bi;
1487   unsigned int i;
1488
1489   EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1490     {
1491       gimple stmt;
1492       gimple_stmt_iterator gsi;
1493
1494       bb = BASIC_BLOCK (i);
1495       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1496         {
1497           stmt = gsi_stmt (gsi);
1498           if (!is_gimple_debug (stmt))
1499             continue;
1500           update_debug_stmt (stmt);
1501         }
1502     }
1503 }
1504
1505 /* Runs tail merge optimization.  */
1506
1507 unsigned int
1508 tail_merge_optimize (unsigned int todo)
1509 {
1510   int nr_bbs_removed_total = 0;
1511   int nr_bbs_removed;
1512   bool loop_entered = false;
1513   int iteration_nr = 0;
1514   int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1515
1516   if (!flag_tree_tail_merge || max_iterations == 0)
1517     return 0;
1518
1519   timevar_push (TV_TREE_TAIL_MERGE);
1520
1521   calculate_dominance_info (CDI_DOMINATORS);
1522   init_worklist ();
1523
1524   while (!VEC_empty (same_succ, worklist))
1525     {
1526       if (!loop_entered)
1527         {
1528           loop_entered = true;
1529           alloc_cluster_vectors ();
1530           update_bbs = BITMAP_ALLOC (NULL);
1531         }
1532       else
1533         reset_cluster_vectors ();
1534
1535       iteration_nr++;
1536       if (dump_file && (dump_flags & TDF_DETAILS))
1537         fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1538
1539       find_clusters ();
1540       gcc_assert (VEC_empty (same_succ, worklist));
1541       if (VEC_empty (bb_cluster, all_clusters))
1542         break;
1543
1544       nr_bbs_removed = apply_clusters ();
1545       nr_bbs_removed_total += nr_bbs_removed;
1546       if (nr_bbs_removed == 0)
1547         break;
1548
1549       free_dominance_info (CDI_DOMINATORS);
1550
1551       if (iteration_nr == max_iterations)
1552         break;
1553
1554       calculate_dominance_info (CDI_DOMINATORS);
1555       update_worklist ();
1556     }
1557
1558   if (dump_file && (dump_flags & TDF_DETAILS))
1559     fprintf (dump_file, "htab collision / search: %f\n",
1560              htab_collisions (same_succ_htab));
1561
1562   if (nr_bbs_removed_total > 0)
1563     {
1564       if (MAY_HAVE_DEBUG_STMTS)
1565         {
1566           calculate_dominance_info (CDI_DOMINATORS);
1567           update_debug_stmts ();
1568         }
1569
1570       if (dump_file && (dump_flags & TDF_DETAILS))
1571         {
1572           fprintf (dump_file, "Before TODOs.\n");
1573           dump_function_to_file (current_function_decl, dump_file, dump_flags);
1574         }
1575
1576       todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
1577                | TODO_dump_func);
1578       mark_sym_for_renaming (gimple_vop (cfun));
1579     }
1580
1581   delete_worklist ();
1582   if (loop_entered)
1583     {
1584       delete_cluster_vectors ();
1585       BITMAP_FREE (update_bbs);
1586     }
1587
1588   timevar_pop (TV_TREE_TAIL_MERGE);
1589
1590   return todo;
1591 }