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