gcc/tree-ssa-tail-merge.c

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