gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
   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 "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 #include "langhooks.h"
  38
  39 /* This file implements dead store elimination.
  40
  41    A dead store is a store into a memory location which will later be
  42    overwritten by another store without any intervening loads.  In this
  43    case the earlier store can be deleted.
  44
  45    In our SSA + virtual operand world we use immediate uses of virtual
  46    operands to detect dead stores.  If a store's virtual definition
  47    is used precisely once by a later store to the same location which
  48    post dominates the first store, then the first store is dead.
  49
  50    The single use of the store's virtual definition ensures that
  51    there are no intervening aliased loads and the requirement that
  52    the second load post dominate the first ensures that if the earlier
  53    store executes, then the later stores will execute before the function
  54    exits.
  55
  56    It may help to think of this as first moving the earlier store to
  57    the point immediately before the later store.  Again, the single
  58    use of the virtual definition and the post-dominance relationship
  59    ensure that such movement would be safe.  Clearly if there are
  60    back to back stores, then the second is redundant.
  61
  62    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
  63    may also help in understanding this code since it discusses the
  64    relationship between dead store and redundant load elimination.  In
  65    fact, they are the same transformation applied to different views of
  66    the CFG.  */
  67
  68
  69 struct dse_global_data
  70 {
  71   /* This is the global bitmap for store statements.
  72
  73      Each statement has a unique ID.  When we encounter a store statement
  74      that we want to record, set the bit corresponding to the statement's
  75      unique ID in this bitmap.  */
  76   bitmap stores;
  77 };
  78
  79 /* We allocate a bitmap-per-block for stores which are encountered
  80    during the scan of that block.  This allows us to restore the
  81    global bitmap of stores when we finish processing a block.  */
  82 struct dse_block_local_data
  83 {
  84   bitmap stores;
  85 };
  86
  87 static bool gate_dse (void);
  88 static unsigned int tree_ssa_dse (void);
  89 static void dse_initialize_block_local_data (struct dom_walk_data *,
  90                                              basic_block,
  91                                              bool);
  92 static void dse_enter_block (struct dom_walk_data *, basic_block);
  93 static void dse_leave_block (struct dom_walk_data *, basic_block);
  94 static void record_voperand_set (bitmap, bitmap *, unsigned int);
  95
  96 /* Returns uid of statement STMT.  */
  97
  98 static unsigned
  99 get_stmt_uid (gimple stmt)
 100 {
 101   if (gimple_code (stmt) == GIMPLE_PHI)
 102     return SSA_NAME_VERSION (gimple_phi_result (stmt))
 103            + gimple_stmt_max_uid (cfun);
 104
 105   return gimple_uid (stmt);
 106 }
 107
 108 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 109
 110 static void
 111 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 112 {
 113   /* Lazily allocate the bitmap.  Note that we do not get a notification
 114      when the block local data structures die, so we allocate the local
 115      bitmap backed by the GC system.  */
 116   if (*local == NULL)
 117     *local = BITMAP_GGC_ALLOC ();
 118
 119   /* Set the bit in the local and global bitmaps.  */
 120   bitmap_set_bit (*local, uid);
 121   bitmap_set_bit (global, uid);
 122 }
 123
 124 /* Initialize block local data structures.  */
 125
 126 static void
 127 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 128                                  basic_block bb ATTRIBUTE_UNUSED,
 129                                  bool recycled)
 130 {
 131   struct dse_block_local_data *bd
 132     = (struct dse_block_local_data *)
 133         VEC_last (void_p, walk_data->block_data_stack);
 134
 135   /* If we are given a recycled block local data structure, ensure any
 136      bitmap associated with the block is cleared.  */
 137   if (recycled)
 138     {
 139       if (bd->stores)
 140         bitmap_clear (bd->stores);
 141     }
 142 }
 143
 144 /* A helper of dse_optimize_stmt.
 145    Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
 146    may prove STMT to be dead.
 147    Return TRUE if the above conditions are met, otherwise FALSE.  */
 148
 149 static bool
 150 dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
 151 {
 152   gimple temp;
 153   unsigned cnt = 0;
 154
 155   *use_stmt = NULL;
 156
 157   /* Find the first dominated statement that clobbers (part of) the
 158      memory stmt stores to with no intermediate statement that may use
 159      part of the memory stmt stores.  That is, find a store that may
 160      prove stmt to be a dead store.  */
 161   temp = stmt;
 162   do
 163     {
 164       gimple prev, use_stmt;
 165       imm_use_iterator ui;
 166       bool fail = false;
 167       tree defvar;
 168
 169       /* Limit stmt walking to be linear in the number of possibly
 170          dead stores.  */
 171       if (++cnt > 256)
 172         return false;
 173
 174       if (gimple_code (temp) == GIMPLE_PHI)
 175         defvar = PHI_RESULT (temp);
 176       else
 177         defvar = gimple_vdef (temp);
 178       prev = temp;
 179       temp = NULL;
 180       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 181         {
 182           cnt++;
 183
 184           /* In simple cases we can look through PHI nodes, but we
 185              have to be careful with loops and with memory references
 186              containing operands that are also operands of PHI nodes.
 187              See gcc.c-torture/execute/20051110-*.c.  */
 188           if (gimple_code (use_stmt) == GIMPLE_PHI)
 189             {
 190               if (temp
 191                   /* We can look through PHIs to post-dominated regions
 192                      without worrying if the use not also dominates prev
 193                      (in which case it would be a loop PHI with the use
 194                      in a latch block).  */
 195                   || gimple_bb (prev) == gimple_bb (use_stmt)
 196                   || !dominated_by_p (CDI_POST_DOMINATORS,
 197                                       gimple_bb (prev), gimple_bb (use_stmt))
 198                   || dominated_by_p (CDI_DOMINATORS,
 199                                      gimple_bb (prev), gimple_bb (use_stmt)))
 200                 {
 201                   fail = true;
 202                   BREAK_FROM_IMM_USE_STMT (ui);
 203                 }
 204               temp = use_stmt;
 205             }
 206           /* If the statement is a use the store is not dead.  */
 207           else if (ref_maybe_used_by_stmt_p (use_stmt,
 208                                              gimple_assign_lhs (stmt)))
 209             {
 210               fail = true;
 211               BREAK_FROM_IMM_USE_STMT (ui);
 212             }
 213           /* If this is a store, remember it or bail out if we have
 214              multiple ones (the will be in different CFG parts then).  */
 215           else if (gimple_vdef (use_stmt))
 216             {
 217               if (temp)
 218                 {
 219                   fail = true;
 220                   BREAK_FROM_IMM_USE_STMT (ui);
 221                 }
 222               temp = use_stmt;
 223             }
 224         }
 225
 226       if (fail)
 227         return false;
 228
 229       /* If we didn't find any definition this means the store is dead
 230          if it isn't a store to global reachable memory.  In this case
 231          just pretend the stmt makes itself dead.  Otherwise fail.  */
 232       if (!temp)
 233         {
 234           if (is_hidden_global_store (stmt))
 235             return false;
 236
 237           temp = stmt;
 238           break;
 239         }
 240     }
 241   /* We deliberately stop on clobbering statements and not only on
 242      killing ones to make walking cheaper.  Otherwise we can just
 243      continue walking until both stores have equal reference trees.  */
 244   while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt)));
 245
 246   if (!is_gimple_assign (temp))
 247     return false;
 248
 249   *use_stmt = temp;
 250
 251   return true;
 252 }
 253
 254
 255 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 256
 257    A dead store is a store into a memory location which will later be
 258    overwritten by another store without any intervening loads.  In this
 259    case the earlier store can be deleted.
 260
 261    In our SSA + virtual operand world we use immediate uses of virtual
 262    operands to detect dead stores.  If a store's virtual definition
 263    is used precisely once by a later store to the same location which
 264    post dominates the first store, then the first store is dead.  */
 265
 266 static void
 267 dse_optimize_stmt (struct dse_global_data *dse_gd,
 268                    struct dse_block_local_data *bd,
 269                    gimple_stmt_iterator gsi)
 270 {
 271   gimple stmt = gsi_stmt (gsi);
 272
 273   /* If this statement has no virtual defs, then there is nothing
 274      to do.  */
 275   if (!gimple_vdef (stmt))
 276     return;
 277
 278   /* We know we have virtual definitions.  If this is a GIMPLE_ASSIGN
 279      that's not also a function call, then record it into our table.  */
 280   if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
 281     return;
 282
 283   if (gimple_has_volatile_ops (stmt))
 284     return;
 285
 286   if (is_gimple_assign (stmt))
 287     {
 288       gimple use_stmt;
 289
 290       record_voperand_set (dse_gd->stores, &bd->stores, gimple_uid (stmt));
 291
 292       if (!dse_possible_dead_store_p (stmt, &use_stmt))
 293         return;
 294
 295       /* If we have precisely one immediate use at this point and the
 296          stores are to the same memory location or there is a chain of
 297          virtual uses from stmt and the stmt which stores to that same
 298          memory location, then we may have found redundant store.  */
 299       if (bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 300           && operand_equal_p (gimple_assign_lhs (stmt),
 301                               gimple_assign_lhs (use_stmt), 0))
 302         {
 303           /* If use_stmt is or might be a nop assignment, e.g. for
 304              struct { ... } S a, b, *p; ...
 305              b = a; b = b;
 306              or
 307              b = a; b = *p; where p might be &b,
 308              or
 309              *p = a; *p = b; where p might be &b,
 310              or
 311              *p = *u; *p = *v; where p might be v, then USE_STMT
 312              acts as a use as well as definition, so store in STMT
 313              is not dead.  */
 314           if (stmt != use_stmt
 315               && !is_gimple_reg (gimple_assign_rhs1 (use_stmt))
 316               && !is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))
 317               /* ???  Should {} be invariant?  */
 318               && gimple_assign_rhs_code (use_stmt) != CONSTRUCTOR
 319               && refs_may_alias_p (gimple_assign_lhs (use_stmt),
 320                                    gimple_assign_rhs1 (use_stmt)))
 321             return;
 322
 323           if (dump_file && (dump_flags & TDF_DETAILS))
 324             {
 325               fprintf (dump_file, "  Deleted dead store '");
 326               print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0);
 327               fprintf (dump_file, "'\n");
 328             }
 329
 330           /* Then we need to fix the operand of the consuming stmt.  */
 331           unlink_stmt_vdef (stmt);
 332
 333           /* Remove the dead store.  */
 334           gsi_remove (&gsi, true);
 335
 336           /* And release any SSA_NAMEs set in this statement back to the
 337              SSA_NAME manager.  */
 338           release_defs (stmt);
 339         }
 340     }
 341 }
 342
 343 /* Record that we have seen the PHIs at the start of BB which correspond
 344    to virtual operands.  */
 345 static void
 346 dse_record_phi (struct dse_global_data *dse_gd,
 347                 struct dse_block_local_data *bd,
 348                 gimple phi)
 349 {
 350   if (!is_gimple_reg (gimple_phi_result (phi)))
 351     record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi));
 352 }
 353
 354 static void
 355 dse_enter_block (struct dom_walk_data *walk_data, basic_block bb)
 356 {
 357   struct dse_block_local_data *bd
 358     = (struct dse_block_local_data *)
 359         VEC_last (void_p, walk_data->block_data_stack);
 360   struct dse_global_data *dse_gd
 361     = (struct dse_global_data *) walk_data->global_data;
 362   gimple_stmt_iterator gsi;
 363
 364   for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi))
 365     dse_optimize_stmt (dse_gd, bd, gsi);
 366   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 367     dse_record_phi (dse_gd, bd, gsi_stmt (gsi));
 368 }
 369
 370 static void
 371 dse_leave_block (struct dom_walk_data *walk_data,
 372                  basic_block bb ATTRIBUTE_UNUSED)
 373 {
 374   struct dse_block_local_data *bd
 375     = (struct dse_block_local_data *)
 376         VEC_last (void_p, walk_data->block_data_stack);
 377   struct dse_global_data *dse_gd
 378     = (struct dse_global_data *) walk_data->global_data;
 379   bitmap stores = dse_gd->stores;
 380   unsigned int i;
 381   bitmap_iterator bi;
 382
 383   /* Unwind the stores noted in this basic block.  */
 384   if (bd->stores)
 385     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 386       {
 387         bitmap_clear_bit (stores, i);
 388       }
 389 }
 390
 391 /* Main entry point.  */
 392
 393 static unsigned int
 394 tree_ssa_dse (void)
 395 {
 396   struct dom_walk_data walk_data;
 397   struct dse_global_data dse_gd;
 398
 399   renumber_gimple_stmt_uids ();
 400
 401   /* We might consider making this a property of each pass so that it
 402      can be [re]computed on an as-needed basis.  Particularly since
 403      this pass could be seen as an extension of DCE which needs post
 404      dominators.  */
 405   calculate_dominance_info (CDI_POST_DOMINATORS);
 406   calculate_dominance_info (CDI_DOMINATORS);
 407
 408   /* Dead store elimination is fundamentally a walk of the post-dominator
 409      tree and a backwards walk of statements within each block.  */
 410   walk_data.dom_direction = CDI_POST_DOMINATORS;
 411   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 412   walk_data.before_dom_children = dse_enter_block;
 413   walk_data.after_dom_children = dse_leave_block;
 414
 415   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 416
 417   /* This is the main hash table for the dead store elimination pass.  */
 418   dse_gd.stores = BITMAP_ALLOC (NULL);
 419   walk_data.global_data = &dse_gd;
 420
 421   /* Initialize the dominator walker.  */
 422   init_walk_dominator_tree (&walk_data);
 423
 424   /* Recursively walk the dominator tree.  */
 425   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 426
 427   /* Finalize the dominator walker.  */
 428   fini_walk_dominator_tree (&walk_data);
 429
 430   /* Release the main bitmap.  */
 431   BITMAP_FREE (dse_gd.stores);
 432
 433   /* For now, just wipe the post-dominator information.  */
 434   free_dominance_info (CDI_POST_DOMINATORS);
 435   return 0;
 436 }
 437
 438 static bool
 439 gate_dse (void)
 440 {
 441   return flag_tree_dse != 0;
 442 }
 443
 444 struct gimple_opt_pass pass_dse =
 445 {
 446  {
 447   GIMPLE_PASS,
 448   "dse",                        /* name */
 449   gate_dse,                     /* gate */
 450   tree_ssa_dse,                 /* execute */
 451   NULL,                         /* sub */
 452   NULL,                         /* next */
 453   0,                            /* static_pass_number */
 454   TV_TREE_DSE,                  /* tv_id */
 455   PROP_cfg | PROP_ssa,          /* properties_required */
 456   0,                            /* properties_provided */
 457   0,                            /* properties_destroyed */
 458   0,                            /* todo_flags_start */
 459   TODO_dump_func
 460     | TODO_ggc_collect
 461     | TODO_verify_ssa           /* todo_flags_finish */
 462  }
 463 };
 464