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 /* Function indicating whether we ought to include information for 'var'
 115    when calculating immediate uses.  For this pass we only want use
 116    information for virtual variables.  */
 117
 118 static bool
 119 need_imm_uses_for (tree var)
 120 {
 121   return !is_gimple_reg (var);
 122 }
 123
 124
 125 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 126 static void
 127 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 128 {
 129   /* Lazily allocate the bitmap.  Note that we do not get a notification
 130      when the block local data structures die, so we allocate the local
 131      bitmap backed by the GC system.  */
 132   if (*local == NULL)
 133     *local = BITMAP_GGC_ALLOC ();
 134
 135   /* Set the bit in the local and global bitmaps.  */
 136   bitmap_set_bit (*local, uid);
 137   bitmap_set_bit (global, uid);
 138 }
 139 /* Initialize block local data structures.  */
 140
 141 static void
 142 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 143                                  basic_block bb ATTRIBUTE_UNUSED,
 144                                  bool recycled)
 145 {
 146   struct dse_block_local_data *bd
 147     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 148
 149   /* If we are given a recycled block local data structure, ensure any
 150      bitmap associated with the block is cleared.  */
 151   if (recycled)
 152     {
 153       if (bd->stores)
 154         bitmap_clear (bd->stores);
 155     }
 156 }
 157
 158 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 159
 160    A dead store is a store into a memory location which will later be
 161    overwritten by another store without any intervening loads.  In this
 162    case the earlier store can be deleted.
 163
 164    In our SSA + virtual operand world we use immediate uses of virtual
 165    operands to detect dead stores.  If a store's virtual definition
 166    is used precisely once by a later store to the same location which
 167    post dominates the first store, then the first store is dead.  */
 168
 169 static void
 170 dse_optimize_stmt (struct dom_walk_data *walk_data,
 171                    basic_block bb ATTRIBUTE_UNUSED,
 172                    block_stmt_iterator bsi)
 173 {
 174   struct dse_block_local_data *bd
 175     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 176   struct dse_global_data *dse_gd = walk_data->global_data;
 177   tree stmt = bsi_stmt (bsi);
 178   stmt_ann_t ann = stmt_ann (stmt);
 179   v_may_def_optype v_may_defs;
 180
 181   get_stmt_operands (stmt);
 182   v_may_defs = V_MAY_DEF_OPS (ann);
 183
 184   /* If this statement has no virtual uses, then there is nothing
 185      to do.  */
 186   if (NUM_V_MAY_DEFS (v_may_defs) == 0)
 187     return;
 188
 189   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
 190      not also a function call, then record it into our table.  */
 191   if (get_call_expr_in (stmt))
 192     return;
 193
 194   if (ann->has_volatile_ops)
 195     return;
 196
 197   if (TREE_CODE (stmt) == MODIFY_EXPR)
 198     {
 199       unsigned int num_uses = 0, count = 0;
 200       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 201       use_operand_p use_p;
 202       tree use, use_stmt;
 203       tree defvar = NULL_TREE, usevar = NULL_TREE;
 204       use_operand_p var2;
 205       def_operand_p var1;
 206       ssa_op_iter op_iter;
 207
 208       FOR_EACH_SSA_MAYDEF_OPERAND (var1, var2, stmt, op_iter)
 209         {
 210           defvar = DEF_FROM_PTR (var1);
 211           usevar = USE_FROM_PTR (var2);
 212           num_uses += num_imm_uses (defvar);
 213           count++;
 214           if (num_uses > 1 || count > 1)
 215             break;
 216         }
 217
 218       if (count == 1 && num_uses == 1)
 219         {
 220           single_imm_use (defvar, &use_p, &use_stmt);
 221           gcc_assert (use_p != NULL_USE_OPERAND_P);
 222           first_use_p = use_p;
 223           use = USE_FROM_PTR (use_p);
 224         }
 225       else
 226         {
 227           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 228           return;
 229         }
 230
 231       /* Skip through any PHI nodes we have already seen if the PHI
 232          represents the only use of this store.
 233
 234          Note this does not handle the case where the store has
 235          multiple V_MAY_DEFs which all reach a set of PHI nodes in the
 236          same block.  */
 237       while (use_p != NULL_USE_OPERAND_P
 238              && TREE_CODE (use_stmt) == PHI_NODE
 239              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
 240         {
 241           /* Skip past this PHI and loop again in case we had a PHI
 242              chain.  */
 243           if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
 244             use = USE_FROM_PTR (use_p);
 245         }
 246
 247       /* If we have precisely one immediate use at this point, then we may
 248          have found redundant store.  */
 249       if (use_p != NULL_USE_OPERAND_P
 250           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 251           && operand_equal_p (TREE_OPERAND (stmt, 0),
 252                               TREE_OPERAND (use_stmt, 0), 0))
 253         {
 254           /* Make sure we propagate the ABNORMAL bit setting.  */
 255           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
 256             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 257           /* Then we need to fix the operand of the consuming stmt.  */
 258           SET_USE (first_use_p, usevar);
 259
 260           if (dump_file && (dump_flags & TDF_DETAILS))
 261             {
 262               fprintf (dump_file, "  Deleted dead store '");
 263               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 264               fprintf (dump_file, "'\n");
 265             }
 266
 267           /* Remove the dead store.  */
 268           bsi_remove (&bsi);
 269
 270           /* And release any SSA_NAMEs set in this statement back to the
 271              SSA_NAME manager.  */
 272           release_defs (stmt);
 273         }
 274
 275       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 276     }
 277 }
 278
 279 /* Record that we have seen the PHIs at the start of BB which correspond
 280    to virtual operands.  */
 281 static void
 282 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 283 {
 284   struct dse_block_local_data *bd
 285     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 286   struct dse_global_data *dse_gd = walk_data->global_data;
 287   tree phi;
 288
 289   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 290     if (need_imm_uses_for (PHI_RESULT (phi)))
 291       record_voperand_set (dse_gd->stores,
 292                            &bd->stores,
 293                            get_stmt_uid (phi));
 294 }
 295
 296 static void
 297 dse_finalize_block (struct dom_walk_data *walk_data,
 298                     basic_block bb ATTRIBUTE_UNUSED)
 299 {
 300   struct dse_block_local_data *bd
 301     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 302   struct dse_global_data *dse_gd = walk_data->global_data;
 303   bitmap stores = dse_gd->stores;
 304   unsigned int i;
 305   bitmap_iterator bi;
 306
 307   /* Unwind the stores noted in this basic block.  */
 308   if (bd->stores)
 309     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 310       {
 311         bitmap_clear_bit (stores, i);
 312       }
 313 }
 314
 315 static void
 316 tree_ssa_dse (void)
 317 {
 318   struct dom_walk_data walk_data;
 319   struct dse_global_data dse_gd;
 320   basic_block bb;
 321
 322   /* Create a UID for each statement in the function.  Ordering of the
 323      UIDs is not important for this pass.  */
 324   max_stmt_uid = 0;
 325   FOR_EACH_BB (bb)
 326     {
 327       block_stmt_iterator bsi;
 328
 329       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 330         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 331     }
 332
 333   /* We might consider making this a property of each pass so that it
 334      can be [re]computed on an as-needed basis.  Particularly since
 335      this pass could be seen as an extension of DCE which needs post
 336      dominators.  */
 337   calculate_dominance_info (CDI_POST_DOMINATORS);
 338
 339   /* Dead store elimination is fundamentally a walk of the post-dominator
 340      tree and a backwards walk of statements within each block.  */
 341   walk_data.walk_stmts_backward = true;
 342   walk_data.dom_direction = CDI_POST_DOMINATORS;
 343   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 344   walk_data.before_dom_children_before_stmts = NULL;
 345   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 346   walk_data.before_dom_children_after_stmts = dse_record_phis;
 347   walk_data.after_dom_children_before_stmts = NULL;
 348   walk_data.after_dom_children_walk_stmts = NULL;
 349   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 350
 351   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 352
 353   /* This is the main hash table for the dead store elimination pass.  */
 354   dse_gd.stores = BITMAP_ALLOC (NULL);
 355   walk_data.global_data = &dse_gd;
 356
 357   /* Initialize the dominator walker.  */
 358   init_walk_dominator_tree (&walk_data);
 359
 360   /* Recursively walk the dominator tree.  */
 361   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 362
 363   /* Finalize the dominator walker.  */
 364   fini_walk_dominator_tree (&walk_data);
 365
 366   /* Release the main bitmap.  */
 367   BITMAP_FREE (dse_gd.stores);
 368
 369   /* For now, just wipe the post-dominator information.  */
 370   free_dominance_info (CDI_POST_DOMINATORS);
 371 }
 372
 373 static bool
 374 gate_dse (void)
 375 {
 376   return flag_tree_dse != 0;
 377 }
 378
 379 struct tree_opt_pass pass_dse = {
 380   "dse",                        /* name */
 381   gate_dse,                     /* gate */
 382   tree_ssa_dse,                 /* execute */
 383   NULL,                         /* sub */
 384   NULL,                         /* next */
 385   0,                            /* static_pass_number */
 386   TV_TREE_DSE,                  /* tv_id */
 387   PROP_cfg | PROP_ssa
 388     | PROP_alias,               /* properties_required */
 389   0,                            /* properties_provided */
 390   0,                            /* properties_destroyed */
 391   0,                            /* todo_flags_start */
 392   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 393   | TODO_verify_ssa,
 394   0                                     /* letter */
 395 };