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           /* Be sure to remove any dataflow information attached to
 330              this statement.  */
 331           free_df_for_stmt (stmt);
 332
 333           /* And release any SSA_NAMEs set in this statement back to the
 334              SSA_NAME manager.  */
 335           release_defs (stmt);
 336
 337           /* Finally remove the dead store.  */
 338           bsi_remove (&bsi);
 339         }
 340
 341       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 342     }
 343 }
 344
 345 /* Record that we have seen the PHIs at the start of BB which correspond
 346    to virtual operands.  */
 347 static void
 348 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 349 {
 350   struct dse_block_local_data *bd
 351     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 352   struct dse_global_data *dse_gd = walk_data->global_data;
 353   tree phi;
 354
 355   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 356     if (need_imm_uses_for (PHI_RESULT (phi)))
 357       record_voperand_set (dse_gd->stores,
 358                            &bd->stores,
 359                            get_stmt_uid (phi));
 360 }
 361
 362 static void
 363 dse_finalize_block (struct dom_walk_data *walk_data,
 364                     basic_block bb ATTRIBUTE_UNUSED)
 365 {
 366   struct dse_block_local_data *bd
 367     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 368   struct dse_global_data *dse_gd = walk_data->global_data;
 369   bitmap stores = dse_gd->stores;
 370   unsigned int i;
 371   bitmap_iterator bi;
 372
 373   /* Unwind the stores noted in this basic block.  */
 374   if (bd->stores)
 375     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 376       {
 377         bitmap_clear_bit (stores, i);
 378       }
 379 }
 380
 381 static void
 382 tree_ssa_dse (void)
 383 {
 384   struct dom_walk_data walk_data;
 385   struct dse_global_data dse_gd;
 386   basic_block bb;
 387
 388   /* Create a UID for each statement in the function.  Ordering of the
 389      UIDs is not important for this pass.  */
 390   max_stmt_uid = 0;
 391   FOR_EACH_BB (bb)
 392     {
 393       block_stmt_iterator bsi;
 394
 395       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 396         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
 397     }
 398
 399   /* We might consider making this a property of each pass so that it
 400      can be [re]computed on an as-needed basis.  Particularly since
 401      this pass could be seen as an extension of DCE which needs post
 402      dominators.  */
 403   calculate_dominance_info (CDI_POST_DOMINATORS);
 404
 405   /* We also need immediate use information for virtual operands.  */
 406   compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
 407
 408   /* Dead store elimination is fundamentally a walk of the post-dominator
 409      tree and a backwards walk of statements within each block.  */
 410   walk_data.walk_stmts_backward = true;
 411   walk_data.dom_direction = CDI_POST_DOMINATORS;
 412   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 413   walk_data.before_dom_children_before_stmts = NULL;
 414   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 415   walk_data.before_dom_children_after_stmts = dse_record_phis;
 416   walk_data.after_dom_children_before_stmts = NULL;
 417   walk_data.after_dom_children_walk_stmts = NULL;
 418   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 419
 420   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 421
 422   /* This is the main hash table for the dead store elimination pass.  */
 423   dse_gd.stores = BITMAP_XMALLOC ();
 424   walk_data.global_data = &dse_gd;
 425
 426   /* Initialize the dominator walker.  */
 427   init_walk_dominator_tree (&walk_data);
 428
 429   /* Recursively walk the dominator tree.  */
 430   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 431
 432   /* Finalize the dominator walker.  */
 433   fini_walk_dominator_tree (&walk_data);
 434
 435   /* Release the main bitmap.  */
 436   BITMAP_XFREE (dse_gd.stores);
 437
 438   /* Free dataflow information.  It's probably out of date now anyway.  */
 439   free_df ();
 440
 441   /* For now, just wipe the post-dominator information.  */
 442   free_dominance_info (CDI_POST_DOMINATORS);
 443 }
 444
 445 static bool
 446 gate_dse (void)
 447 {
 448   return flag_tree_dse != 0;
 449 }
 450
 451 struct tree_opt_pass pass_dse = {
 452   "dse",                        /* name */
 453   gate_dse,                     /* gate */
 454   tree_ssa_dse,                 /* execute */
 455   NULL,                         /* sub */
 456   NULL,                         /* next */
 457   0,                            /* static_pass_number */
 458   TV_TREE_DSE,                  /* tv_id */
 459   PROP_cfg | PROP_ssa
 460     | PROP_alias,               /* properties_required */
 461   0,                            /* properties_provided */
 462   0,                            /* properties_destroyed */
 463   0,                            /* todo_flags_start */
 464   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 465   | TODO_verify_ssa,
 466   0                                     /* letter */
 467 };