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