gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004 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 fix_phi_uses (tree, tree);
  98 static void fix_stmt_v_may_defs (tree, tree);
  99 static void record_voperand_set (bitmap, bitmap *, unsigned int);
 100
 101 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 102                                    nodes are assigned using the versions of
 103                                    ssa names they define.  */
 104
 105 /* Returns uid of statement STMT.  */
 106
 107 static unsigned
 108 get_stmt_uid (tree stmt)
 109 {
 110   if (TREE_CODE (stmt) == PHI_NODE)
 111     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 112
 113   return stmt_ann (stmt)->uid;
 114 }
 115
 116 /* Function indicating whether we ought to include information for 'var'
 117    when calculating immediate uses.  For this pass we only want use
 118    information for virtual variables.  */
 119
 120 static bool
 121 need_imm_uses_for (tree var)
 122 {
 123   return !is_gimple_reg (var);
 124 }
 125
 126
 127 /* Replace uses in PHI which match V_MAY_DEF_RESULTs in STMT with the
 128    corresponding V_MAY_DEF_OP in STMT.  */
 129
 130 static void
 131 fix_phi_uses (tree phi, tree stmt)
 132 {
 133   stmt_ann_t ann = stmt_ann (stmt);
 134   v_may_def_optype v_may_defs;
 135   unsigned int i;
 136   int j;
 137
 138   get_stmt_operands (stmt);
 139   v_may_defs = V_MAY_DEF_OPS (ann);
 140
 141   /* Walk each V_MAY_DEF in STMT.  */
 142   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 143     {
 144       tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
 145
 146       /* Find any uses in the PHI which match V_MAY_DEF and replace
 147          them with the appropriate V_MAY_DEF_OP.  */
 148       for (j = 0; j < PHI_NUM_ARGS (phi); j++)
 149         if (v_may_def == PHI_ARG_DEF (phi, j))
 150           SET_PHI_ARG_DEF (phi, j, V_MAY_DEF_OP (v_may_defs, i));
 151     }
 152 }
 153
 154 /* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs
 155    in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2.  */
 156
 157 static void
 158 fix_stmt_v_may_defs (tree stmt1, tree stmt2)
 159 {
 160   stmt_ann_t ann1 = stmt_ann (stmt1);
 161   stmt_ann_t ann2 = stmt_ann (stmt2);
 162   v_may_def_optype v_may_defs1;
 163   v_may_def_optype v_may_defs2;
 164   unsigned int i, j;
 165
 166   get_stmt_operands (stmt1);
 167   get_stmt_operands (stmt2);
 168   v_may_defs1 = V_MAY_DEF_OPS (ann1);
 169   v_may_defs2 = V_MAY_DEF_OPS (ann2);
 170
 171   /* Walk each V_MAY_DEF_OP in stmt1.  */
 172   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs1); i++)
 173     {
 174       tree v_may_def1 = V_MAY_DEF_OP (v_may_defs1, i);
 175
 176       /* Find the appropriate V_MAY_DEF_RESULT in STMT2.  */
 177       for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs2); j++)
 178         {
 179           if (v_may_def1 == V_MAY_DEF_RESULT (v_may_defs2, j))
 180             {
 181               /* Update.  */
 182               SET_V_MAY_DEF_OP (v_may_defs1, i, V_MAY_DEF_OP (v_may_defs2, j));
 183               break;
 184             }
 185         }
 186
 187       /* If we did not find a corresponding V_MAY_DEF_RESULT, then something
 188          has gone terribly wrong.  */
 189       gcc_assert (j != NUM_V_MAY_DEFS (v_may_defs2));
 190     }
 191 }
 192
 193
 194 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 195 static void
 196 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 197 {
 198   /* Lazily allocate the bitmap.  Note that we do not get a notification
 199      when the block local data structures die, so we allocate the local
 200      bitmap backed by the GC system.  */
 201   if (*local == NULL)
 202     *local = BITMAP_GGC_ALLOC ();
 203
 204   /* Set the bit in the local and global bitmaps.  */
 205   bitmap_set_bit (*local, uid);
 206   bitmap_set_bit (global, uid);
 207 }
 208 /* Initialize block local data structures.  */
 209
 210 static void
 211 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 212                                  basic_block bb ATTRIBUTE_UNUSED,
 213                                  bool recycled)
 214 {
 215   struct dse_block_local_data *bd
 216     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 217
 218   /* If we are given a recycled block local data structure, ensure any
 219      bitmap associated with the block is cleared.  */
 220   if (recycled)
 221     {
 222       if (bd->stores)
 223         bitmap_clear (bd->stores);
 224     }
 225 }
 226
 227 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 228
 229    A dead store is a store into a memory location which will later be
 230    overwritten by another store without any intervening loads.  In this
 231    case the earlier store can be deleted.
 232
 233    In our SSA + virtual operand world we use immediate uses of virtual
 234    operands to detect dead stores.  If a store's virtual definition
 235    is used precisely once by a later store to the same location which
 236    post dominates the first store, then the first store is dead.  */
 237
 238 static void
 239 dse_optimize_stmt (struct dom_walk_data *walk_data,
 240                    basic_block bb ATTRIBUTE_UNUSED,
 241                    block_stmt_iterator bsi)
 242 {
 243   struct dse_block_local_data *bd
 244     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 245   struct dse_global_data *dse_gd = walk_data->global_data;
 246   tree stmt = bsi_stmt (bsi);
 247   stmt_ann_t ann = stmt_ann (stmt);
 248   v_may_def_optype v_may_defs;
 249
 250   get_stmt_operands (stmt);
 251   v_may_defs = V_MAY_DEF_OPS (ann);
 252
 253   /* If this statement has no virtual uses, then there is nothing
 254      to do.  */
 255   if (NUM_V_MAY_DEFS (v_may_defs) == 0)
 256     return;
 257
 258   /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
 259      not also a function call, then record it into our table.  */
 260   if (get_call_expr_in (stmt))
 261     return;
 262   if (TREE_CODE (stmt) == MODIFY_EXPR)
 263     {
 264       dataflow_t df = get_immediate_uses (stmt);
 265       unsigned int num_uses = num_immediate_uses (df);
 266       tree use;
 267       tree skipped_phi;
 268
 269
 270       /* If there are no uses then there is nothing left to do.  */
 271       if (num_uses == 0)
 272         {
 273           record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 274           return;
 275         }
 276
 277       use = immediate_use (df, 0);
 278       skipped_phi = NULL;
 279
 280       /* Skip through any PHI nodes we have already seen if the PHI
 281          represents the only use of this store.
 282
 283          Note this does not handle the case where the store has
 284          multiple V_MAY_DEFs which all reach a set of PHI nodes in the
 285          same block.  */
 286       while (num_uses == 1
 287              && TREE_CODE (use) == PHI_NODE
 288              && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use)))
 289         {
 290           /* Record the first PHI we skip so that we can fix its
 291              uses if we find that STMT is a dead store.  */
 292           if (!skipped_phi)
 293             skipped_phi = use;
 294
 295           /* Skip past this PHI and loop again in case we had a PHI
 296              chain.  */
 297           df = get_immediate_uses (use);
 298           num_uses = num_immediate_uses (df);
 299           use = immediate_use (df, 0);
 300         }
 301
 302       /* If we have precisely one immediate use at this point, then we may
 303          have found redundant store.  */
 304       if (num_uses == 1
 305           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use))
 306           && operand_equal_p (TREE_OPERAND (stmt, 0),
 307                               TREE_OPERAND (use, 0), 0))
 308         {
 309           /* We need to fix the operands if either the first PHI we
 310              skipped, or the store which we are not deleting if we did
 311              not skip any PHIs.  */
 312           if (skipped_phi)
 313             fix_phi_uses (skipped_phi, stmt);
 314           else
 315             fix_stmt_v_may_defs (use, stmt);
 316
 317           if (dump_file && (dump_flags & TDF_DETAILS))
 318             {
 319               fprintf (dump_file, "  Deleted dead store '");
 320               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 321               fprintf (dump_file, "'\n");
 322             }
 323
 324           /* Any immediate uses which reference STMT need to instead
 325              reference the new consumer, either SKIPPED_PHI or USE.
 326              This allows us to cascade dead stores.  */
 327           redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);
 328
 329           /* Finally remove the dead store.  */
 330           bsi_remove (&bsi);
 331         }
 332
 333       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 334     }
 335 }
 336
 337 /* Record that we have seen the PHIs at the start of BB which correspond
 338    to virtual operands.  */
 339 static void
 340 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 341 {
 342   struct dse_block_local_data *bd
 343     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 344   struct dse_global_data *dse_gd = walk_data->global_data;
 345   tree phi;
 346
 347   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 348     if (need_imm_uses_for (PHI_RESULT (phi)))
 349       record_voperand_set (dse_gd->stores,
 350                            &bd->stores,
 351                            get_stmt_uid (phi));
 352 }
 353
 354 static void
 355 dse_finalize_block (struct dom_walk_data *walk_data,
 356                     basic_block bb ATTRIBUTE_UNUSED)
 357 {
 358   struct dse_block_local_data *bd
 359     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 360   struct dse_global_data *dse_gd = walk_data->global_data;
 361   bitmap stores = dse_gd->stores;
 362   unsigned int i;
 363
 364   /* Unwind the stores noted in this basic block.  */
 365   if (bd->stores)
 366     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bitmap_clear_bit (stores, i););
 367 }
 368
 369 static void
 370 tree_ssa_dse (void)
 371 {
 372   struct dom_walk_data walk_data;
 373   struct dse_global_data dse_gd;
 374   basic_block bb;
 375
 376   /* Create a UID for each statement in the function.  Ordering of the
 377      UIDs is not important for this pass.  */
 378   max_stmt_uid = 0;
 379   FOR_EACH_BB (bb)
 380     {
 381       block_stmt_iterator bsi;
 382
 383       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 384         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 385     }
 386
 387   /* We might consider making this a property of each pass so that it
 388      can be [re]computed on an as-needed basis.  Particularly since
 389      this pass could be seen as an extension of DCE which needs post
 390      dominators.  */
 391   calculate_dominance_info (CDI_POST_DOMINATORS);
 392
 393   /* We also need immediate use information for virtual operands.  */
 394   compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
 395
 396   /* Dead store elimination is fundamentally a walk of the post-dominator
 397      tree and a backwards walk of statements within each block.  */
 398   walk_data.walk_stmts_backward = true;
 399   walk_data.dom_direction = CDI_POST_DOMINATORS;
 400   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 401   walk_data.before_dom_children_before_stmts = NULL;
 402   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 403   walk_data.before_dom_children_after_stmts = dse_record_phis;
 404   walk_data.after_dom_children_before_stmts = NULL;
 405   walk_data.after_dom_children_walk_stmts = NULL;
 406   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 407
 408   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 409
 410   /* This is the main hash table for the dead store elimination pass.  */
 411   dse_gd.stores = BITMAP_XMALLOC ();
 412   walk_data.global_data = &dse_gd;
 413
 414   /* Initialize the dominator walker.  */
 415   init_walk_dominator_tree (&walk_data);
 416
 417   /* Recursively walk the dominator tree.  */
 418   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 419
 420   /* Finalize the dominator walker.  */
 421   fini_walk_dominator_tree (&walk_data);
 422
 423   /* Release the main bitmap.  */
 424   BITMAP_XFREE (dse_gd.stores);
 425
 426   /* Free dataflow information.  It's probably out of date now anyway.  */
 427   free_df ();
 428
 429   /* For now, just wipe the post-dominator information.  */
 430   free_dominance_info (CDI_POST_DOMINATORS);
 431 }
 432
 433 static bool
 434 gate_dse (void)
 435 {
 436   return flag_tree_dse != 0;
 437 }
 438
 439 struct tree_opt_pass pass_dse = {
 440   "dse",                        /* name */
 441   gate_dse,                     /* gate */
 442   tree_ssa_dse,                 /* execute */
 443   NULL,                         /* sub */
 444   NULL,                         /* next */
 445   0,                            /* static_pass_number */
 446   TV_TREE_DSE,                  /* tv_id */
 447   PROP_cfg | PROP_ssa
 448     | PROP_alias,               /* properties_required */
 449   0,                            /* properties_provided */
 450   0,                            /* properties_destroyed */
 451   0,                            /* todo_flags_start */
 452   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 453   | TODO_verify_ssa,
 454   0                                     /* letter */
 455 };