gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "ggc.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "timevar.h"
  30 #include "diagnostic.h"
  31 #include "tree-flow.h"
  32 #include "tree-pass.h"
  33 #include "tree-dump.h"
  34 #include "domwalk.h"
  35 #include "flags.h"
  36
  37 /* This file implements dead store elimination.
  38
  39    A dead store is a store into a memory location which will later be
  40    overwritten by another store without any intervening loads.  In this
  41    case the earlier store can be deleted.
  42
  43    In our SSA + virtual operand world we use immediate uses of virtual
  44    operands to detect dead stores.  If a store's virtual definition
  45    is used precisely once by a later store to the same location which
  46    post dominates the first store, then the first store is dead.
  47
  48    The single use of the store's virtual definition ensures that
  49    there are no intervening aliased loads and the requirement that
  50    the second load post dominate the first ensures that if the earlier
  51    store executes, then the later stores will execute before the function
  52    exits.
  53
  54    It may help to think of this as first moving the earlier store to
  55    the point immediately before the later store.  Again, the single
  56    use of the virtual definition and the post-dominance relationship
  57    ensure that such movement would be safe.  Clearly if there are
  58    back to back stores, then the second is redundant.
  59
  60    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
  61    may also help in understanding this code since it discusses the
  62    relationship between dead store and redundant load elimination.  In
  63    fact, they are the same transformation applied to different views of
  64    the CFG.  */
  65
  66
  67 struct dse_global_data
  68 {
  69   /* This is the global bitmap for store statements.
  70
  71      Each statement has a unique ID.  When we encounter a store statement
  72      that we want to record, set the bit corresponding to the statement's
  73      unique ID in this bitmap.  */
  74   bitmap stores;
  75 };
  76
  77 /* We allocate a bitmap-per-block for stores which are encountered
  78    during the scan of that block.  This allows us to restore the
  79    global bitmap of stores when we finish processing a block.  */
  80 struct dse_block_local_data
  81 {
  82   bitmap stores;
  83 };
  84
  85 /* Basic blocks of the potentially dead store and the following
  86    store, for memory_address_same.  */
  87 struct address_walk_data
  88 {
  89   basic_block store1_bb, store2_bb;
  90 };
  91
  92 static bool gate_dse (void);
  93 static unsigned int tree_ssa_dse (void);
  94 static void dse_initialize_block_local_data (struct dom_walk_data *,
  95                                              basic_block,
  96                                              bool);
  97 static void dse_optimize_stmt (struct dom_walk_data *,
  98                                basic_block,
  99                                block_stmt_iterator);
 100 static void dse_record_phis (struct dom_walk_data *, basic_block);
 101 static void dse_finalize_block (struct dom_walk_data *, basic_block);
 102 static void record_voperand_set (bitmap, bitmap *, unsigned int);
 103
 104 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 105                                    nodes are assigned using the versions of
 106                                    ssa names they define.  */
 107
 108 /* Returns uid of statement STMT.  */
 109
 110 static unsigned
 111 get_stmt_uid (tree stmt)
 112 {
 113   if (TREE_CODE (stmt) == PHI_NODE)
 114     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 115
 116   return stmt_ann (stmt)->uid;
 117 }
 118
 119 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 120
 121 static void
 122 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 123 {
 124   /* Lazily allocate the bitmap.  Note that we do not get a notification
 125      when the block local data structures die, so we allocate the local
 126      bitmap backed by the GC system.  */
 127   if (*local == NULL)
 128     *local = BITMAP_GGC_ALLOC ();
 129
 130   /* Set the bit in the local and global bitmaps.  */
 131   bitmap_set_bit (*local, uid);
 132   bitmap_set_bit (global, uid);
 133 }
 134
 135 /* Initialize block local data structures.  */
 136
 137 static void
 138 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 139                                  basic_block bb ATTRIBUTE_UNUSED,
 140                                  bool recycled)
 141 {
 142   struct dse_block_local_data *bd
 143     = (struct dse_block_local_data *)
 144         VEC_last (void_p, walk_data->block_data_stack);
 145
 146   /* If we are given a recycled block local data structure, ensure any
 147      bitmap associated with the block is cleared.  */
 148   if (recycled)
 149     {
 150       if (bd->stores)
 151         bitmap_clear (bd->stores);
 152     }
 153 }
 154
 155 /* Helper function for memory_address_same via walk_tree.  Returns
 156    non-NULL if it finds an SSA_NAME which is part of the address,
 157    such that the definition of the SSA_NAME post-dominates the store
 158    we want to delete but not the store that we believe makes it
 159    redundant.  This indicates that the address may change between
 160    the two stores.  */
 161
 162 static tree
 163 memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
 164                       void *data)
 165 {
 166   struct address_walk_data *walk_data = (struct address_walk_data *) data;
 167   tree expr = *expr_p;
 168   tree def_stmt;
 169   basic_block def_bb;
 170
 171   if (TREE_CODE (expr) != SSA_NAME)
 172     return NULL_TREE;
 173
 174   /* If we've found a default definition, then there's no problem.  Both
 175      stores will post-dominate it.  And def_bb will be NULL.  */
 176   if (SSA_NAME_IS_DEFAULT_DEF (expr))
 177     return NULL_TREE;
 178
 179   def_stmt = SSA_NAME_DEF_STMT (expr);
 180   def_bb = bb_for_stmt (def_stmt);
 181
 182   /* DEF_STMT must dominate both stores.  So if it is in the same
 183      basic block as one, it does not post-dominate that store.  */
 184   if (walk_data->store1_bb != def_bb
 185       && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
 186     {
 187       if (walk_data->store2_bb == def_bb
 188           || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
 189                               def_bb))
 190         /* Return non-NULL to stop the walk.  */
 191         return def_stmt;
 192     }
 193
 194   return NULL_TREE;
 195 }
 196
 197 /* Return TRUE if the destination memory address in STORE1 and STORE2
 198    might be modified after STORE1, before control reaches STORE2.  */
 199
 200 static bool
 201 memory_address_same (tree store1, tree store2)
 202 {
 203   struct address_walk_data walk_data;
 204
 205   walk_data.store1_bb = bb_for_stmt (store1);
 206   walk_data.store2_bb = bb_for_stmt (store2);
 207
 208   return (walk_tree (&GIMPLE_STMT_OPERAND (store1, 0), memory_ssa_name_same,
 209                      &walk_data, NULL)
 210           == NULL);
 211 }
 212
 213 /* Return true if there is a stmt that kills the lhs of STMT and is in the
 214    virtual def-use chain of STMT without a use inbetween the kill and STMT.
 215    Returns false if no such stmt is found.
 216    *FIRST_USE_P is set to the first use of the single virtual def of
 217    STMT.  *USE_P is set to the vop killed by *USE_STMT.  */
 218
 219 static bool
 220 get_kill_of_stmt_lhs (tree stmt,
 221                       use_operand_p * first_use_p,
 222                       use_operand_p * use_p, tree * use_stmt)
 223 {
 224   tree lhs;
 225
 226   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
 227
 228   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 229
 230   /* We now walk the chain of single uses of the single VDEFs.
 231      We succeeded finding a kill if the lhs of the use stmt is
 232      equal to the original lhs.  We can keep walking to the next
 233      use if there are no possible uses of the original lhs in
 234      the stmt.  */
 235   do
 236     {
 237       tree use_lhs, use_rhs;
 238       def_operand_p def_p;
 239
 240       /* The stmt must have a single VDEF.  */
 241       def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_VDEF);
 242       if (def_p == NULL_DEF_OPERAND_P)
 243         return false;
 244
 245       /* Get the single immediate use of the def.  */
 246       if (!single_imm_use (DEF_FROM_PTR (def_p), first_use_p, &stmt))
 247         return false;
 248       first_use_p = use_p;
 249
 250       /* If there are possible hidden uses, give up.  */
 251       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 252         return false;
 253       use_rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 254       if (TREE_CODE (use_rhs) == CALL_EXPR
 255           || (!is_gimple_min_invariant (use_rhs)
 256               && TREE_CODE (use_rhs) != SSA_NAME))
 257         return false;
 258
 259       /* If the use stmts lhs matches the original lhs we have
 260          found the kill, otherwise continue walking.  */
 261       use_lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 262       if (operand_equal_p (use_lhs, lhs, 0))
 263         {
 264           *use_stmt = stmt;
 265           return true;
 266         }
 267     }
 268   while (1);
 269 }
 270
 271 /* A helper of dse_optimize_stmt.
 272    Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
 273    use, and that one use is another VDEF clobbering the first one.
 274
 275    Return TRUE if the above conditions are met, otherwise FALSE.  */
 276
 277 static bool
 278 dse_possible_dead_store_p (tree stmt,
 279                            use_operand_p *first_use_p,
 280                            use_operand_p *use_p,
 281                            tree *use_stmt,
 282                            struct dse_global_data *dse_gd,
 283                            struct dse_block_local_data *bd)
 284 {
 285   ssa_op_iter op_iter;
 286   bool fail = false;
 287   def_operand_p var1;
 288   vuse_vec_p vv;
 289   tree defvar = NULL_TREE, temp;
 290   tree prev_defvar = NULL_TREE;
 291   stmt_ann_t ann = stmt_ann (stmt);
 292
 293   /* We want to verify that each virtual definition in STMT has
 294      precisely one use and that all the virtual definitions are
 295      used by the same single statement.  When complete, we
 296      want USE_STMT to refer to the one statement which uses
 297      all of the virtual definitions from STMT.  */
 298   *use_stmt = NULL;
 299   FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 300     {
 301       defvar = DEF_FROM_PTR (var1);
 302
 303       /* If this virtual def does not have precisely one use, then
 304          we will not be able to eliminate STMT.  */
 305       if (!has_single_use (defvar))
 306         {
 307           fail = true;
 308           break;
 309         }
 310
 311       /* Get the one and only immediate use of DEFVAR.  */
 312       single_imm_use (defvar, use_p, &temp);
 313       gcc_assert (*use_p != NULL_USE_OPERAND_P);
 314       *first_use_p = *use_p;
 315
 316       /* In the case of memory partitions, we may get:
 317
 318            # MPT.764_162 = VDEF <MPT.764_161(D)>
 319            x = {};
 320            # MPT.764_167 = VDEF <MPT.764_162>
 321            y = {};
 322
 323            So we must make sure we're talking about the same LHS.
 324       */
 325       if (TREE_CODE (temp) == GIMPLE_MODIFY_STMT)
 326         {
 327           tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 328           tree base2 =  get_base_address (GIMPLE_STMT_OPERAND (temp, 0));
 329
 330           while (base1 && INDIRECT_REF_P (base1))
 331             base1 = TREE_OPERAND (base1, 0);
 332           while (base2 && INDIRECT_REF_P (base2))
 333             base2 = TREE_OPERAND (base2, 0);
 334
 335           if (base1 != base2)
 336             {
 337               fail = true;
 338               break;
 339             }
 340         }
 341
 342       /* If the immediate use of DEF_VAR is not the same as the
 343          previously find immediate uses, then we will not be able
 344          to eliminate STMT.  */
 345       if (*use_stmt == NULL)
 346         {
 347           *use_stmt = temp;
 348           prev_defvar = defvar;
 349         }
 350       else if (temp != *use_stmt)
 351         {
 352           fail = true;
 353           break;
 354         }
 355     }
 356
 357   if (fail)
 358     {
 359       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 360       return false;
 361     }
 362
 363   /* Skip through any PHI nodes we have already seen if the PHI
 364      represents the only use of this store.
 365
 366      Note this does not handle the case where the store has
 367      multiple VDEFs which all reach a set of PHI nodes in the same block.  */
 368   while (*use_p != NULL_USE_OPERAND_P
 369          && TREE_CODE (*use_stmt) == PHI_NODE
 370          && bitmap_bit_p (dse_gd->stores, get_stmt_uid (*use_stmt)))
 371     {
 372       /* A PHI node can both define and use the same SSA_NAME if
 373          the PHI is at the top of a loop and the PHI_RESULT is
 374          a loop invariant and copies have not been fully propagated.
 375
 376          The safe thing to do is exit assuming no optimization is
 377          possible.  */
 378       if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt)) == *use_stmt)
 379         return false;
 380
 381       /* Skip past this PHI and loop again in case we had a PHI
 382          chain.  */
 383       single_imm_use (PHI_RESULT (*use_stmt), use_p, use_stmt);
 384     }
 385
 386   return true;
 387 }
 388
 389
 390 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 391
 392    A dead store is a store into a memory location which will later be
 393    overwritten by another store without any intervening loads.  In this
 394    case the earlier store can be deleted.
 395
 396    In our SSA + virtual operand world we use immediate uses of virtual
 397    operands to detect dead stores.  If a store's virtual definition
 398    is used precisely once by a later store to the same location which
 399    post dominates the first store, then the first store is dead.  */
 400
 401 static void
 402 dse_optimize_stmt (struct dom_walk_data *walk_data,
 403                    basic_block bb ATTRIBUTE_UNUSED,
 404                    block_stmt_iterator bsi)
 405 {
 406   struct dse_block_local_data *bd
 407     = (struct dse_block_local_data *)
 408         VEC_last (void_p, walk_data->block_data_stack);
 409   struct dse_global_data *dse_gd
 410     = (struct dse_global_data *) walk_data->global_data;
 411   tree stmt = bsi_stmt (bsi);
 412   stmt_ann_t ann = stmt_ann (stmt);
 413
 414   /* If this statement has no virtual defs, then there is nothing
 415      to do.  */
 416   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 417     return;
 418
 419   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
 420      that's not also a function call, then record it into our table.  */
 421   if (get_call_expr_in (stmt))
 422     return;
 423
 424   if (ann->has_volatile_ops)
 425     return;
 426
 427   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 428     {
 429       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 430       use_operand_p use_p = NULL;
 431       tree use_stmt;
 432
 433       if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
 434                                       dse_gd, bd))
 435         return;
 436
 437       /* If we have precisely one immediate use at this point, then we may
 438          have found redundant store.  Make sure that the stores are to
 439          the same memory location.  This includes checking that any
 440          SSA-form variables in the address will have the same values.  */
 441       if (use_p != NULL_USE_OPERAND_P
 442           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 443           && !operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 444                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 445           && memory_address_same (stmt, use_stmt))
 446         {
 447           /* If we have precisely one immediate use at this point, but
 448              the stores are not to the same memory location then walk the
 449              virtual def-use chain to get the stmt which stores to that same
 450              memory location.  */
 451           if (!get_kill_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt))
 452             {
 453               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 454               return;
 455             }
 456         }
 457
 458       /* If we have precisely one immediate use at this point and the
 459          stores are to the same memory location or there is a chain of
 460          virtual uses from stmt and the stmt which stores to that same
 461          memory location, then we may have found redundant store.  */
 462       if (use_p != NULL_USE_OPERAND_P
 463           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 464           && operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 465                               GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 466           && memory_address_same (stmt, use_stmt))
 467         {
 468           ssa_op_iter op_iter;
 469           def_operand_p var1;
 470           vuse_vec_p vv;
 471           tree stmt_lhs;
 472
 473           /* If use_stmt is or might be a nop assignment, e.g. for
 474              struct { ... } S a, b, *p; ...
 475              b = a; b = b;
 476              or
 477              b = a; b = *p; where p might be &b,
 478              or
 479              *p = a; *p = b; where p might be &b,
 480              or
 481              *p = *u; *p = *v; where p might be v, then USE_STMT
 482              acts as a use as well as definition, so store in STMT
 483              is not dead.  */
 484           if (LOADED_SYMS (use_stmt)
 485               && bitmap_intersect_p (LOADED_SYMS (use_stmt),
 486                                      STORED_SYMS (use_stmt)))
 487             {
 488               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 489               return;
 490             }
 491
 492           if (dump_file && (dump_flags & TDF_DETAILS))
 493             {
 494               fprintf (dump_file, "  Deleted dead store '");
 495               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 496               fprintf (dump_file, "'\n");
 497             }
 498
 499           /* Then we need to fix the operand of the consuming stmt.  */
 500           stmt_lhs = USE_FROM_PTR (first_use_p);
 501           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 502             {
 503               tree usevar, temp;
 504
 505               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 506               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 507               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 508               SET_USE (use_p, usevar);
 509
 510               /* Make sure we propagate the ABNORMAL bit setting.  */
 511               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 512                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 513             }
 514
 515           /* Remove the dead store.  */
 516           bsi_remove (&bsi, true);
 517
 518           /* And release any SSA_NAMEs set in this statement back to the
 519              SSA_NAME manager.  */
 520           release_defs (stmt);
 521         }
 522
 523       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 524     }
 525 }
 526
 527 /* Record that we have seen the PHIs at the start of BB which correspond
 528    to virtual operands.  */
 529 static void
 530 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 531 {
 532   struct dse_block_local_data *bd
 533     = (struct dse_block_local_data *)
 534         VEC_last (void_p, walk_data->block_data_stack);
 535   struct dse_global_data *dse_gd
 536     = (struct dse_global_data *) walk_data->global_data;
 537   tree phi;
 538
 539   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 540     if (!is_gimple_reg (PHI_RESULT (phi)))
 541       record_voperand_set (dse_gd->stores,
 542                            &bd->stores,
 543                            get_stmt_uid (phi));
 544 }
 545
 546 static void
 547 dse_finalize_block (struct dom_walk_data *walk_data,
 548                     basic_block bb ATTRIBUTE_UNUSED)
 549 {
 550   struct dse_block_local_data *bd
 551     = (struct dse_block_local_data *)
 552         VEC_last (void_p, walk_data->block_data_stack);
 553   struct dse_global_data *dse_gd
 554     = (struct dse_global_data *) walk_data->global_data;
 555   bitmap stores = dse_gd->stores;
 556   unsigned int i;
 557   bitmap_iterator bi;
 558
 559   /* Unwind the stores noted in this basic block.  */
 560   if (bd->stores)
 561     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 562       {
 563         bitmap_clear_bit (stores, i);
 564       }
 565 }
 566
 567 /* Main entry point.  */
 568
 569 static unsigned int
 570 tree_ssa_dse (void)
 571 {
 572   struct dom_walk_data walk_data;
 573   struct dse_global_data dse_gd;
 574   basic_block bb;
 575
 576   /* Create a UID for each statement in the function.  Ordering of the
 577      UIDs is not important for this pass.  */
 578   max_stmt_uid = 0;
 579   FOR_EACH_BB (bb)
 580     {
 581       block_stmt_iterator bsi;
 582
 583       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 584         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 585     }
 586
 587   /* We might consider making this a property of each pass so that it
 588      can be [re]computed on an as-needed basis.  Particularly since
 589      this pass could be seen as an extension of DCE which needs post
 590      dominators.  */
 591   calculate_dominance_info (CDI_POST_DOMINATORS);
 592
 593   /* Dead store elimination is fundamentally a walk of the post-dominator
 594      tree and a backwards walk of statements within each block.  */
 595   walk_data.walk_stmts_backward = true;
 596   walk_data.dom_direction = CDI_POST_DOMINATORS;
 597   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 598   walk_data.before_dom_children_before_stmts = NULL;
 599   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 600   walk_data.before_dom_children_after_stmts = dse_record_phis;
 601   walk_data.after_dom_children_before_stmts = NULL;
 602   walk_data.after_dom_children_walk_stmts = NULL;
 603   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 604   walk_data.interesting_blocks = NULL;
 605
 606   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 607
 608   /* This is the main hash table for the dead store elimination pass.  */
 609   dse_gd.stores = BITMAP_ALLOC (NULL);
 610   walk_data.global_data = &dse_gd;
 611
 612   /* Initialize the dominator walker.  */
 613   init_walk_dominator_tree (&walk_data);
 614
 615   /* Recursively walk the dominator tree.  */
 616   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 617
 618   /* Finalize the dominator walker.  */
 619   fini_walk_dominator_tree (&walk_data);
 620
 621   /* Release the main bitmap.  */
 622   BITMAP_FREE (dse_gd.stores);
 623
 624   /* For now, just wipe the post-dominator information.  */
 625   free_dominance_info (CDI_POST_DOMINATORS);
 626   return 0;
 627 }
 628
 629 static bool
 630 gate_dse (void)
 631 {
 632   return flag_tree_dse != 0;
 633 }
 634
 635 struct gimple_opt_pass pass_dse =
 636 {
 637  {
 638   GIMPLE_PASS,
 639   "dse",                        /* name */
 640   gate_dse,                     /* gate */
 641   tree_ssa_dse,                 /* execute */
 642   NULL,                         /* sub */
 643   NULL,                         /* next */
 644   0,                            /* static_pass_number */
 645   TV_TREE_DSE,                  /* tv_id */
 646   PROP_cfg
 647     | PROP_ssa
 648     | PROP_alias,               /* properties_required */
 649   0,                            /* properties_provided */
 650   0,                            /* properties_destroyed */
 651   0,                            /* todo_flags_start */
 652   TODO_dump_func
 653     | TODO_ggc_collect
 654     | TODO_verify_ssa           /* todo_flags_finish */
 655  }
 656 };
 657
 658 /* A very simple dead store pass eliminating write only local variables.
 659    The pass does not require alias information and thus can be run before
 660    inlining to quickly eliminate artifacts of some common C++ constructs.  */
 661
 662 static unsigned int
 663 execute_simple_dse (void)
 664 {
 665   block_stmt_iterator bsi;
 666   basic_block bb;
 667   bitmap variables_loaded = BITMAP_ALLOC (NULL);
 668   unsigned int todo = 0;
 669
 670   /* Collect into VARIABLES LOADED all variables that are read in function
 671      body.  */
 672   FOR_EACH_BB (bb)
 673     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 674       if (LOADED_SYMS (bsi_stmt (bsi)))
 675         bitmap_ior_into (variables_loaded,
 676                          LOADED_SYMS (bsi_stmt (bsi)));
 677
 678   /* Look for statements writing into the write only variables.
 679      And try to remove them.  */
 680
 681   FOR_EACH_BB (bb)
 682     for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
 683       {
 684         tree stmt = bsi_stmt (bsi), op;
 685         bool removed = false;
 686         ssa_op_iter iter;
 687
 688         if (STORED_SYMS (stmt) && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 689             && TREE_CODE (stmt) != RETURN_EXPR
 690             && !bitmap_intersect_p (STORED_SYMS (stmt), variables_loaded))
 691           {
 692             unsigned int i;
 693             bitmap_iterator bi;
 694             bool dead = true;
 695
 696
 697
 698             /* See if STMT only stores to write-only variables and
 699                verify that there are no volatile operands.  tree-ssa-operands
 700                sets has_volatile_ops flag for all statements involving
 701                reads and writes when aliases are not built to prevent passes
 702                from removing them as dead.  The flag thus has no use for us
 703                and we need to look into all operands.  */
 704
 705             EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
 706               {
 707                 tree var = referenced_var_lookup (i);
 708                 if (TREE_ADDRESSABLE (var)
 709                     || is_global_var (var)
 710                     || TREE_THIS_VOLATILE (var))
 711                   dead = false;
 712               }
 713
 714             if (dead && LOADED_SYMS (stmt))
 715               EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
 716                 if (TREE_THIS_VOLATILE (referenced_var_lookup (i)))
 717                   dead = false;
 718
 719             if (dead)
 720               FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 721                 if (TREE_THIS_VOLATILE (op))
 722                   dead = false;
 723
 724             /* Look for possible occurence var = indirect_ref (...) where
 725                indirect_ref itself is volatile.  */
 726
 727             if (dead && TREE_THIS_VOLATILE (GIMPLE_STMT_OPERAND (stmt, 1)))
 728               dead = false;
 729
 730             if (dead)
 731               {
 732                 tree call = get_call_expr_in (stmt);
 733
 734                 /* When LHS of var = call (); is dead, simplify it into
 735                    call (); saving one operand.  */
 736                 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 737                     && call
 738                     && TREE_SIDE_EFFECTS (call))
 739                   {
 740                     if (dump_file && (dump_flags & TDF_DETAILS))
 741                       {
 742                         fprintf (dump_file, "Deleted LHS of call: ");
 743                         print_generic_stmt (dump_file, stmt, TDF_SLIM);
 744                         fprintf (dump_file, "\n");
 745                       }
 746                     push_stmt_changes (bsi_stmt_ptr (bsi));
 747                     TREE_BLOCK (call) = TREE_BLOCK (stmt);
 748                     bsi_replace (&bsi, call, false);
 749                     maybe_clean_or_replace_eh_stmt (stmt, call);
 750                     mark_symbols_for_renaming (call);
 751                     pop_stmt_changes (bsi_stmt_ptr (bsi));
 752                   }
 753                 else
 754                   {
 755                     if (dump_file && (dump_flags & TDF_DETAILS))
 756                       {
 757                         fprintf (dump_file, "  Deleted dead store '");
 758                         print_generic_expr (dump_file, stmt, dump_flags);
 759                         fprintf (dump_file, "'\n");
 760                       }
 761                     removed = true;
 762                     bsi_remove (&bsi, true);
 763                     todo |= TODO_cleanup_cfg;
 764                   }
 765                 todo |= TODO_remove_unused_locals | TODO_ggc_collect;
 766               }
 767           }
 768         if (!removed)
 769           bsi_next (&bsi);
 770       }
 771   BITMAP_FREE (variables_loaded);
 772   return todo;
 773 }
 774
 775 struct gimple_opt_pass pass_simple_dse =
 776 {
 777  {
 778   GIMPLE_PASS,
 779   "sdse",                               /* name */
 780   NULL,                                 /* gate */
 781   execute_simple_dse,                   /* execute */
 782   NULL,                                 /* sub */
 783   NULL,                                 /* next */
 784   0,                                    /* static_pass_number */
 785   0,                                    /* tv_id */
 786   PROP_ssa,                             /* properties_required */
 787   0,                                    /* properties_provided */
 788   0,                                    /* properties_destroyed */
 789   0,                                    /* todo_flags_start */
 790   TODO_dump_func                        /* todo_flags_finish */
 791  }
 792 };