gcc/tree-ssa-dse.c

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