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       /* Eventually, we'll significantly complicate the CFG by adding
1055          back edges to properly model the effects of transaction restart.
1056          For the bulk of optimization this does not matter, but what we
1057          cannot recover from is tail merging blocks between two separate
1058          transactions.  Avoid that by making commit not match.  */
1059       if (gimple_call_builtin_p (s1, BUILT_IN_TM_COMMIT))
1060         return false;
1061
1062       equal = true;
1063       for (i = 0; i < gimple_call_num_args (s1); ++i)
1064         {
1065           t1 = gimple_call_arg (s1, i);
1066           t2 = gimple_call_arg (s2, i);
1067           if (operand_equal_p (t1, t2, 0))
1068             continue;
1069           if (gvn_uses_equal (t1, t2))
1070             continue;
1071           equal = false;
1072           break;
1073         }
1074       if (equal)
1075         return true;
1076
1077       lhs1 = gimple_get_lhs (s1);
1078       lhs2 = gimple_get_lhs (s2);
1079       return (lhs1 != NULL_TREE && lhs2 != NULL_TREE
1080               && TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME
1081               && vn_valueize (lhs1) == vn_valueize (lhs2));
1082
1083     case GIMPLE_ASSIGN:
1084       lhs1 = gimple_get_lhs (s1);
1085       lhs2 = gimple_get_lhs (s2);
1086       return (TREE_CODE (lhs1) == SSA_NAME
1087               && TREE_CODE (lhs2) == SSA_NAME
1088               && vn_valueize (lhs1) == vn_valueize (lhs2));
1089
1090     case GIMPLE_COND:
1091       t1 = gimple_cond_lhs (s1);
1092       t2 = gimple_cond_lhs (s2);
1093       if (!operand_equal_p (t1, t2, 0)
1094           && !gvn_uses_equal (t1, t2))
1095         return false;
1096
1097       t1 = gimple_cond_rhs (s1);
1098       t2 = gimple_cond_rhs (s2);
1099       if (!operand_equal_p (t1, t2, 0)
1100           && !gvn_uses_equal (t1, t2))
1101         return false;
1102
1103       code1 = gimple_expr_code (s1);
1104       code2 = gimple_expr_code (s2);
1105       inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1106                   != bitmap_bit_p (same_succ->inverse, bb2->index));
1107       if (inv_cond)
1108         {
1109           bool honor_nans
1110             = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
1111           code2 = invert_tree_comparison (code2, honor_nans);
1112         }
1113       return code1 == code2;
1114
1115     default:
1116       return false;
1117     }
1118 }
1119
1120 /* Let GSI skip backwards over local defs.  */
1121
1122 static void
1123 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
1124 {
1125   gimple stmt;
1126
1127   while (true)
1128     {
1129       if (gsi_end_p (*gsi))
1130         return;
1131       stmt = gsi_stmt (*gsi);
1132       if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
1133             && !gimple_has_side_effects (stmt)))
1134         return;
1135       gsi_prev_nondebug (gsi);
1136     }
1137 }
1138
1139 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates.  If so,
1140    clusters them.  */
1141
1142 static void
1143 find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
1144 {
1145   gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1146   gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1147
1148   gsi_advance_bw_nondebug_nonlocal (&gsi1);
1149   gsi_advance_bw_nondebug_nonlocal (&gsi2);
1150
1151   while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1152     {
1153       if (!gimple_equal_p (same_succ, gsi_stmt (gsi1), gsi_stmt (gsi2)))
1154         return;
1155
1156       gsi_prev_nondebug (&gsi1);
1157       gsi_prev_nondebug (&gsi2);
1158       gsi_advance_bw_nondebug_nonlocal (&gsi1);
1159       gsi_advance_bw_nondebug_nonlocal (&gsi2);
1160     }
1161
1162   if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1163     return;
1164
1165   if (dump_file)
1166     fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1167              bb1->index, bb2->index);
1168
1169   set_cluster (bb1, bb2);
1170 }
1171
1172 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1173    E2 are equal.  */
1174
1175 static bool
1176 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1177 {
1178   int n1 = e1->dest_idx, n2 = e2->dest_idx;
1179   gimple_stmt_iterator gsi;
1180
1181   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1182     {
1183       gimple phi = gsi_stmt (gsi);
1184       tree lhs = gimple_phi_result (phi);
1185       tree val1 = gimple_phi_arg_def (phi, n1);
1186       tree val2 = gimple_phi_arg_def (phi, n2);
1187
1188       if (!is_gimple_reg (lhs))
1189         continue;
1190
1191       if (operand_equal_for_phi_arg_p (val1, val2))
1192         continue;
1193       if (gvn_uses_equal (val1, val2))
1194         continue;
1195
1196       return false;
1197     }
1198
1199   return true;
1200 }
1201
1202 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1203    phi alternatives for BB1 and BB2 are equal.  */
1204
1205 static bool
1206 same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
1207 {
1208   unsigned int s;
1209   bitmap_iterator bs;
1210   edge e1, e2;
1211   basic_block succ;
1212
1213   EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1214     {
1215       succ = BASIC_BLOCK (s);
1216       e1 = find_edge (bb1, succ);
1217       e2 = find_edge (bb2, succ);
1218       if (e1->flags & EDGE_COMPLEX
1219           || e2->flags & EDGE_COMPLEX)
1220         return false;
1221
1222       /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1223          the same value.  */
1224       if (!same_phi_alternatives_1 (succ, e1, e2))
1225         return false;
1226     }
1227
1228   return true;
1229 }
1230
1231 /* Return true if BB has non-vop phis.  */
1232
1233 static bool
1234 bb_has_non_vop_phi (basic_block bb)
1235 {
1236   gimple_seq phis = phi_nodes (bb);
1237   gimple phi;
1238
1239   if (phis == NULL)
1240     return false;
1241
1242   if (!gimple_seq_singleton_p (phis))
1243     return true;
1244
1245   phi = gimple_seq_first_stmt (phis);
1246   return is_gimple_reg (gimple_phi_result (phi));
1247 }
1248
1249 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1250    invariant that uses in FROM are dominates by their defs.  */
1251
1252 static bool
1253 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1254 {
1255   basic_block cd, dep_bb = BB_DEP_BB (to);
1256   edge_iterator ei;
1257   edge e;
1258   bitmap from_preds = BITMAP_ALLOC (NULL);
1259
1260   if (dep_bb == NULL)
1261     return true;
1262
1263   FOR_EACH_EDGE (e, ei, from->preds)
1264     bitmap_set_bit (from_preds, e->src->index);
1265   cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1266   BITMAP_FREE (from_preds);
1267
1268   return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1269 }
1270
1271 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1272    replacement bb) and vice versa maintains the invariant that uses in the
1273    replacement are dominates by their defs.  */
1274
1275 static bool
1276 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1277 {
1278   if (BB_CLUSTER (bb1) != NULL)
1279     bb1 = BB_CLUSTER (bb1)->rep_bb;
1280
1281   if (BB_CLUSTER (bb2) != NULL)
1282     bb2 = BB_CLUSTER (bb2)->rep_bb;
1283
1284   return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1285           && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1286 }
1287
1288 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged.  */
1289
1290 static void
1291 find_clusters_1 (same_succ same_succ)
1292 {
1293   basic_block bb1, bb2;
1294   unsigned int i, j;
1295   bitmap_iterator bi, bj;
1296   int nr_comparisons;
1297   int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1298
1299   EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1300     {
1301       bb1 = BASIC_BLOCK (i);
1302
1303       /* TODO: handle blocks with phi-nodes.  We'll have to find corresponding
1304          phi-nodes in bb1 and bb2, with the same alternatives for the same
1305          preds.  */
1306       if (bb_has_non_vop_phi (bb1))
1307         continue;
1308
1309       nr_comparisons = 0;
1310       EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1311         {
1312           bb2 = BASIC_BLOCK (j);
1313
1314           if (bb_has_non_vop_phi (bb2))
1315             continue;
1316
1317           if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1318             continue;
1319
1320           /* Limit quadratic behaviour.  */
1321           nr_comparisons++;
1322           if (nr_comparisons > max_comparisons)
1323             break;
1324
1325           /* This is a conservative dependency check.  We could test more
1326              precise for allowed replacement direction.  */
1327           if (!deps_ok_for_redirect (bb1, bb2))
1328             continue;
1329
1330           if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1331             continue;
1332
1333           find_duplicate (same_succ, bb1, bb2);
1334         }
1335     }
1336 }
1337
1338 /* Find clusters of bbs which can be merged.  */
1339
1340 static void
1341 find_clusters (void)
1342 {
1343   same_succ same;
1344
1345   while (!VEC_empty (same_succ, worklist))
1346     {
1347       same = VEC_pop (same_succ, worklist);
1348       same->in_worklist = false;
1349       if (dump_file && (dump_flags & TDF_DETAILS))
1350         {
1351           fprintf (dump_file, "processing worklist entry\n");
1352           same_succ_print (dump_file, same);
1353         }
1354       find_clusters_1 (same);
1355     }
1356 }
1357
1358 /* Returns the vop phi of BB, if any.  */
1359
1360 static gimple
1361 vop_phi (basic_block bb)
1362 {
1363   gimple stmt;
1364   gimple_stmt_iterator gsi;
1365   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1366     {
1367       stmt = gsi_stmt (gsi);
1368       if (is_gimple_reg (gimple_phi_result (stmt)))
1369         continue;
1370       return stmt;
1371     }
1372   return NULL;
1373 }
1374
1375 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed.  */
1376
1377 static void
1378 replace_block_by (basic_block bb1, basic_block bb2)
1379 {
1380   edge pred_edge;
1381   unsigned int i;
1382   gimple bb2_phi;
1383
1384   bb2_phi = vop_phi (bb2);
1385
1386   /* Mark the basic block as deleted.  */
1387   mark_basic_block_deleted (bb1);
1388
1389   /* Redirect the incoming edges of bb1 to bb2.  */
1390   for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1391     {
1392       pred_edge = EDGE_PRED (bb1, i - 1);
1393       pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1394       gcc_assert (pred_edge != NULL);
1395
1396       if (bb2_phi == NULL)
1397         continue;
1398
1399       /* The phi might have run out of capacity when the redirect added an
1400          argument, which means it could have been replaced.  Refresh it.  */
1401       bb2_phi = vop_phi (bb2);
1402
1403       add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1404                    pred_edge, UNKNOWN_LOCATION);
1405     }
1406
1407   bb2->frequency += bb1->frequency;
1408   if (bb2->frequency > BB_FREQ_MAX)
1409     bb2->frequency = BB_FREQ_MAX;
1410   bb1->frequency = 0;
1411
1412   /* Do updates that use bb1, before deleting bb1.  */
1413   release_last_vdef (bb1);
1414   same_succ_flush_bb (bb1);
1415
1416   delete_basic_block (bb1);
1417 }
1418
1419 /* Bbs for which update_debug_stmt need to be called.  */
1420
1421 static bitmap update_bbs;
1422
1423 /* For each cluster in all_clusters, merge all cluster->bbs.  Returns
1424    number of bbs removed.  */
1425
1426 static int
1427 apply_clusters (void)
1428 {
1429   basic_block bb1, bb2;
1430   bb_cluster c;
1431   unsigned int i, j;
1432   bitmap_iterator bj;
1433   int nr_bbs_removed = 0;
1434
1435   for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
1436     {
1437       c = VEC_index (bb_cluster, all_clusters, i);
1438       if (c == NULL)
1439         continue;
1440
1441       bb2 = c->rep_bb;
1442       bitmap_set_bit (update_bbs, bb2->index);
1443
1444       bitmap_clear_bit (c->bbs, bb2->index);
1445       EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1446         {
1447           bb1 = BASIC_BLOCK (j);
1448           bitmap_clear_bit (update_bbs, bb1->index);
1449
1450           replace_block_by (bb1, bb2);
1451           nr_bbs_removed++;
1452         }
1453     }
1454
1455   return nr_bbs_removed;
1456 }
1457
1458 /* Resets debug statement STMT if it has uses that are not dominated by their
1459    defs.  */
1460
1461 static void
1462 update_debug_stmt (gimple stmt)
1463 {
1464   use_operand_p use_p;
1465   ssa_op_iter oi;
1466   basic_block bbdef, bbuse;
1467   gimple def_stmt;
1468   tree name;
1469
1470   if (!gimple_debug_bind_p (stmt))
1471     return;
1472
1473   bbuse = gimple_bb (stmt);
1474   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1475     {
1476       name = USE_FROM_PTR (use_p);
1477       gcc_assert (TREE_CODE (name) == SSA_NAME);
1478
1479       def_stmt = SSA_NAME_DEF_STMT (name);
1480       gcc_assert (def_stmt != NULL);
1481
1482       bbdef = gimple_bb (def_stmt);
1483       if (bbdef == NULL || bbuse == bbdef
1484           || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1485         continue;
1486
1487       gimple_debug_bind_reset_value (stmt);
1488       update_stmt (stmt);
1489     }
1490 }
1491
1492 /* Resets all debug statements that have uses that are not
1493    dominated by their defs.  */
1494
1495 static void
1496 update_debug_stmts (void)
1497 {
1498   basic_block bb;
1499   bitmap_iterator bi;
1500   unsigned int i;
1501
1502   EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1503     {
1504       gimple stmt;
1505       gimple_stmt_iterator gsi;
1506
1507       bb = BASIC_BLOCK (i);
1508       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1509         {
1510           stmt = gsi_stmt (gsi);
1511           if (!is_gimple_debug (stmt))
1512             continue;
1513           update_debug_stmt (stmt);
1514         }
1515     }
1516 }
1517
1518 /* Runs tail merge optimization.  */
1519
1520 unsigned int
1521 tail_merge_optimize (unsigned int todo)
1522 {
1523   int nr_bbs_removed_total = 0;
1524   int nr_bbs_removed;
1525   bool loop_entered = false;
1526   int iteration_nr = 0;
1527   int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1528
1529   if (!flag_tree_tail_merge || max_iterations == 0)
1530     return 0;
1531
1532   timevar_push (TV_TREE_TAIL_MERGE);
1533
1534   calculate_dominance_info (CDI_DOMINATORS);
1535   init_worklist ();
1536
1537   while (!VEC_empty (same_succ, worklist))
1538     {
1539       if (!loop_entered)
1540         {
1541           loop_entered = true;
1542           alloc_cluster_vectors ();
1543           update_bbs = BITMAP_ALLOC (NULL);
1544         }
1545       else
1546         reset_cluster_vectors ();
1547
1548       iteration_nr++;
1549       if (dump_file && (dump_flags & TDF_DETAILS))
1550         fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1551
1552       find_clusters ();
1553       gcc_assert (VEC_empty (same_succ, worklist));
1554       if (VEC_empty (bb_cluster, all_clusters))
1555         break;
1556
1557       nr_bbs_removed = apply_clusters ();
1558       nr_bbs_removed_total += nr_bbs_removed;
1559       if (nr_bbs_removed == 0)
1560         break;
1561
1562       free_dominance_info (CDI_DOMINATORS);
1563
1564       if (iteration_nr == max_iterations)
1565         break;
1566
1567       calculate_dominance_info (CDI_DOMINATORS);
1568       update_worklist ();
1569     }
1570
1571   if (dump_file && (dump_flags & TDF_DETAILS))
1572     fprintf (dump_file, "htab collision / search: %f\n",
1573              htab_collisions (same_succ_htab));
1574
1575   if (nr_bbs_removed_total > 0)
1576     {
1577       if (MAY_HAVE_DEBUG_STMTS)
1578         {
1579           calculate_dominance_info (CDI_DOMINATORS);
1580           update_debug_stmts ();
1581         }
1582
1583       if (dump_file && (dump_flags & TDF_DETAILS))
1584         {
1585           fprintf (dump_file, "Before TODOs.\n");
1586           dump_function_to_file (current_function_decl, dump_file, dump_flags);
1587         }
1588
1589       todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
1590                | TODO_dump_func);
1591       mark_sym_for_renaming (gimple_vop (cfun));
1592     }
1593
1594   delete_worklist ();
1595   if (loop_entered)
1596     {
1597       delete_cluster_vectors ();
1598       BITMAP_FREE (update_bbs);
1599     }
1600
1601   timevar_pop (TV_TREE_TAIL_MERGE);
1602
1603   return todo;
1604 }