gcc/tree-ssa-dse.c

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