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