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