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