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                                block_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 (tree stmt)
 109 {
 110   if (TREE_CODE (stmt) == PHI_NODE)
 111     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + gimple_stmt_max_uid (cfun);
 112
 113   return gimple_stmt_uid (stmt);
 114 }
 115
 116 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 117
 118 static void
 119 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 120 {
 121   /* Lazily allocate the bitmap.  Note that we do not get a notification
 122      when the block local data structures die, so we allocate the local
 123      bitmap backed by the GC system.  */
 124   if (*local == NULL)
 125     *local = BITMAP_GGC_ALLOC ();
 126
 127   /* Set the bit in the local and global bitmaps.  */
 128   bitmap_set_bit (*local, uid);
 129   bitmap_set_bit (global, uid);
 130 }
 131
 132 /* Initialize block local data structures.  */
 133
 134 static void
 135 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 136                                  basic_block bb ATTRIBUTE_UNUSED,
 137                                  bool recycled)
 138 {
 139   struct dse_block_local_data *bd
 140     = (struct dse_block_local_data *)
 141         VEC_last (void_p, walk_data->block_data_stack);
 142
 143   /* If we are given a recycled block local data structure, ensure any
 144      bitmap associated with the block is cleared.  */
 145   if (recycled)
 146     {
 147       if (bd->stores)
 148         bitmap_clear (bd->stores);
 149     }
 150 }
 151
 152 /* Helper function for memory_address_same via walk_tree.  Returns
 153    non-NULL if it finds an SSA_NAME which is part of the address,
 154    such that the definition of the SSA_NAME post-dominates the store
 155    we want to delete but not the store that we believe makes it
 156    redundant.  This indicates that the address may change between
 157    the two stores.  */
 158
 159 static tree
 160 memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
 161                       void *data)
 162 {
 163   struct address_walk_data *walk_data = (struct address_walk_data *) data;
 164   tree expr = *expr_p;
 165   tree def_stmt;
 166   basic_block def_bb;
 167
 168   if (TREE_CODE (expr) != SSA_NAME)
 169     return NULL_TREE;
 170
 171   /* If we've found a default definition, then there's no problem.  Both
 172      stores will post-dominate it.  And def_bb will be NULL.  */
 173   if (SSA_NAME_IS_DEFAULT_DEF (expr))
 174     return NULL_TREE;
 175
 176   def_stmt = SSA_NAME_DEF_STMT (expr);
 177   def_bb = bb_for_stmt (def_stmt);
 178
 179   /* DEF_STMT must dominate both stores.  So if it is in the same
 180      basic block as one, it does not post-dominate that store.  */
 181   if (walk_data->store1_bb != def_bb
 182       && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
 183     {
 184       if (walk_data->store2_bb == def_bb
 185           || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
 186                               def_bb))
 187         /* Return non-NULL to stop the walk.  */
 188         return def_stmt;
 189     }
 190
 191   return NULL_TREE;
 192 }
 193
 194 /* Return TRUE if the destination memory address in STORE1 and STORE2
 195    might be modified after STORE1, before control reaches STORE2.  */
 196
 197 static bool
 198 memory_address_same (tree store1, tree store2)
 199 {
 200   struct address_walk_data walk_data;
 201
 202   walk_data.store1_bb = bb_for_stmt (store1);
 203   walk_data.store2_bb = bb_for_stmt (store2);
 204
 205   return (walk_tree (&GIMPLE_STMT_OPERAND (store1, 0), memory_ssa_name_same,
 206                      &walk_data, NULL)
 207           == NULL);
 208 }
 209
 210 /* Return true if there is a stmt that kills the lhs of STMT and is in the
 211    virtual def-use chain of STMT without a use in between the kill and STMT.
 212    Returns false if no such stmt is found.
 213    *FIRST_USE_P is set to the first use of the single virtual def of
 214    STMT.  *USE_P is set to the vop killed by *USE_STMT.  */
 215
 216 static bool
 217 get_kill_of_stmt_lhs (tree stmt,
 218                       use_operand_p * first_use_p,
 219                       use_operand_p * use_p, tree * use_stmt)
 220 {
 221   tree lhs;
 222
 223   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
 224
 225   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 226
 227   /* We now walk the chain of single uses of the single VDEFs.
 228      We succeeded finding a kill if the lhs of the use stmt is
 229      equal to the original lhs.  We can keep walking to the next
 230      use if there are no possible uses of the original lhs in
 231      the stmt.  */
 232   do
 233     {
 234       tree use_lhs, use_rhs;
 235       def_operand_p def_p;
 236
 237       /* The stmt must have a single VDEF.  */
 238       def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_VDEF);
 239       if (def_p == NULL_DEF_OPERAND_P)
 240         return false;
 241
 242       /* Get the single immediate use of the def.  */
 243       if (!single_imm_use (DEF_FROM_PTR (def_p), first_use_p, &stmt))
 244         return false;
 245       first_use_p = use_p;
 246
 247       /* If there are possible hidden uses, give up.  */
 248       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 249         return false;
 250       use_rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 251       if (TREE_CODE (use_rhs) == CALL_EXPR
 252           || (!is_gimple_min_invariant (use_rhs)
 253               && TREE_CODE (use_rhs) != SSA_NAME))
 254         return false;
 255
 256       /* If the use stmts lhs matches the original lhs we have
 257          found the kill, otherwise continue walking.  */
 258       use_lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 259       if (operand_equal_p (use_lhs, lhs, 0))
 260         {
 261           *use_stmt = stmt;
 262           return true;
 263         }
 264     }
 265   while (1);
 266 }
 267
 268 /* A helper of dse_optimize_stmt.
 269    Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
 270    use, and that one use is another VDEF clobbering the first one.
 271
 272    Return TRUE if the above conditions are met, otherwise FALSE.  */
 273
 274 static bool
 275 dse_possible_dead_store_p (tree stmt,
 276                            use_operand_p *first_use_p,
 277                            use_operand_p *use_p,
 278                            tree *use_stmt,
 279                            struct dse_global_data *dse_gd,
 280                            struct dse_block_local_data *bd)
 281 {
 282   ssa_op_iter op_iter;
 283   bool fail = false;
 284   def_operand_p var1;
 285   vuse_vec_p vv;
 286   tree defvar = NULL_TREE, temp;
 287   tree prev_defvar = NULL_TREE;
 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 PHI_NODE we could skip to the PHI_RESULT uses.
 313          Don't bother to do that for now.  */
 314       if (TREE_CODE (temp) == PHI_NODE)
 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 (TREE_CODE (temp) == GIMPLE_MODIFY_STMT)
 330         {
 331           tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 332           tree base2 =  get_base_address (GIMPLE_STMT_OPERAND (temp, 0));
 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_stmt_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                    block_stmt_iterator bsi)
 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   tree stmt = bsi_stmt (bsi);
 393   stmt_ann_t ann = stmt_ann (stmt);
 394
 395   /* If this statement has no virtual defs, then there is nothing
 396      to do.  */
 397   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 398     return;
 399
 400   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
 401      that's not also a function call, then record it into our table.  */
 402   if (get_call_expr_in (stmt))
 403     return;
 404
 405   if (ann->has_volatile_ops)
 406     return;
 407
 408   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 409     {
 410       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 411       use_operand_p use_p = NULL;
 412       tree use_stmt;
 413
 414       if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
 415                                       dse_gd, bd))
 416         return;
 417
 418       /* If we have precisely one immediate use at this point, then we may
 419          have found redundant store.  Make sure that the stores are to
 420          the same memory location.  This includes checking that any
 421          SSA-form variables in the address will have the same values.  */
 422       if (use_p != NULL_USE_OPERAND_P
 423           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 424           && !operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 425                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 426           && memory_address_same (stmt, use_stmt))
 427         {
 428           /* If we have precisely one immediate use at this point, but
 429              the stores are not to the same memory location then walk the
 430              virtual def-use chain to get the stmt which stores to that same
 431              memory location.  */
 432           if (!get_kill_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt))
 433             {
 434               record_voperand_set (dse_gd->stores, &bd->stores, gimple_stmt_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_STMT_OPERAND (stmt, 0),
 446                               GIMPLE_STMT_OPERAND (use_stmt, 0), 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 (LOADED_SYMS (use_stmt)
 466               && bitmap_intersect_p (LOADED_SYMS (use_stmt),
 467                                      STORED_SYMS (use_stmt)))
 468             {
 469               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 470               return;
 471             }
 472
 473           if (dump_file && (dump_flags & TDF_DETAILS))
 474             {
 475               fprintf (dump_file, "  Deleted dead store '");
 476               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 477               fprintf (dump_file, "'\n");
 478             }
 479
 480           /* Then we need to fix the operand of the consuming stmt.  */
 481           stmt_lhs = USE_FROM_PTR (first_use_p);
 482           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 483             {
 484               tree usevar, temp;
 485
 486               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 487               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 488               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 489               SET_USE (use_p, usevar);
 490
 491               /* Make sure we propagate the ABNORMAL bit setting.  */
 492               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 493                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 494             }
 495
 496           /* Remove the dead store.  */
 497           bsi_remove (&bsi, true);
 498
 499           /* And release any SSA_NAMEs set in this statement back to the
 500              SSA_NAME manager.  */
 501           release_defs (stmt);
 502         }
 503
 504       record_voperand_set (dse_gd->stores, &bd->stores, gimple_stmt_uid (stmt));
 505     }
 506 }
 507
 508 /* Record that we have seen the PHIs at the start of BB which correspond
 509    to virtual operands.  */
 510 static void
 511 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 512 {
 513   struct dse_block_local_data *bd
 514     = (struct dse_block_local_data *)
 515         VEC_last (void_p, walk_data->block_data_stack);
 516   struct dse_global_data *dse_gd
 517     = (struct dse_global_data *) walk_data->global_data;
 518   tree phi;
 519
 520   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 521     if (!is_gimple_reg (PHI_RESULT (phi)))
 522       record_voperand_set (dse_gd->stores,
 523                            &bd->stores,
 524                            get_stmt_uid (phi));
 525 }
 526
 527 static void
 528 dse_finalize_block (struct dom_walk_data *walk_data,
 529                     basic_block bb ATTRIBUTE_UNUSED)
 530 {
 531   struct dse_block_local_data *bd
 532     = (struct dse_block_local_data *)
 533         VEC_last (void_p, walk_data->block_data_stack);
 534   struct dse_global_data *dse_gd
 535     = (struct dse_global_data *) walk_data->global_data;
 536   bitmap stores = dse_gd->stores;
 537   unsigned int i;
 538   bitmap_iterator bi;
 539
 540   /* Unwind the stores noted in this basic block.  */
 541   if (bd->stores)
 542     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 543       {
 544         bitmap_clear_bit (stores, i);
 545       }
 546 }
 547
 548 /* Main entry point.  */
 549
 550 static unsigned int
 551 tree_ssa_dse (void)
 552 {
 553   struct dom_walk_data walk_data;
 554   struct dse_global_data dse_gd;
 555
 556   renumber_gimple_stmt_uids ();
 557
 558   /* We might consider making this a property of each pass so that it
 559      can be [re]computed on an as-needed basis.  Particularly since
 560      this pass could be seen as an extension of DCE which needs post
 561      dominators.  */
 562   calculate_dominance_info (CDI_POST_DOMINATORS);
 563
 564   /* Dead store elimination is fundamentally a walk of the post-dominator
 565      tree and a backwards walk of statements within each block.  */
 566   walk_data.walk_stmts_backward = true;
 567   walk_data.dom_direction = CDI_POST_DOMINATORS;
 568   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 569   walk_data.before_dom_children_before_stmts = NULL;
 570   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 571   walk_data.before_dom_children_after_stmts = dse_record_phis;
 572   walk_data.after_dom_children_before_stmts = NULL;
 573   walk_data.after_dom_children_walk_stmts = NULL;
 574   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 575   walk_data.interesting_blocks = NULL;
 576
 577   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 578
 579   /* This is the main hash table for the dead store elimination pass.  */
 580   dse_gd.stores = BITMAP_ALLOC (NULL);
 581   walk_data.global_data = &dse_gd;
 582
 583   /* Initialize the dominator walker.  */
 584   init_walk_dominator_tree (&walk_data);
 585
 586   /* Recursively walk the dominator tree.  */
 587   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 588
 589   /* Finalize the dominator walker.  */
 590   fini_walk_dominator_tree (&walk_data);
 591
 592   /* Release the main bitmap.  */
 593   BITMAP_FREE (dse_gd.stores);
 594
 595   /* For now, just wipe the post-dominator information.  */
 596   free_dominance_info (CDI_POST_DOMINATORS);
 597   return 0;
 598 }
 599
 600 static bool
 601 gate_dse (void)
 602 {
 603   return flag_tree_dse != 0;
 604 }
 605
 606 struct gimple_opt_pass pass_dse =
 607 {
 608  {
 609   GIMPLE_PASS,
 610   "dse",                        /* name */
 611   gate_dse,                     /* gate */
 612   tree_ssa_dse,                 /* execute */
 613   NULL,                         /* sub */
 614   NULL,                         /* next */
 615   0,                            /* static_pass_number */
 616   TV_TREE_DSE,                  /* tv_id */
 617   PROP_cfg
 618     | PROP_ssa
 619     | PROP_alias,               /* properties_required */
 620   0,                            /* properties_provided */
 621   0,                            /* properties_destroyed */
 622   0,                            /* todo_flags_start */
 623   TODO_dump_func
 624     | TODO_ggc_collect
 625     | TODO_verify_ssa           /* todo_flags_finish */
 626  }
 627 };
 628
 629 /* A very simple dead store pass eliminating write only local variables.
 630    The pass does not require alias information and thus can be run before
 631    inlining to quickly eliminate artifacts of some common C++ constructs.  */
 632
 633 static unsigned int
 634 execute_simple_dse (void)
 635 {
 636   block_stmt_iterator bsi;
 637   basic_block bb;
 638   bitmap variables_loaded = BITMAP_ALLOC (NULL);
 639   unsigned int todo = 0;
 640
 641   /* Collect into VARIABLES LOADED all variables that are read in function
 642      body.  */
 643   FOR_EACH_BB (bb)
 644     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 645       if (LOADED_SYMS (bsi_stmt (bsi)))
 646         bitmap_ior_into (variables_loaded,
 647                          LOADED_SYMS (bsi_stmt (bsi)));
 648
 649   /* Look for statements writing into the write only variables.
 650      And try to remove them.  */
 651
 652   FOR_EACH_BB (bb)
 653     for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
 654       {
 655         tree stmt = bsi_stmt (bsi), op;
 656         bool removed = false;
 657         ssa_op_iter iter;
 658
 659         if (STORED_SYMS (stmt) && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 660             && TREE_CODE (stmt) != RETURN_EXPR
 661             && !bitmap_intersect_p (STORED_SYMS (stmt), variables_loaded))
 662           {
 663             unsigned int i;
 664             bitmap_iterator bi;
 665             bool dead = true;
 666
 667
 668
 669             /* See if STMT only stores to write-only variables and
 670                verify that there are no volatile operands.  tree-ssa-operands
 671                sets has_volatile_ops flag for all statements involving
 672                reads and writes when aliases are not built to prevent passes
 673                from removing them as dead.  The flag thus has no use for us
 674                and we need to look into all operands.  */
 675
 676             EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
 677               {
 678                 tree var = referenced_var_lookup (i);
 679                 if (TREE_ADDRESSABLE (var)
 680                     || is_global_var (var)
 681                     || TREE_THIS_VOLATILE (var))
 682                   dead = false;
 683               }
 684
 685             if (dead && LOADED_SYMS (stmt))
 686               EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
 687                 if (TREE_THIS_VOLATILE (referenced_var_lookup (i)))
 688                   dead = false;
 689
 690             if (dead)
 691               FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 692                 if (TREE_THIS_VOLATILE (op))
 693                   dead = false;
 694
 695             /* Look for possible occurrence var = indirect_ref (...) where
 696                indirect_ref itself is volatile.  */
 697
 698             if (dead && TREE_THIS_VOLATILE (GIMPLE_STMT_OPERAND (stmt, 1)))
 699               dead = false;
 700
 701             if (dead)
 702               {
 703                 tree call = get_call_expr_in (stmt);
 704
 705                 /* When LHS of var = call (); is dead, simplify it into
 706                    call (); saving one operand.  */
 707                 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 708                     && call
 709                     && TREE_SIDE_EFFECTS (call))
 710                   {
 711                     if (dump_file && (dump_flags & TDF_DETAILS))
 712                       {
 713                         fprintf (dump_file, "Deleted LHS of call: ");
 714                         print_generic_stmt (dump_file, stmt, TDF_SLIM);
 715                         fprintf (dump_file, "\n");
 716                       }
 717                     push_stmt_changes (bsi_stmt_ptr (bsi));
 718                     TREE_BLOCK (call) = TREE_BLOCK (stmt);
 719                     bsi_replace (&bsi, call, false);
 720                     maybe_clean_or_replace_eh_stmt (stmt, call);
 721                     mark_symbols_for_renaming (call);
 722                     pop_stmt_changes (bsi_stmt_ptr (bsi));
 723                   }
 724                 else
 725                   {
 726                     if (dump_file && (dump_flags & TDF_DETAILS))
 727                       {
 728                         fprintf (dump_file, "  Deleted dead store '");
 729                         print_generic_expr (dump_file, stmt, dump_flags);
 730                         fprintf (dump_file, "'\n");
 731                       }
 732                     removed = true;
 733                     bsi_remove (&bsi, true);
 734                     todo |= TODO_cleanup_cfg;
 735                   }
 736                 todo |= TODO_remove_unused_locals | TODO_ggc_collect;
 737               }
 738           }
 739         if (!removed)
 740           bsi_next (&bsi);
 741       }
 742   BITMAP_FREE (variables_loaded);
 743   return todo;
 744 }
 745
 746 struct gimple_opt_pass pass_simple_dse =
 747 {
 748  {
 749   GIMPLE_PASS,
 750   "sdse",                               /* name */
 751   NULL,                                 /* gate */
 752   execute_simple_dse,                   /* execute */
 753   NULL,                                 /* sub */
 754   NULL,                                 /* next */
 755   0,                                    /* static_pass_number */
 756   0,                                    /* tv_id */
 757   PROP_ssa,                             /* properties_required */
 758   0,                                    /* properties_provided */
 759   0,                                    /* properties_destroyed */
 760   0,                                    /* todo_flags_start */
 761   TODO_dump_func                        /* todo_flags_finish */
 762  }
 763 };