gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "timevar.h"
  30 #include "gimple-pretty-print.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 #include "langhooks.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 /* Bitmap of blocks that have had EH statements cleaned.  We should
  87    remove their dead edges eventually.  */
  88 static bitmap need_eh_cleanup;
  89
  90 static bool gate_dse (void);
  91 static unsigned int tree_ssa_dse (void);
  92 static void dse_initialize_block_local_data (struct dom_walk_data *,
  93                                              basic_block,
  94                                              bool);
  95 static void dse_enter_block (struct dom_walk_data *, basic_block);
  96 static void dse_leave_block (struct dom_walk_data *, basic_block);
  97 static void record_voperand_set (bitmap, bitmap *, unsigned int);
  98
  99 /* Returns uid of statement STMT.  */
 100
 101 static unsigned
 102 get_stmt_uid (gimple stmt)
 103 {
 104   if (gimple_code (stmt) == GIMPLE_PHI)
 105     return SSA_NAME_VERSION (gimple_phi_result (stmt))
 106            + gimple_stmt_max_uid (cfun);
 107
 108   return gimple_uid (stmt);
 109 }
 110
 111 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 112
 113 static void
 114 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 115 {
 116   /* Lazily allocate the bitmap.  Note that we do not get a notification
 117      when the block local data structures die, so we allocate the local
 118      bitmap backed by the GC system.  */
 119   if (*local == NULL)
 120     *local = BITMAP_GGC_ALLOC ();
 121
 122   /* Set the bit in the local and global bitmaps.  */
 123   bitmap_set_bit (*local, uid);
 124   bitmap_set_bit (global, uid);
 125 }
 126
 127 /* Initialize block local data structures.  */
 128
 129 static void
 130 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 131                                  basic_block bb ATTRIBUTE_UNUSED,
 132                                  bool recycled)
 133 {
 134   struct dse_block_local_data *bd
 135     = (struct dse_block_local_data *)
 136         VEC_last (void_p, walk_data->block_data_stack);
 137
 138   /* If we are given a recycled block local data structure, ensure any
 139      bitmap associated with the block is cleared.  */
 140   if (recycled)
 141     {
 142       if (bd->stores)
 143         bitmap_clear (bd->stores);
 144     }
 145 }
 146
 147 /* A helper of dse_optimize_stmt.
 148    Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
 149    may prove STMT to be dead.
 150    Return TRUE if the above conditions are met, otherwise FALSE.  */
 151
 152 static bool
 153 dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
 154 {
 155   gimple temp;
 156   unsigned cnt = 0;
 157
 158   *use_stmt = NULL;
 159
 160   /* Find the first dominated statement that clobbers (part of) the
 161      memory stmt stores to with no intermediate statement that may use
 162      part of the memory stmt stores.  That is, find a store that may
 163      prove stmt to be a dead store.  */
 164   temp = stmt;
 165   do
 166     {
 167       gimple use_stmt;
 168       imm_use_iterator ui;
 169       bool fail = false;
 170       tree defvar;
 171
 172       /* Limit stmt walking to be linear in the number of possibly
 173          dead stores.  */
 174       if (++cnt > 256)
 175         return false;
 176
 177       if (gimple_code (temp) == GIMPLE_PHI)
 178         defvar = PHI_RESULT (temp);
 179       else
 180         defvar = gimple_vdef (temp);
 181       temp = NULL;
 182       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 183         {
 184           cnt++;
 185
 186           /* If we ever reach our DSE candidate stmt again fail.  We
 187              cannot handle dead stores in loops.  */
 188           if (use_stmt == stmt)
 189             {
 190               fail = true;
 191               BREAK_FROM_IMM_USE_STMT (ui);
 192             }
 193           /* In simple cases we can look through PHI nodes, but we
 194              have to be careful with loops and with memory references
 195              containing operands that are also operands of PHI nodes.
 196              See gcc.c-torture/execute/20051110-*.c.  */
 197           else if (gimple_code (use_stmt) == GIMPLE_PHI)
 198             {
 199               if (temp
 200                   /* Make sure we are not in a loop latch block.  */
 201                   || gimple_bb (stmt) == gimple_bb (use_stmt)
 202                   || dominated_by_p (CDI_DOMINATORS,
 203                                      gimple_bb (stmt), gimple_bb (use_stmt))
 204                   /* We can look through PHIs to regions post-dominating
 205                      the DSE candidate stmt.  */
 206                   || !dominated_by_p (CDI_POST_DOMINATORS,
 207                                       gimple_bb (stmt), gimple_bb (use_stmt)))
 208                 {
 209                   fail = true;
 210                   BREAK_FROM_IMM_USE_STMT (ui);
 211                 }
 212               temp = use_stmt;
 213             }
 214           /* If the statement is a use the store is not dead.  */
 215           else if (ref_maybe_used_by_stmt_p (use_stmt,
 216                                              gimple_assign_lhs (stmt)))
 217             {
 218               fail = true;
 219               BREAK_FROM_IMM_USE_STMT (ui);
 220             }
 221           /* If this is a store, remember it or bail out if we have
 222              multiple ones (the will be in different CFG parts then).  */
 223           else if (gimple_vdef (use_stmt))
 224             {
 225               if (temp)
 226                 {
 227                   fail = true;
 228                   BREAK_FROM_IMM_USE_STMT (ui);
 229                 }
 230               temp = use_stmt;
 231             }
 232         }
 233
 234       if (fail)
 235         return false;
 236
 237       /* If we didn't find any definition this means the store is dead
 238          if it isn't a store to global reachable memory.  In this case
 239          just pretend the stmt makes itself dead.  Otherwise fail.  */
 240       if (!temp)
 241         {
 242           if (is_hidden_global_store (stmt))
 243             return false;
 244
 245           temp = stmt;
 246           break;
 247         }
 248     }
 249   /* We deliberately stop on clobbering statements and not only on
 250      killing ones to make walking cheaper.  Otherwise we can just
 251      continue walking until both stores have equal reference trees.  */
 252   while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt)));
 253
 254   if (!is_gimple_assign (temp))
 255     return false;
 256
 257   *use_stmt = temp;
 258
 259   return true;
 260 }
 261
 262
 263 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 264
 265    A dead store is a store into a memory location which will later be
 266    overwritten by another store without any intervening loads.  In this
 267    case the earlier store can be deleted.
 268
 269    In our SSA + virtual operand world we use immediate uses of virtual
 270    operands to detect dead stores.  If a store's virtual definition
 271    is used precisely once by a later store to the same location which
 272    post dominates the first store, then the first store is dead.  */
 273
 274 static void
 275 dse_optimize_stmt (struct dse_global_data *dse_gd,
 276                    struct dse_block_local_data *bd,
 277                    gimple_stmt_iterator gsi)
 278 {
 279   gimple stmt = gsi_stmt (gsi);
 280
 281   /* If this statement has no virtual defs, then there is nothing
 282      to do.  */
 283   if (!gimple_vdef (stmt))
 284     return;
 285
 286   /* We know we have virtual definitions.  If this is a GIMPLE_ASSIGN
 287      that's not also a function call, then record it into our table.  */
 288   if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
 289     return;
 290
 291   if (gimple_has_volatile_ops (stmt))
 292     return;
 293
 294   if (is_gimple_assign (stmt))
 295     {
 296       gimple use_stmt;
 297
 298       record_voperand_set (dse_gd->stores, &bd->stores, gimple_uid (stmt));
 299
 300       if (!dse_possible_dead_store_p (stmt, &use_stmt))
 301         return;
 302
 303       /* If we have precisely one immediate use at this point and the
 304          stores are to the same memory location or there is a chain of
 305          virtual uses from stmt and the stmt which stores to that same
 306          memory location, then we may have found redundant store.  */
 307       if (bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 308           && (operand_equal_p (gimple_assign_lhs (stmt),
 309                                gimple_assign_lhs (use_stmt), 0)
 310               || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt))))
 311         {
 312           /* If use_stmt is or might be a nop assignment, e.g. for
 313              struct { ... } S a, b, *p; ...
 314              b = a; b = b;
 315              or
 316              b = a; b = *p; where p might be &b,
 317              or
 318              *p = a; *p = b; where p might be &b,
 319              or
 320              *p = *u; *p = *v; where p might be v, then USE_STMT
 321              acts as a use as well as definition, so store in STMT
 322              is not dead.  */
 323           if (stmt != use_stmt
 324               && !is_gimple_reg (gimple_assign_rhs1 (use_stmt))
 325               && !is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))
 326               /* ???  Should {} be invariant?  */
 327               && gimple_assign_rhs_code (use_stmt) != CONSTRUCTOR
 328               && refs_may_alias_p (gimple_assign_lhs (use_stmt),
 329                                    gimple_assign_rhs1 (use_stmt)))
 330             return;
 331
 332           if (dump_file && (dump_flags & TDF_DETAILS))
 333             {
 334               fprintf (dump_file, "  Deleted dead store '");
 335               print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0);
 336               fprintf (dump_file, "'\n");
 337             }
 338
 339           /* Then we need to fix the operand of the consuming stmt.  */
 340           unlink_stmt_vdef (stmt);
 341
 342           bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
 343
 344           /* Remove the dead store.  */
 345           gsi_remove (&gsi, true);
 346
 347           /* And release any SSA_NAMEs set in this statement back to the
 348              SSA_NAME manager.  */
 349           release_defs (stmt);
 350         }
 351     }
 352 }
 353
 354 /* Record that we have seen the PHIs at the start of BB which correspond
 355    to virtual operands.  */
 356 static void
 357 dse_record_phi (struct dse_global_data *dse_gd,
 358                 struct dse_block_local_data *bd,
 359                 gimple phi)
 360 {
 361   if (!is_gimple_reg (gimple_phi_result (phi)))
 362     record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi));
 363 }
 364
 365 static void
 366 dse_enter_block (struct dom_walk_data *walk_data, basic_block bb)
 367 {
 368   struct dse_block_local_data *bd
 369     = (struct dse_block_local_data *)
 370         VEC_last (void_p, walk_data->block_data_stack);
 371   struct dse_global_data *dse_gd
 372     = (struct dse_global_data *) walk_data->global_data;
 373   gimple_stmt_iterator gsi;
 374
 375   for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi))
 376     dse_optimize_stmt (dse_gd, bd, gsi);
 377   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 378     dse_record_phi (dse_gd, bd, gsi_stmt (gsi));
 379 }
 380
 381 static void
 382 dse_leave_block (struct dom_walk_data *walk_data,
 383                  basic_block bb ATTRIBUTE_UNUSED)
 384 {
 385   struct dse_block_local_data *bd
 386     = (struct dse_block_local_data *)
 387         VEC_last (void_p, walk_data->block_data_stack);
 388   struct dse_global_data *dse_gd
 389     = (struct dse_global_data *) walk_data->global_data;
 390   bitmap stores = dse_gd->stores;
 391   unsigned int i;
 392   bitmap_iterator bi;
 393
 394   /* Unwind the stores noted in this basic block.  */
 395   if (bd->stores)
 396     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 397       {
 398         bitmap_clear_bit (stores, i);
 399       }
 400 }
 401
 402 /* Main entry point.  */
 403
 404 static unsigned int
 405 tree_ssa_dse (void)
 406 {
 407   struct dom_walk_data walk_data;
 408   struct dse_global_data dse_gd;
 409
 410   need_eh_cleanup = BITMAP_ALLOC (NULL);
 411
 412   renumber_gimple_stmt_uids ();
 413
 414   /* We might consider making this a property of each pass so that it
 415      can be [re]computed on an as-needed basis.  Particularly since
 416      this pass could be seen as an extension of DCE which needs post
 417      dominators.  */
 418   calculate_dominance_info (CDI_POST_DOMINATORS);
 419   calculate_dominance_info (CDI_DOMINATORS);
 420
 421   /* Dead store elimination is fundamentally a walk of the post-dominator
 422      tree and a backwards walk of statements within each block.  */
 423   walk_data.dom_direction = CDI_POST_DOMINATORS;
 424   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 425   walk_data.before_dom_children = dse_enter_block;
 426   walk_data.after_dom_children = dse_leave_block;
 427
 428   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 429
 430   /* This is the main hash table for the dead store elimination pass.  */
 431   dse_gd.stores = BITMAP_ALLOC (NULL);
 432   walk_data.global_data = &dse_gd;
 433
 434   /* Initialize the dominator walker.  */
 435   init_walk_dominator_tree (&walk_data);
 436
 437   /* Recursively walk the dominator tree.  */
 438   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 439
 440   /* Finalize the dominator walker.  */
 441   fini_walk_dominator_tree (&walk_data);
 442
 443   /* Release the main bitmap.  */
 444   BITMAP_FREE (dse_gd.stores);
 445
 446   /* Removal of stores may make some EH edges dead.  Purge such edges from
 447      the CFG as needed.  */
 448   if (!bitmap_empty_p (need_eh_cleanup))
 449     {
 450       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 451       cleanup_tree_cfg ();
 452     }
 453
 454   BITMAP_FREE (need_eh_cleanup);
 455
 456   /* For now, just wipe the post-dominator information.  */
 457   free_dominance_info (CDI_POST_DOMINATORS);
 458   return 0;
 459 }
 460
 461 static bool
 462 gate_dse (void)
 463 {
 464   return flag_tree_dse != 0;
 465 }
 466
 467 struct gimple_opt_pass pass_dse =
 468 {
 469  {
 470   GIMPLE_PASS,
 471   "dse",                        /* name */
 472   gate_dse,                     /* gate */
 473   tree_ssa_dse,                 /* execute */
 474   NULL,                         /* sub */
 475   NULL,                         /* next */
 476   0,                            /* static_pass_number */
 477   TV_TREE_DSE,                  /* tv_id */
 478   PROP_cfg | PROP_ssa,          /* properties_required */
 479   0,                            /* properties_provided */
 480   0,                            /* properties_destroyed */
 481   0,                            /* todo_flags_start */
 482   TODO_dump_func
 483     | TODO_ggc_collect
 484     | TODO_verify_ssa           /* todo_flags_finish */
 485  }
 486 };
 487