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