gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "basic-block.h"
  31 #include "timevar.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-pass.h"
  35 #include "tree-dump.h"
  36 #include "domwalk.h"
  37 #include "flags.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 void 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_optimize_stmt (struct dom_walk_data *,
  93                                basic_block,
  94                                block_stmt_iterator);
  95 static void dse_record_phis (struct dom_walk_data *, basic_block);
  96 static void dse_finalize_block (struct dom_walk_data *, basic_block);
  97 static void record_voperand_set (bitmap, bitmap *, unsigned int);
  98
  99 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 100                                    nodes are assigned using the versions of
 101                                    ssa names they define.  */
 102
 103 /* Returns uid of statement STMT.  */
 104
 105 static unsigned
 106 get_stmt_uid (tree stmt)
 107 {
 108   if (TREE_CODE (stmt) == PHI_NODE)
 109     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 110
 111   return stmt_ann (stmt)->uid;
 112 }
 113
 114 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 115
 116 static void
 117 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 118 {
 119   /* Lazily allocate the bitmap.  Note that we do not get a notification
 120      when the block local data structures die, so we allocate the local
 121      bitmap backed by the GC system.  */
 122   if (*local == NULL)
 123     *local = BITMAP_GGC_ALLOC ();
 124
 125   /* Set the bit in the local and global bitmaps.  */
 126   bitmap_set_bit (*local, uid);
 127   bitmap_set_bit (global, uid);
 128 }
 129
 130 /* Initialize block local data structures.  */
 131
 132 static void
 133 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 134                                  basic_block bb ATTRIBUTE_UNUSED,
 135                                  bool recycled)
 136 {
 137   struct dse_block_local_data *bd
 138     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 139
 140   /* If we are given a recycled block local data structure, ensure any
 141      bitmap associated with the block is cleared.  */
 142   if (recycled)
 143     {
 144       if (bd->stores)
 145         bitmap_clear (bd->stores);
 146     }
 147 }
 148
 149 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 150
 151    A dead store is a store into a memory location which will later be
 152    overwritten by another store without any intervening loads.  In this
 153    case the earlier store can be deleted.
 154
 155    In our SSA + virtual operand world we use immediate uses of virtual
 156    operands to detect dead stores.  If a store's virtual definition
 157    is used precisely once by a later store to the same location which
 158    post dominates the first store, then the first store is dead.  */
 159
 160 static void
 161 dse_optimize_stmt (struct dom_walk_data *walk_data,
 162                    basic_block bb ATTRIBUTE_UNUSED,
 163                    block_stmt_iterator bsi)
 164 {
 165   struct dse_block_local_data *bd
 166     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 167   struct dse_global_data *dse_gd = walk_data->global_data;
 168   tree stmt = bsi_stmt (bsi);
 169   stmt_ann_t ann = stmt_ann (stmt);
 170   v_may_def_optype v_may_defs;
 171   v_must_def_optype v_must_defs;
 172
 173   v_may_defs = V_MAY_DEF_OPS (ann);
 174   v_must_defs = V_MUST_DEF_OPS (ann);
 175
 176   /* If this statement has no virtual defs, then there is nothing
 177      to do.  */
 178   if (NUM_V_MAY_DEFS (v_may_defs) == 0
 179       && NUM_V_MUST_DEFS (v_must_defs) == 0)
 180     return;
 181
 182   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
 183      not also a function call, then record it into our table.  */
 184   if (get_call_expr_in (stmt))
 185     return;
 186
 187   if (ann->has_volatile_ops)
 188     return;
 189
 190   if (TREE_CODE (stmt) == MODIFY_EXPR)
 191     {
 192       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 193       use_operand_p use_p = NULL;
 194       tree use, use_stmt, temp;
 195       tree defvar = NULL_TREE, usevar = NULL_TREE;
 196       bool fail = false;
 197       use_operand_p var2;
 198       def_operand_p var1;
 199       ssa_op_iter op_iter;
 200
 201       /* We want to verify that each virtual definition in STMT has
 202          precisely one use and that all the virtual definitions are
 203          used by the same single statement.  When complete, we
 204          want USE_STMT to refer to the one statment which uses
 205          all of the virtual definitions from STMT.  */
 206       use_stmt = NULL;
 207       FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
 208         {
 209           defvar = DEF_FROM_PTR (var1);
 210           usevar = USE_FROM_PTR (var2);
 211
 212           /* If this virtual def does not have precisely one use, then
 213              we will not be able to eliminate STMT.  */
 214           if (num_imm_uses (defvar) != 1)
 215             {
 216               fail = true;
 217               break;
 218             }
 219
 220           /* Get the one and only immediate use of DEFVAR.  */
 221           single_imm_use (defvar, &use_p, &temp);
 222           gcc_assert (use_p != NULL_USE_OPERAND_P);
 223           first_use_p = use_p;
 224           use = USE_FROM_PTR (use_p);
 225
 226           /* If the immediate use of DEF_VAR is not the same as the
 227              previously find immediate uses, then we will not be able
 228              to eliminate STMT.  */
 229           if (use_stmt == NULL)
 230             use_stmt = temp;
 231           else if (temp != use_stmt)
 232             {
 233               fail = true;
 234               break;
 235             }
 236         }
 237
 238       if (fail)
 239         {
 240           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 241           return;
 242         }
 243
 244       /* Skip through any PHI nodes we have already seen if the PHI
 245          represents the only use of this store.
 246
 247          Note this does not handle the case where the store has
 248          multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
 249          same block.  */
 250       while (use_p != NULL_USE_OPERAND_P
 251              && TREE_CODE (use_stmt) == PHI_NODE
 252              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
 253         {
 254           /* Skip past this PHI and loop again in case we had a PHI
 255              chain.  */
 256           if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
 257             use = USE_FROM_PTR (use_p);
 258         }
 259
 260       /* If we have precisely one immediate use at this point, then we may
 261          have found redundant store.  */
 262       if (use_p != NULL_USE_OPERAND_P
 263           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 264           && operand_equal_p (TREE_OPERAND (stmt, 0),
 265                               TREE_OPERAND (use_stmt, 0), 0))
 266         {
 267           tree def;
 268           ssa_op_iter iter;
 269
 270           /* Make sure we propagate the ABNORMAL bit setting.  */
 271           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
 272             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 273           /* Then we need to fix the operand of the consuming stmt.  */
 274           SET_USE (first_use_p, usevar);
 275
 276           if (dump_file && (dump_flags & TDF_DETAILS))
 277             {
 278               fprintf (dump_file, "  Deleted dead store '");
 279               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 280               fprintf (dump_file, "'\n");
 281             }
 282
 283           /* Remove the dead store.  */
 284           bsi_remove (&bsi);
 285
 286           /* The virtual defs for the dead statement will need to be
 287              updated.  Since these names are going to disappear,
 288              FUD chains for uses downstream need to be updated.  */
 289           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 290             mark_sym_for_renaming (SSA_NAME_VAR (def));
 291
 292           /* And release any SSA_NAMEs set in this statement back to the
 293              SSA_NAME manager.  */
 294           release_defs (stmt);
 295         }
 296
 297       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 298     }
 299 }
 300
 301 /* Record that we have seen the PHIs at the start of BB which correspond
 302    to virtual operands.  */
 303 static void
 304 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 305 {
 306   struct dse_block_local_data *bd
 307     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 308   struct dse_global_data *dse_gd = walk_data->global_data;
 309   tree phi;
 310
 311   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 312     if (!is_gimple_reg (PHI_RESULT (phi)))
 313       record_voperand_set (dse_gd->stores,
 314                            &bd->stores,
 315                            get_stmt_uid (phi));
 316 }
 317
 318 static void
 319 dse_finalize_block (struct dom_walk_data *walk_data,
 320                     basic_block bb ATTRIBUTE_UNUSED)
 321 {
 322   struct dse_block_local_data *bd
 323     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 324   struct dse_global_data *dse_gd = walk_data->global_data;
 325   bitmap stores = dse_gd->stores;
 326   unsigned int i;
 327   bitmap_iterator bi;
 328
 329   /* Unwind the stores noted in this basic block.  */
 330   if (bd->stores)
 331     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 332       {
 333         bitmap_clear_bit (stores, i);
 334       }
 335 }
 336
 337 static void
 338 tree_ssa_dse (void)
 339 {
 340   struct dom_walk_data walk_data;
 341   struct dse_global_data dse_gd;
 342   basic_block bb;
 343
 344   /* Create a UID for each statement in the function.  Ordering of the
 345      UIDs is not important for this pass.  */
 346   max_stmt_uid = 0;
 347   FOR_EACH_BB (bb)
 348     {
 349       block_stmt_iterator bsi;
 350
 351       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 352         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 353     }
 354
 355   /* We might consider making this a property of each pass so that it
 356      can be [re]computed on an as-needed basis.  Particularly since
 357      this pass could be seen as an extension of DCE which needs post
 358      dominators.  */
 359   calculate_dominance_info (CDI_POST_DOMINATORS);
 360
 361   /* Dead store elimination is fundamentally a walk of the post-dominator
 362      tree and a backwards walk of statements within each block.  */
 363   walk_data.walk_stmts_backward = true;
 364   walk_data.dom_direction = CDI_POST_DOMINATORS;
 365   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 366   walk_data.before_dom_children_before_stmts = NULL;
 367   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 368   walk_data.before_dom_children_after_stmts = dse_record_phis;
 369   walk_data.after_dom_children_before_stmts = NULL;
 370   walk_data.after_dom_children_walk_stmts = NULL;
 371   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 372   walk_data.interesting_blocks = NULL;
 373
 374   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 375
 376   /* This is the main hash table for the dead store elimination pass.  */
 377   dse_gd.stores = BITMAP_ALLOC (NULL);
 378   walk_data.global_data = &dse_gd;
 379
 380   /* Initialize the dominator walker.  */
 381   init_walk_dominator_tree (&walk_data);
 382
 383   /* Recursively walk the dominator tree.  */
 384   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 385
 386   /* Finalize the dominator walker.  */
 387   fini_walk_dominator_tree (&walk_data);
 388
 389   /* Release the main bitmap.  */
 390   BITMAP_FREE (dse_gd.stores);
 391
 392   /* For now, just wipe the post-dominator information.  */
 393   free_dominance_info (CDI_POST_DOMINATORS);
 394 }
 395
 396 static bool
 397 gate_dse (void)
 398 {
 399   return flag_tree_dse != 0;
 400 }
 401
 402 struct tree_opt_pass pass_dse = {
 403   "dse",                        /* name */
 404   gate_dse,                     /* gate */
 405   tree_ssa_dse,                 /* execute */
 406   NULL,                         /* sub */
 407   NULL,                         /* next */
 408   0,                            /* static_pass_number */
 409   TV_TREE_DSE,                  /* tv_id */
 410   PROP_cfg
 411     | PROP_ssa
 412     | PROP_alias,               /* properties_required */
 413   0,                            /* properties_provided */
 414   0,                            /* properties_destroyed */
 415   0,                            /* todo_flags_start */
 416   TODO_dump_func
 417     | TODO_ggc_collect
 418     | TODO_update_ssa
 419     | TODO_verify_ssa,          /* todo_flags_finish */
 420   0                             /* letter */
 421 };