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 (dump_file && (dump_flags & TDF_DETAILS))
 474             {
 475               fprintf (dump_file, "  Deleted dead store '");
 476               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 477               fprintf (dump_file, "'\n");
 478             }
 479
 480           /* Then we need to fix the operand of the consuming stmt.  */
 481           stmt_lhs = USE_FROM_PTR (first_use_p);
 482           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 483             {
 484               tree usevar, temp;
 485
 486               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 487               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 488               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 489               SET_USE (use_p, usevar);
 490
 491               /* Make sure we propagate the ABNORMAL bit setting.  */
 492               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 493                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 494             }
 495
 496           /* Remove the dead store.  */
 497           bsi_remove (&bsi, true);
 498
 499           /* And release any SSA_NAMEs set in this statement back to the
 500              SSA_NAME manager.  */
 501           release_defs (stmt);
 502         }
 503
 504       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 505     }
 506 }
 507
 508 /* Record that we have seen the PHIs at the start of BB which correspond
 509    to virtual operands.  */
 510 static void
 511 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 512 {
 513   struct dse_block_local_data *bd
 514     = (struct dse_block_local_data *)
 515         VEC_last (void_p, walk_data->block_data_stack);
 516   struct dse_global_data *dse_gd
 517     = (struct dse_global_data *) walk_data->global_data;
 518   tree phi;
 519
 520   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 521     if (!is_gimple_reg (PHI_RESULT (phi)))
 522       record_voperand_set (dse_gd->stores,
 523                            &bd->stores,
 524                            get_stmt_uid (phi));
 525 }
 526
 527 static void
 528 dse_finalize_block (struct dom_walk_data *walk_data,
 529                     basic_block bb ATTRIBUTE_UNUSED)
 530 {
 531   struct dse_block_local_data *bd
 532     = (struct dse_block_local_data *)
 533         VEC_last (void_p, walk_data->block_data_stack);
 534   struct dse_global_data *dse_gd
 535     = (struct dse_global_data *) walk_data->global_data;
 536   bitmap stores = dse_gd->stores;
 537   unsigned int i;
 538   bitmap_iterator bi;
 539
 540   /* Unwind the stores noted in this basic block.  */
 541   if (bd->stores)
 542     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 543       {
 544         bitmap_clear_bit (stores, i);
 545       }
 546 }
 547
 548 /* Main entry point.  */
 549
 550 static unsigned int
 551 tree_ssa_dse (void)
 552 {
 553   struct dom_walk_data walk_data;
 554   struct dse_global_data dse_gd;
 555   basic_block bb;
 556
 557   /* Create a UID for each statement in the function.  Ordering of the
 558      UIDs is not important for this pass.  */
 559   max_stmt_uid = 0;
 560   FOR_EACH_BB (bb)
 561     {
 562       block_stmt_iterator bsi;
 563
 564       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 565         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 566     }
 567
 568   /* We might consider making this a property of each pass so that it
 569      can be [re]computed on an as-needed basis.  Particularly since
 570      this pass could be seen as an extension of DCE which needs post
 571      dominators.  */
 572   calculate_dominance_info (CDI_POST_DOMINATORS);
 573
 574   /* Dead store elimination is fundamentally a walk of the post-dominator
 575      tree and a backwards walk of statements within each block.  */
 576   walk_data.walk_stmts_backward = true;
 577   walk_data.dom_direction = CDI_POST_DOMINATORS;
 578   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 579   walk_data.before_dom_children_before_stmts = NULL;
 580   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 581   walk_data.before_dom_children_after_stmts = dse_record_phis;
 582   walk_data.after_dom_children_before_stmts = NULL;
 583   walk_data.after_dom_children_walk_stmts = NULL;
 584   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 585   walk_data.interesting_blocks = NULL;
 586
 587   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 588
 589   /* This is the main hash table for the dead store elimination pass.  */
 590   dse_gd.stores = BITMAP_ALLOC (NULL);
 591   walk_data.global_data = &dse_gd;
 592
 593   /* Initialize the dominator walker.  */
 594   init_walk_dominator_tree (&walk_data);
 595
 596   /* Recursively walk the dominator tree.  */
 597   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 598
 599   /* Finalize the dominator walker.  */
 600   fini_walk_dominator_tree (&walk_data);
 601
 602   /* Release the main bitmap.  */
 603   BITMAP_FREE (dse_gd.stores);
 604
 605   /* For now, just wipe the post-dominator information.  */
 606   free_dominance_info (CDI_POST_DOMINATORS);
 607   return 0;
 608 }
 609
 610 static bool
 611 gate_dse (void)
 612 {
 613   return flag_tree_dse != 0;
 614 }
 615
 616 struct tree_opt_pass pass_dse = {
 617   "dse",                        /* name */
 618   gate_dse,                     /* gate */
 619   tree_ssa_dse,                 /* execute */
 620   NULL,                         /* sub */
 621   NULL,                         /* next */
 622   0,                            /* static_pass_number */
 623   TV_TREE_DSE,                  /* tv_id */
 624   PROP_cfg
 625     | PROP_ssa
 626     | PROP_alias,               /* properties_required */
 627   0,                            /* properties_provided */
 628   0,                            /* properties_destroyed */
 629   0,                            /* todo_flags_start */
 630   TODO_dump_func
 631     | TODO_ggc_collect
 632     | TODO_verify_ssa,          /* todo_flags_finish */
 633   0                             /* letter */
 634 };
 635
 636 /* A very simple dead store pass eliminating write only local variables.
 637    The pass does not require alias information and thus can be run before
 638    inlining to quickly eliminate artifacts of some common C++ constructs.  */
 639
 640 static unsigned int
 641 execute_simple_dse (void)
 642 {
 643   block_stmt_iterator bsi;
 644   basic_block bb;
 645   bitmap variables_loaded = BITMAP_ALLOC (NULL);
 646   unsigned int todo = 0;
 647
 648   /* Collect into VARIABLES LOADED all variables that are read in function
 649      body.  */
 650   FOR_EACH_BB (bb)
 651     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 652       if (LOADED_SYMS (bsi_stmt (bsi)))
 653         bitmap_ior_into (variables_loaded,
 654                          LOADED_SYMS (bsi_stmt (bsi)));
 655
 656   /* Look for statements writing into the write only variables.
 657      And try to remove them.  */
 658
 659   FOR_EACH_BB (bb)
 660     for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
 661       {
 662         tree stmt = bsi_stmt (bsi), op;
 663         bool removed = false;
 664         ssa_op_iter iter;
 665
 666         if (STORED_SYMS (stmt) && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 667             && TREE_CODE (stmt) != RETURN_EXPR
 668             && !bitmap_intersect_p (STORED_SYMS (stmt), variables_loaded))
 669           {
 670             unsigned int i;
 671             bitmap_iterator bi;
 672             bool dead = true;
 673
 674
 675
 676             /* See if STMT only stores to write-only variables and
 677                verify that there are no volatile operands.  tree-ssa-operands
 678                sets has_volatile_ops flag for all statements involving
 679                reads and writes when aliases are not built to prevent passes
 680                from removing them as dead.  The flag thus has no use for us
 681                and we need to look into all operands.  */
 682
 683             EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
 684               {
 685                 tree var = referenced_var_lookup (i);
 686                 if (TREE_ADDRESSABLE (var)
 687                     || is_global_var (var)
 688                     || TREE_THIS_VOLATILE (var))
 689                   dead = false;
 690               }
 691
 692             if (dead && LOADED_SYMS (stmt))
 693               EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
 694                 if (TREE_THIS_VOLATILE (referenced_var_lookup (i)))
 695                   dead = false;
 696
 697             if (dead)
 698               FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 699                 if (TREE_THIS_VOLATILE (op))
 700                   dead = false;
 701
 702             /* Look for possible occurence var = indirect_ref (...) where
 703                indirect_ref itself is volatile.  */
 704
 705             if (dead && TREE_THIS_VOLATILE (GIMPLE_STMT_OPERAND (stmt, 1)))
 706               dead = false;
 707
 708             if (dead)
 709               {
 710                 tree call = get_call_expr_in (stmt);
 711
 712                 /* When LHS of var = call (); is dead, simplify it into
 713                    call (); saving one operand.  */
 714                 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 715                     && call
 716                     && TREE_SIDE_EFFECTS (call))
 717                   {
 718                     if (dump_file && (dump_flags & TDF_DETAILS))
 719                       {
 720                         fprintf (dump_file, "Deleted LHS of call: ");
 721                         print_generic_stmt (dump_file, stmt, TDF_SLIM);
 722                         fprintf (dump_file, "\n");
 723                       }
 724                     push_stmt_changes (bsi_stmt_ptr (bsi));
 725                     TREE_BLOCK (call) = TREE_BLOCK (stmt);
 726                     bsi_replace (&bsi, call, false);
 727                     maybe_clean_or_replace_eh_stmt (stmt, call);
 728                     mark_symbols_for_renaming (call);
 729                     pop_stmt_changes (bsi_stmt_ptr (bsi));
 730                   }
 731                 else
 732                   {
 733                     if (dump_file && (dump_flags & TDF_DETAILS))
 734                       {
 735                         fprintf (dump_file, "  Deleted dead store '");
 736                         print_generic_expr (dump_file, stmt, dump_flags);
 737                         fprintf (dump_file, "'\n");
 738                       }
 739                     removed = true;
 740                     bsi_remove (&bsi, true);
 741                     todo |= TODO_cleanup_cfg;
 742                   }
 743                 todo |= TODO_remove_unused_locals | TODO_ggc_collect;
 744               }
 745           }
 746         if (!removed)
 747           bsi_next (&bsi);
 748       }
 749   BITMAP_FREE (variables_loaded);
 750   return todo;
 751 }
 752
 753 struct tree_opt_pass pass_simple_dse =
 754 {
 755   "sdse",                               /* name */
 756   NULL,                                 /* gate */
 757   execute_simple_dse,                   /* execute */
 758   NULL,                                 /* sub */
 759   NULL,                                 /* next */
 760   0,                                    /* static_pass_number */
 761   0,                                    /* tv_id */
 762   PROP_ssa,                             /* properties_required */
 763   0,                                    /* properties_provided */
 764   0,                                    /* properties_destroyed */
 765   0,                                    /* todo_flags_start */
 766   TODO_dump_func,                       /* todo_flags_finish */
 767   0                                     /* letter */
 768 };