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