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   v_may_defs = V_MAY_DEF_OPS (ann);
 182
 183   /* If this statement has no virtual defs, then there is nothing
 184      to do.  */
 185   if (NUM_V_MAY_DEFS (v_may_defs) == 0)
 186     return;
 187
 188   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
 189      not also a function call, then record it into our table.  */
 190   if (get_call_expr_in (stmt))
 191     return;
 192
 193   if (ann->has_volatile_ops)
 194     return;
 195
 196   if (TREE_CODE (stmt) == MODIFY_EXPR)
 197     {
 198       unsigned int num_uses = 0, count = 0;
 199       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 200       use_operand_p use_p;
 201       tree use, use_stmt;
 202       tree defvar = NULL_TREE, usevar = NULL_TREE;
 203       use_operand_p var2;
 204       def_operand_p var1;
 205       ssa_op_iter op_iter;
 206
 207       FOR_EACH_SSA_MAYDEF_OPERAND (var1, var2, stmt, op_iter)
 208         {
 209           defvar = DEF_FROM_PTR (var1);
 210           usevar = USE_FROM_PTR (var2);
 211           num_uses += num_imm_uses (defvar);
 212           count++;
 213           if (num_uses > 1 || count > 1)
 214             break;
 215         }
 216
 217       if (count == 1 && num_uses == 1)
 218         {
 219           single_imm_use (defvar, &use_p, &use_stmt);
 220           gcc_assert (use_p != NULL_USE_OPERAND_P);
 221           first_use_p = use_p;
 222           use = USE_FROM_PTR (use_p);
 223         }
 224       else
 225         {
 226           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 227           return;
 228         }
 229
 230       /* Skip through any PHI nodes we have already seen if the PHI
 231          represents the only use of this store.
 232
 233          Note this does not handle the case where the store has
 234          multiple V_MAY_DEFs which all reach a set of PHI nodes in the
 235          same block.  */
 236       while (use_p != NULL_USE_OPERAND_P
 237              && TREE_CODE (use_stmt) == PHI_NODE
 238              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
 239         {
 240           /* Skip past this PHI and loop again in case we had a PHI
 241              chain.  */
 242           if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
 243             use = USE_FROM_PTR (use_p);
 244         }
 245
 246       /* If we have precisely one immediate use at this point, then we may
 247          have found redundant store.  */
 248       if (use_p != NULL_USE_OPERAND_P
 249           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 250           && operand_equal_p (TREE_OPERAND (stmt, 0),
 251                               TREE_OPERAND (use_stmt, 0), 0))
 252         {
 253           tree def;
 254           ssa_op_iter iter;
 255
 256           /* Make sure we propagate the ABNORMAL bit setting.  */
 257           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
 258             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 259           /* Then we need to fix the operand of the consuming stmt.  */
 260           SET_USE (first_use_p, usevar);
 261
 262           if (dump_file && (dump_flags & TDF_DETAILS))
 263             {
 264               fprintf (dump_file, "  Deleted dead store '");
 265               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 266               fprintf (dump_file, "'\n");
 267             }
 268
 269           /* Remove the dead store.  */
 270           bsi_remove (&bsi);
 271
 272           /* The virtual defs for the dead statement will need to be
 273              updated.  Since these names are going to disappear,
 274              FUD chains for uses downstream need to be updated.  */
 275           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 276             mark_sym_for_renaming (SSA_NAME_VAR (def));
 277
 278           /* And release any SSA_NAMEs set in this statement back to the
 279              SSA_NAME manager.  */
 280           release_defs (stmt);
 281         }
 282
 283       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 284     }
 285 }
 286
 287 /* Record that we have seen the PHIs at the start of BB which correspond
 288    to virtual operands.  */
 289 static void
 290 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 291 {
 292   struct dse_block_local_data *bd
 293     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 294   struct dse_global_data *dse_gd = walk_data->global_data;
 295   tree phi;
 296
 297   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 298     if (need_imm_uses_for (PHI_RESULT (phi)))
 299       record_voperand_set (dse_gd->stores,
 300                            &bd->stores,
 301                            get_stmt_uid (phi));
 302 }
 303
 304 static void
 305 dse_finalize_block (struct dom_walk_data *walk_data,
 306                     basic_block bb ATTRIBUTE_UNUSED)
 307 {
 308   struct dse_block_local_data *bd
 309     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 310   struct dse_global_data *dse_gd = walk_data->global_data;
 311   bitmap stores = dse_gd->stores;
 312   unsigned int i;
 313   bitmap_iterator bi;
 314
 315   /* Unwind the stores noted in this basic block.  */
 316   if (bd->stores)
 317     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 318       {
 319         bitmap_clear_bit (stores, i);
 320       }
 321 }
 322
 323 static void
 324 tree_ssa_dse (void)
 325 {
 326   struct dom_walk_data walk_data;
 327   struct dse_global_data dse_gd;
 328   basic_block bb;
 329
 330   /* Create a UID for each statement in the function.  Ordering of the
 331      UIDs is not important for this pass.  */
 332   max_stmt_uid = 0;
 333   FOR_EACH_BB (bb)
 334     {
 335       block_stmt_iterator bsi;
 336
 337       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 338         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 339     }
 340
 341   /* We might consider making this a property of each pass so that it
 342      can be [re]computed on an as-needed basis.  Particularly since
 343      this pass could be seen as an extension of DCE which needs post
 344      dominators.  */
 345   calculate_dominance_info (CDI_POST_DOMINATORS);
 346
 347   /* Dead store elimination is fundamentally a walk of the post-dominator
 348      tree and a backwards walk of statements within each block.  */
 349   walk_data.walk_stmts_backward = true;
 350   walk_data.dom_direction = CDI_POST_DOMINATORS;
 351   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 352   walk_data.before_dom_children_before_stmts = NULL;
 353   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 354   walk_data.before_dom_children_after_stmts = dse_record_phis;
 355   walk_data.after_dom_children_before_stmts = NULL;
 356   walk_data.after_dom_children_walk_stmts = NULL;
 357   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 358   walk_data.interesting_blocks = NULL;
 359
 360   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 361
 362   /* This is the main hash table for the dead store elimination pass.  */
 363   dse_gd.stores = BITMAP_ALLOC (NULL);
 364   walk_data.global_data = &dse_gd;
 365
 366   /* Initialize the dominator walker.  */
 367   init_walk_dominator_tree (&walk_data);
 368
 369   /* Recursively walk the dominator tree.  */
 370   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 371
 372   /* Finalize the dominator walker.  */
 373   fini_walk_dominator_tree (&walk_data);
 374
 375   /* Release the main bitmap.  */
 376   BITMAP_FREE (dse_gd.stores);
 377
 378   /* For now, just wipe the post-dominator information.  */
 379   free_dominance_info (CDI_POST_DOMINATORS);
 380 }
 381
 382 static bool
 383 gate_dse (void)
 384 {
 385   return flag_tree_dse != 0;
 386 }
 387
 388 struct tree_opt_pass pass_dse = {
 389   "dse",                        /* name */
 390   gate_dse,                     /* gate */
 391   tree_ssa_dse,                 /* execute */
 392   NULL,                         /* sub */
 393   NULL,                         /* next */
 394   0,                            /* static_pass_number */
 395   TV_TREE_DSE,                  /* tv_id */
 396   PROP_cfg
 397     | PROP_ssa
 398     | PROP_alias,               /* properties_required */
 399   0,                            /* properties_provided */
 400   0,                            /* properties_destroyed */
 401   0,                            /* todo_flags_start */
 402   TODO_dump_func
 403     | TODO_ggc_collect
 404     | TODO_update_ssa
 405     | TODO_verify_ssa,          /* todo_flags_finish */
 406   0                             /* letter */
 407 };