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       /* ???  If we hit a PHI_NODE we could skip to the PHI_RESULT uses.
 317          Don't bother to do that for now.  */
 318       if (TREE_CODE (temp) == PHI_NODE)
 319         {
 320           fail = true;
 321           break;
 322         }
 323
 324       /* In the case of memory partitions, we may get:
 325
 326            # MPT.764_162 = VDEF <MPT.764_161(D)>
 327            x = {};
 328            # MPT.764_167 = VDEF <MPT.764_162>
 329            y = {};
 330
 331            So we must make sure we're talking about the same LHS.
 332       */
 333       if (TREE_CODE (temp) == GIMPLE_MODIFY_STMT)
 334         {
 335           tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 336           tree base2 =  get_base_address (GIMPLE_STMT_OPERAND (temp, 0));
 337
 338           while (base1 && INDIRECT_REF_P (base1))
 339             base1 = TREE_OPERAND (base1, 0);
 340           while (base2 && INDIRECT_REF_P (base2))
 341             base2 = TREE_OPERAND (base2, 0);
 342
 343           if (base1 != base2)
 344             {
 345               fail = true;
 346               break;
 347             }
 348         }
 349
 350       /* If the immediate use of DEF_VAR is not the same as the
 351          previously find immediate uses, then we will not be able
 352          to eliminate STMT.  */
 353       if (*use_stmt == NULL)
 354         {
 355           *use_stmt = temp;
 356           prev_defvar = defvar;
 357         }
 358       else if (temp != *use_stmt)
 359         {
 360           fail = true;
 361           break;
 362         }
 363     }
 364
 365   if (fail)
 366     {
 367       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 368       return false;
 369     }
 370
 371   return true;
 372 }
 373
 374
 375 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 376
 377    A dead store is a store into a memory location which will later be
 378    overwritten by another store without any intervening loads.  In this
 379    case the earlier store can be deleted.
 380
 381    In our SSA + virtual operand world we use immediate uses of virtual
 382    operands to detect dead stores.  If a store's virtual definition
 383    is used precisely once by a later store to the same location which
 384    post dominates the first store, then the first store is dead.  */
 385
 386 static void
 387 dse_optimize_stmt (struct dom_walk_data *walk_data,
 388                    basic_block bb ATTRIBUTE_UNUSED,
 389                    block_stmt_iterator bsi)
 390 {
 391   struct dse_block_local_data *bd
 392     = (struct dse_block_local_data *)
 393         VEC_last (void_p, walk_data->block_data_stack);
 394   struct dse_global_data *dse_gd
 395     = (struct dse_global_data *) walk_data->global_data;
 396   tree stmt = bsi_stmt (bsi);
 397   stmt_ann_t ann = stmt_ann (stmt);
 398
 399   /* If this statement has no virtual defs, then there is nothing
 400      to do.  */
 401   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 402     return;
 403
 404   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
 405      that's not also a function call, then record it into our table.  */
 406   if (get_call_expr_in (stmt))
 407     return;
 408
 409   if (ann->has_volatile_ops)
 410     return;
 411
 412   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 413     {
 414       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 415       use_operand_p use_p = NULL;
 416       tree use_stmt;
 417
 418       if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
 419                                       dse_gd, bd))
 420         return;
 421
 422       /* If we have precisely one immediate use at this point, then we may
 423          have found redundant store.  Make sure that the stores are to
 424          the same memory location.  This includes checking that any
 425          SSA-form variables in the address will have the same values.  */
 426       if (use_p != NULL_USE_OPERAND_P
 427           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 428           && !operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 429                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 430           && memory_address_same (stmt, use_stmt))
 431         {
 432           /* If we have precisely one immediate use at this point, but
 433              the stores are not to the same memory location then walk the
 434              virtual def-use chain to get the stmt which stores to that same
 435              memory location.  */
 436           if (!get_kill_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt))
 437             {
 438               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 439               return;
 440             }
 441         }
 442
 443       /* If we have precisely one immediate use at this point and the
 444          stores are to the same memory location or there is a chain of
 445          virtual uses from stmt and the stmt which stores to that same
 446          memory location, then we may have found redundant store.  */
 447       if (use_p != NULL_USE_OPERAND_P
 448           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 449           && operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 450                               GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 451           && memory_address_same (stmt, use_stmt))
 452         {
 453           ssa_op_iter op_iter;
 454           def_operand_p var1;
 455           vuse_vec_p vv;
 456           tree stmt_lhs;
 457
 458           /* If use_stmt is or might be a nop assignment, e.g. for
 459              struct { ... } S a, b, *p; ...
 460              b = a; b = b;
 461              or
 462              b = a; b = *p; where p might be &b,
 463              or
 464              *p = a; *p = b; where p might be &b,
 465              or
 466              *p = *u; *p = *v; where p might be v, then USE_STMT
 467              acts as a use as well as definition, so store in STMT
 468              is not dead.  */
 469           if (LOADED_SYMS (use_stmt)
 470               && bitmap_intersect_p (LOADED_SYMS (use_stmt),
 471                                      STORED_SYMS (use_stmt)))
 472             {
 473               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 474               return;
 475             }
 476
 477           if (dump_file && (dump_flags & TDF_DETAILS))
 478             {
 479               fprintf (dump_file, "  Deleted dead store '");
 480               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 481               fprintf (dump_file, "'\n");
 482             }
 483
 484           /* Then we need to fix the operand of the consuming stmt.  */
 485           stmt_lhs = USE_FROM_PTR (first_use_p);
 486           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 487             {
 488               tree usevar, temp;
 489
 490               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 491               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 492               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 493               SET_USE (use_p, usevar);
 494
 495               /* Make sure we propagate the ABNORMAL bit setting.  */
 496               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 497                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 498             }
 499
 500           /* Remove the dead store.  */
 501           bsi_remove (&bsi, true);
 502
 503           /* And release any SSA_NAMEs set in this statement back to the
 504              SSA_NAME manager.  */
 505           release_defs (stmt);
 506         }
 507
 508       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 509     }
 510 }
 511
 512 /* Record that we have seen the PHIs at the start of BB which correspond
 513    to virtual operands.  */
 514 static void
 515 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 516 {
 517   struct dse_block_local_data *bd
 518     = (struct dse_block_local_data *)
 519         VEC_last (void_p, walk_data->block_data_stack);
 520   struct dse_global_data *dse_gd
 521     = (struct dse_global_data *) walk_data->global_data;
 522   tree phi;
 523
 524   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 525     if (!is_gimple_reg (PHI_RESULT (phi)))
 526       record_voperand_set (dse_gd->stores,
 527                            &bd->stores,
 528                            get_stmt_uid (phi));
 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   basic_block bb;
 560
 561   /* Create a UID for each statement in the function.  Ordering of the
 562      UIDs is not important for this pass.  */
 563   max_stmt_uid = 0;
 564   FOR_EACH_BB (bb)
 565     {
 566       block_stmt_iterator bsi;
 567
 568       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 569         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 570     }
 571
 572   /* We might consider making this a property of each pass so that it
 573      can be [re]computed on an as-needed basis.  Particularly since
 574      this pass could be seen as an extension of DCE which needs post
 575      dominators.  */
 576   calculate_dominance_info (CDI_POST_DOMINATORS);
 577
 578   /* Dead store elimination is fundamentally a walk of the post-dominator
 579      tree and a backwards walk of statements within each block.  */
 580   walk_data.walk_stmts_backward = true;
 581   walk_data.dom_direction = CDI_POST_DOMINATORS;
 582   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 583   walk_data.before_dom_children_before_stmts = NULL;
 584   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 585   walk_data.before_dom_children_after_stmts = dse_record_phis;
 586   walk_data.after_dom_children_before_stmts = NULL;
 587   walk_data.after_dom_children_walk_stmts = NULL;
 588   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 589   walk_data.interesting_blocks = NULL;
 590
 591   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 592
 593   /* This is the main hash table for the dead store elimination pass.  */
 594   dse_gd.stores = BITMAP_ALLOC (NULL);
 595   walk_data.global_data = &dse_gd;
 596
 597   /* Initialize the dominator walker.  */
 598   init_walk_dominator_tree (&walk_data);
 599
 600   /* Recursively walk the dominator tree.  */
 601   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 602
 603   /* Finalize the dominator walker.  */
 604   fini_walk_dominator_tree (&walk_data);
 605
 606   /* Release the main bitmap.  */
 607   BITMAP_FREE (dse_gd.stores);
 608
 609   /* For now, just wipe the post-dominator information.  */
 610   free_dominance_info (CDI_POST_DOMINATORS);
 611   return 0;
 612 }
 613
 614 static bool
 615 gate_dse (void)
 616 {
 617   return flag_tree_dse != 0;
 618 }
 619
 620 struct gimple_opt_pass pass_dse =
 621 {
 622  {
 623   GIMPLE_PASS,
 624   "dse",                        /* name */
 625   gate_dse,                     /* gate */
 626   tree_ssa_dse,                 /* execute */
 627   NULL,                         /* sub */
 628   NULL,                         /* next */
 629   0,                            /* static_pass_number */
 630   TV_TREE_DSE,                  /* tv_id */
 631   PROP_cfg
 632     | PROP_ssa
 633     | PROP_alias,               /* properties_required */
 634   0,                            /* properties_provided */
 635   0,                            /* properties_destroyed */
 636   0,                            /* todo_flags_start */
 637   TODO_dump_func
 638     | TODO_ggc_collect
 639     | TODO_verify_ssa           /* todo_flags_finish */
 640  }
 641 };
 642
 643 /* A very simple dead store pass eliminating write only local variables.
 644    The pass does not require alias information and thus can be run before
 645    inlining to quickly eliminate artifacts of some common C++ constructs.  */
 646
 647 static unsigned int
 648 execute_simple_dse (void)
 649 {
 650   block_stmt_iterator bsi;
 651   basic_block bb;
 652   bitmap variables_loaded = BITMAP_ALLOC (NULL);
 653   unsigned int todo = 0;
 654
 655   /* Collect into VARIABLES LOADED all variables that are read in function
 656      body.  */
 657   FOR_EACH_BB (bb)
 658     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 659       if (LOADED_SYMS (bsi_stmt (bsi)))
 660         bitmap_ior_into (variables_loaded,
 661                          LOADED_SYMS (bsi_stmt (bsi)));
 662
 663   /* Look for statements writing into the write only variables.
 664      And try to remove them.  */
 665
 666   FOR_EACH_BB (bb)
 667     for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
 668       {
 669         tree stmt = bsi_stmt (bsi), op;
 670         bool removed = false;
 671         ssa_op_iter iter;
 672
 673         if (STORED_SYMS (stmt) && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 674             && TREE_CODE (stmt) != RETURN_EXPR
 675             && !bitmap_intersect_p (STORED_SYMS (stmt), variables_loaded))
 676           {
 677             unsigned int i;
 678             bitmap_iterator bi;
 679             bool dead = true;
 680
 681
 682
 683             /* See if STMT only stores to write-only variables and
 684                verify that there are no volatile operands.  tree-ssa-operands
 685                sets has_volatile_ops flag for all statements involving
 686                reads and writes when aliases are not built to prevent passes
 687                from removing them as dead.  The flag thus has no use for us
 688                and we need to look into all operands.  */
 689
 690             EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
 691               {
 692                 tree var = referenced_var_lookup (i);
 693                 if (TREE_ADDRESSABLE (var)
 694                     || is_global_var (var)
 695                     || TREE_THIS_VOLATILE (var))
 696                   dead = false;
 697               }
 698
 699             if (dead && LOADED_SYMS (stmt))
 700               EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
 701                 if (TREE_THIS_VOLATILE (referenced_var_lookup (i)))
 702                   dead = false;
 703
 704             if (dead)
 705               FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 706                 if (TREE_THIS_VOLATILE (op))
 707                   dead = false;
 708
 709             /* Look for possible occurence var = indirect_ref (...) where
 710                indirect_ref itself is volatile.  */
 711
 712             if (dead && TREE_THIS_VOLATILE (GIMPLE_STMT_OPERAND (stmt, 1)))
 713               dead = false;
 714
 715             if (dead)
 716               {
 717                 tree call = get_call_expr_in (stmt);
 718
 719                 /* When LHS of var = call (); is dead, simplify it into
 720                    call (); saving one operand.  */
 721                 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 722                     && call
 723                     && TREE_SIDE_EFFECTS (call))
 724                   {
 725                     if (dump_file && (dump_flags & TDF_DETAILS))
 726                       {
 727                         fprintf (dump_file, "Deleted LHS of call: ");
 728                         print_generic_stmt (dump_file, stmt, TDF_SLIM);
 729                         fprintf (dump_file, "\n");
 730                       }
 731                     push_stmt_changes (bsi_stmt_ptr (bsi));
 732                     TREE_BLOCK (call) = TREE_BLOCK (stmt);
 733                     bsi_replace (&bsi, call, false);
 734                     maybe_clean_or_replace_eh_stmt (stmt, call);
 735                     mark_symbols_for_renaming (call);
 736                     pop_stmt_changes (bsi_stmt_ptr (bsi));
 737                   }
 738                 else
 739                   {
 740                     if (dump_file && (dump_flags & TDF_DETAILS))
 741                       {
 742                         fprintf (dump_file, "  Deleted dead store '");
 743                         print_generic_expr (dump_file, stmt, dump_flags);
 744                         fprintf (dump_file, "'\n");
 745                       }
 746                     removed = true;
 747                     bsi_remove (&bsi, true);
 748                     todo |= TODO_cleanup_cfg;
 749                   }
 750                 todo |= TODO_remove_unused_locals | TODO_ggc_collect;
 751               }
 752           }
 753         if (!removed)
 754           bsi_next (&bsi);
 755       }
 756   BITMAP_FREE (variables_loaded);
 757   return todo;
 758 }
 759
 760 struct gimple_opt_pass pass_simple_dse =
 761 {
 762  {
 763   GIMPLE_PASS,
 764   "sdse",                               /* name */
 765   NULL,                                 /* gate */
 766   execute_simple_dse,                   /* execute */
 767   NULL,                                 /* sub */
 768   NULL,                                 /* next */
 769   0,                                    /* static_pass_number */
 770   0,                                    /* tv_id */
 771   PROP_ssa,                             /* properties_required */
 772   0,                                    /* properties_provided */
 773   0,                                    /* properties_destroyed */
 774   0,                                    /* todo_flags_start */
 775   TODO_dump_func                        /* todo_flags_finish */
 776  }
 777 };