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 defs, 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           tree def;
 255           ssa_op_iter iter;
 256
 257           /* Make sure we propagate the ABNORMAL bit setting.  */
 258           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
 259             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 260           /* Then we need to fix the operand of the consuming stmt.  */
 261           SET_USE (first_use_p, usevar);
 262
 263           if (dump_file && (dump_flags & TDF_DETAILS))
 264             {
 265               fprintf (dump_file, "  Deleted dead store '");
 266               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 267               fprintf (dump_file, "'\n");
 268             }
 269
 270           /* Remove the dead store.  */
 271           bsi_remove (&bsi);
 272
 273           /* The virtual defs for the dead statement will need to be
 274              updated.  Since these names are going to disappear,
 275              FUD chains for uses downstream need to be updated.  */
 276           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 277             mark_sym_for_renaming (SSA_NAME_VAR (def));
 278
 279           /* And release any SSA_NAMEs set in this statement back to the
 280              SSA_NAME manager.  */
 281           release_defs (stmt);
 282         }
 283
 284       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 285     }
 286 }
 287
 288 /* Record that we have seen the PHIs at the start of BB which correspond
 289    to virtual operands.  */
 290 static void
 291 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 292 {
 293   struct dse_block_local_data *bd
 294     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 295   struct dse_global_data *dse_gd = walk_data->global_data;
 296   tree phi;
 297
 298   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 299     if (need_imm_uses_for (PHI_RESULT (phi)))
 300       record_voperand_set (dse_gd->stores,
 301                            &bd->stores,
 302                            get_stmt_uid (phi));
 303 }
 304
 305 static void
 306 dse_finalize_block (struct dom_walk_data *walk_data,
 307                     basic_block bb ATTRIBUTE_UNUSED)
 308 {
 309   struct dse_block_local_data *bd
 310     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 311   struct dse_global_data *dse_gd = walk_data->global_data;
 312   bitmap stores = dse_gd->stores;
 313   unsigned int i;
 314   bitmap_iterator bi;
 315
 316   /* Unwind the stores noted in this basic block.  */
 317   if (bd->stores)
 318     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 319       {
 320         bitmap_clear_bit (stores, i);
 321       }
 322 }
 323
 324 static void
 325 tree_ssa_dse (void)
 326 {
 327   struct dom_walk_data walk_data;
 328   struct dse_global_data dse_gd;
 329   basic_block bb;
 330
 331   /* Create a UID for each statement in the function.  Ordering of the
 332      UIDs is not important for this pass.  */
 333   max_stmt_uid = 0;
 334   FOR_EACH_BB (bb)
 335     {
 336       block_stmt_iterator bsi;
 337
 338       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 339         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 340     }
 341
 342   /* We might consider making this a property of each pass so that it
 343      can be [re]computed on an as-needed basis.  Particularly since
 344      this pass could be seen as an extension of DCE which needs post
 345      dominators.  */
 346   calculate_dominance_info (CDI_POST_DOMINATORS);
 347
 348   /* Dead store elimination is fundamentally a walk of the post-dominator
 349      tree and a backwards walk of statements within each block.  */
 350   walk_data.walk_stmts_backward = true;
 351   walk_data.dom_direction = CDI_POST_DOMINATORS;
 352   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 353   walk_data.before_dom_children_before_stmts = NULL;
 354   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 355   walk_data.before_dom_children_after_stmts = dse_record_phis;
 356   walk_data.after_dom_children_before_stmts = NULL;
 357   walk_data.after_dom_children_walk_stmts = NULL;
 358   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 359   walk_data.interesting_blocks = NULL;
 360
 361   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 362
 363   /* This is the main hash table for the dead store elimination pass.  */
 364   dse_gd.stores = BITMAP_ALLOC (NULL);
 365   walk_data.global_data = &dse_gd;
 366
 367   /* Initialize the dominator walker.  */
 368   init_walk_dominator_tree (&walk_data);
 369
 370   /* Recursively walk the dominator tree.  */
 371   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 372
 373   /* Finalize the dominator walker.  */
 374   fini_walk_dominator_tree (&walk_data);
 375
 376   /* Release the main bitmap.  */
 377   BITMAP_FREE (dse_gd.stores);
 378
 379   /* For now, just wipe the post-dominator information.  */
 380   free_dominance_info (CDI_POST_DOMINATORS);
 381 }
 382
 383 static bool
 384 gate_dse (void)
 385 {
 386   return flag_tree_dse != 0;
 387 }
 388
 389 struct tree_opt_pass pass_dse = {
 390   "dse",                        /* name */
 391   gate_dse,                     /* gate */
 392   tree_ssa_dse,                 /* execute */
 393   NULL,                         /* sub */
 394   NULL,                         /* next */
 395   0,                            /* static_pass_number */
 396   TV_TREE_DSE,                  /* tv_id */
 397   PROP_cfg
 398     | PROP_ssa
 399     | PROP_alias,               /* properties_required */
 400   0,                            /* properties_provided */
 401   0,                            /* properties_destroyed */
 402   0,                            /* todo_flags_start */
 403   TODO_dump_func
 404     | TODO_ggc_collect
 405     | TODO_update_ssa
 406     | TODO_verify_ssa,          /* todo_flags_finish */
 407   0                             /* letter */
 408 };