gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004-2015 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "hash-set.h"
  25 #include "machmode.h"
  26 #include "vec.h"
  27 #include "double-int.h"
  28 #include "input.h"
  29 #include "alias.h"
  30 #include "symtab.h"
  31 #include "wide-int.h"
  32 #include "inchash.h"
  33 #include "tree.h"
  34 #include "fold-const.h"
  35 #include "tm_p.h"
  36 #include "predict.h"
  37 #include "hard-reg-set.h"
  38 #include "function.h"
  39 #include "dominance.h"
  40 #include "cfg.h"
  41 #include "basic-block.h"
  42 #include "gimple-pretty-print.h"
  43 #include "bitmap.h"
  44 #include "tree-ssa-alias.h"
  45 #include "internal-fn.h"
  46 #include "gimple-expr.h"
  47 #include "is-a.h"
  48 #include "gimple.h"
  49 #include "gimple-iterator.h"
  50 #include "gimple-ssa.h"
  51 #include "tree-cfg.h"
  52 #include "tree-phinodes.h"
  53 #include "ssa-iterators.h"
  54 #include "stringpool.h"
  55 #include "tree-ssanames.h"
  56 #include "hashtab.h"
  57 #include "rtl.h"
  58 #include "flags.h"
  59 #include "statistics.h"
  60 #include "real.h"
  61 #include "fixed-value.h"
  62 #include "insn-config.h"
  63 #include "expmed.h"
  64 #include "dojump.h"
  65 #include "explow.h"
  66 #include "calls.h"
  67 #include "emit-rtl.h"
  68 #include "varasm.h"
  69 #include "stmt.h"
  70 #include "expr.h"
  71 #include "tree-dfa.h"
  72 #include "tree-pass.h"
  73 #include "domwalk.h"
  74 #include "langhooks.h"
  75 #include "tree-cfgcleanup.h"
  76
  77 /* This file implements dead store elimination.
  78
  79    A dead store is a store into a memory location which will later be
  80    overwritten by another store without any intervening loads.  In this
  81    case the earlier store can be deleted.
  82
  83    In our SSA + virtual operand world we use immediate uses of virtual
  84    operands to detect dead stores.  If a store's virtual definition
  85    is used precisely once by a later store to the same location which
  86    post dominates the first store, then the first store is dead.
  87
  88    The single use of the store's virtual definition ensures that
  89    there are no intervening aliased loads and the requirement that
  90    the second load post dominate the first ensures that if the earlier
  91    store executes, then the later stores will execute before the function
  92    exits.
  93
  94    It may help to think of this as first moving the earlier store to
  95    the point immediately before the later store.  Again, the single
  96    use of the virtual definition and the post-dominance relationship
  97    ensure that such movement would be safe.  Clearly if there are
  98    back to back stores, then the second is redundant.
  99
 100    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
 101    may also help in understanding this code since it discusses the
 102    relationship between dead store and redundant load elimination.  In
 103    fact, they are the same transformation applied to different views of
 104    the CFG.  */
 105
 106
 107 /* Bitmap of blocks that have had EH statements cleaned.  We should
 108    remove their dead edges eventually.  */
 109 static bitmap need_eh_cleanup;
 110
 111
 112 /* A helper of dse_optimize_stmt.
 113    Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
 114    statement *USE_STMT that may prove STMT to be dead.
 115    Return TRUE if the above conditions are met, otherwise FALSE.  */
 116
 117 static bool
 118 dse_possible_dead_store_p (ao_ref *ref, gimple stmt, gimple *use_stmt)
 119 {
 120   gimple temp;
 121   unsigned cnt = 0;
 122
 123   *use_stmt = NULL;
 124
 125   /* Find the first dominated statement that clobbers (part of) the
 126      memory stmt stores to with no intermediate statement that may use
 127      part of the memory stmt stores.  That is, find a store that may
 128      prove stmt to be a dead store.  */
 129   temp = stmt;
 130   do
 131     {
 132       gimple use_stmt, defvar_def;
 133       imm_use_iterator ui;
 134       bool fail = false;
 135       tree defvar;
 136
 137       /* Limit stmt walking to be linear in the number of possibly
 138          dead stores.  */
 139       if (++cnt > 256)
 140         return false;
 141
 142       if (gimple_code (temp) == GIMPLE_PHI)
 143         defvar = PHI_RESULT (temp);
 144       else
 145         defvar = gimple_vdef (temp);
 146       defvar_def = temp;
 147       temp = NULL;
 148       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 149         {
 150           cnt++;
 151
 152           /* If we ever reach our DSE candidate stmt again fail.  We
 153              cannot handle dead stores in loops.  */
 154           if (use_stmt == stmt)
 155             {
 156               fail = true;
 157               BREAK_FROM_IMM_USE_STMT (ui);
 158             }
 159           /* In simple cases we can look through PHI nodes, but we
 160              have to be careful with loops and with memory references
 161              containing operands that are also operands of PHI nodes.
 162              See gcc.c-torture/execute/20051110-*.c.  */
 163           else if (gimple_code (use_stmt) == GIMPLE_PHI)
 164             {
 165               if (temp
 166                   /* Make sure we are not in a loop latch block.  */
 167                   || gimple_bb (stmt) == gimple_bb (use_stmt)
 168                   || dominated_by_p (CDI_DOMINATORS,
 169                                      gimple_bb (stmt), gimple_bb (use_stmt))
 170                   /* We can look through PHIs to regions post-dominating
 171                      the DSE candidate stmt.  */
 172                   || !dominated_by_p (CDI_POST_DOMINATORS,
 173                                       gimple_bb (stmt), gimple_bb (use_stmt)))
 174                 {
 175                   fail = true;
 176                   BREAK_FROM_IMM_USE_STMT (ui);
 177                 }
 178               /* Do not consider the PHI as use if it dominates the
 179                  stmt defining the virtual operand we are processing,
 180                  we have processed it already in this case.  */
 181               if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
 182                   && !dominated_by_p (CDI_DOMINATORS,
 183                                       gimple_bb (defvar_def),
 184                                       gimple_bb (use_stmt)))
 185                 temp = use_stmt;
 186             }
 187           /* If the statement is a use the store is not dead.  */
 188           else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
 189             {
 190               fail = true;
 191               BREAK_FROM_IMM_USE_STMT (ui);
 192             }
 193           /* If this is a store, remember it or bail out if we have
 194              multiple ones (the will be in different CFG parts then).  */
 195           else if (gimple_vdef (use_stmt))
 196             {
 197               if (temp)
 198                 {
 199                   fail = true;
 200                   BREAK_FROM_IMM_USE_STMT (ui);
 201                 }
 202               temp = use_stmt;
 203             }
 204         }
 205
 206       if (fail)
 207         return false;
 208
 209       /* If we didn't find any definition this means the store is dead
 210          if it isn't a store to global reachable memory.  In this case
 211          just pretend the stmt makes itself dead.  Otherwise fail.  */
 212       if (!temp)
 213         {
 214           if (ref_may_alias_global_p (ref))
 215             return false;
 216
 217           temp = stmt;
 218           break;
 219         }
 220     }
 221   /* Continue walking until we reach a kill.  */
 222   while (!stmt_kills_ref_p (temp, ref));
 223
 224   *use_stmt = temp;
 225
 226   return true;
 227 }
 228
 229
 230 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 231
 232    A dead store is a store into a memory location which will later be
 233    overwritten by another store without any intervening loads.  In this
 234    case the earlier store can be deleted.
 235
 236    In our SSA + virtual operand world we use immediate uses of virtual
 237    operands to detect dead stores.  If a store's virtual definition
 238    is used precisely once by a later store to the same location which
 239    post dominates the first store, then the first store is dead.  */
 240
 241 static void
 242 dse_optimize_stmt (gimple_stmt_iterator *gsi)
 243 {
 244   gimple stmt = gsi_stmt (*gsi);
 245
 246   /* If this statement has no virtual defs, then there is nothing
 247      to do.  */
 248   if (!gimple_vdef (stmt))
 249     return;
 250
 251   /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
 252   if (gimple_has_volatile_ops (stmt)
 253       && (!gimple_clobber_p (stmt)
 254           || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
 255     return;
 256
 257   /* We know we have virtual definitions.  We can handle assignments and
 258      some builtin calls.  */
 259   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
 260     {
 261       switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
 262         {
 263           case BUILT_IN_MEMCPY:
 264           case BUILT_IN_MEMMOVE:
 265           case BUILT_IN_MEMSET:
 266             {
 267               gimple use_stmt;
 268               ao_ref ref;
 269               tree size = NULL_TREE;
 270               if (gimple_call_num_args (stmt) == 3)
 271                 size = gimple_call_arg (stmt, 2);
 272               tree ptr = gimple_call_arg (stmt, 0);
 273               ao_ref_init_from_ptr_and_size (&ref, ptr, size);
 274               if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
 275                 return;
 276
 277               if (dump_file && (dump_flags & TDF_DETAILS))
 278                 {
 279                   fprintf (dump_file, "  Deleted dead call '");
 280                   print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
 281                   fprintf (dump_file, "'\n");
 282                 }
 283
 284               tree lhs = gimple_call_lhs (stmt);
 285               if (lhs)
 286                 {
 287                   gimple new_stmt = gimple_build_assign (lhs, ptr);
 288                   unlink_stmt_vdef (stmt);
 289                   if (gsi_replace (gsi, new_stmt, true))
 290                     bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
 291                 }
 292               else
 293                 {
 294                   /* Then we need to fix the operand of the consuming stmt.  */
 295                   unlink_stmt_vdef (stmt);
 296
 297                   /* Remove the dead store.  */
 298                   if (gsi_remove (gsi, true))
 299                     bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
 300                 }
 301               break;
 302             }
 303           default:
 304             return;
 305         }
 306     }
 307
 308   if (is_gimple_assign (stmt))
 309     {
 310       gimple use_stmt;
 311
 312       /* Self-assignments are zombies.  */
 313       if (operand_equal_p (gimple_assign_rhs1 (stmt),
 314                            gimple_assign_lhs (stmt), 0))
 315         use_stmt = stmt;
 316       else
 317         {
 318           ao_ref ref;
 319           ao_ref_init (&ref, gimple_assign_lhs (stmt));
 320           if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
 321             return;
 322         }
 323
 324       /* Now we know that use_stmt kills the LHS of stmt.  */
 325
 326       /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
 327          another clobber stmt.  */
 328       if (gimple_clobber_p (stmt)
 329           && !gimple_clobber_p (use_stmt))
 330         return;
 331
 332       if (dump_file && (dump_flags & TDF_DETAILS))
 333         {
 334           fprintf (dump_file, "  Deleted dead store '");
 335           print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
 336           fprintf (dump_file, "'\n");
 337         }
 338
 339       /* Then we need to fix the operand of the consuming stmt.  */
 340       unlink_stmt_vdef (stmt);
 341
 342       /* Remove the dead store.  */
 343       basic_block bb = gimple_bb (stmt);
 344       if (gsi_remove (gsi, true))
 345         bitmap_set_bit (need_eh_cleanup, bb->index);
 346
 347       /* And release any SSA_NAMEs set in this statement back to the
 348          SSA_NAME manager.  */
 349       release_defs (stmt);
 350     }
 351 }
 352
 353 class dse_dom_walker : public dom_walker
 354 {
 355 public:
 356   dse_dom_walker (cdi_direction direction) : dom_walker (direction) {}
 357
 358   virtual void before_dom_children (basic_block);
 359 };
 360
 361 void
 362 dse_dom_walker::before_dom_children (basic_block bb)
 363 {
 364   gimple_stmt_iterator gsi;
 365
 366   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 367     {
 368       dse_optimize_stmt (&gsi);
 369       if (gsi_end_p (gsi))
 370         gsi = gsi_last_bb (bb);
 371       else
 372         gsi_prev (&gsi);
 373     }
 374 }
 375
 376 namespace {
 377
 378 const pass_data pass_data_dse =
 379 {
 380   GIMPLE_PASS, /* type */
 381   "dse", /* name */
 382   OPTGROUP_NONE, /* optinfo_flags */
 383   TV_TREE_DSE, /* tv_id */
 384   ( PROP_cfg | PROP_ssa ), /* properties_required */
 385   0, /* properties_provided */
 386   0, /* properties_destroyed */
 387   0, /* todo_flags_start */
 388   0, /* todo_flags_finish */
 389 };
 390
 391 class pass_dse : public gimple_opt_pass
 392 {
 393 public:
 394   pass_dse (gcc::context *ctxt)
 395     : gimple_opt_pass (pass_data_dse, ctxt)
 396   {}
 397
 398   /* opt_pass methods: */
 399   opt_pass * clone () { return new pass_dse (m_ctxt); }
 400   virtual bool gate (function *) { return flag_tree_dse != 0; }
 401   virtual unsigned int execute (function *);
 402
 403 }; // class pass_dse
 404
 405 unsigned int
 406 pass_dse::execute (function *fun)
 407 {
 408   need_eh_cleanup = BITMAP_ALLOC (NULL);
 409
 410   renumber_gimple_stmt_uids ();
 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   calculate_dominance_info (CDI_DOMINATORS);
 418
 419   /* Dead store elimination is fundamentally a walk of the post-dominator
 420      tree and a backwards walk of statements within each block.  */
 421   dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
 422
 423   /* Removal of stores may make some EH edges dead.  Purge such edges from
 424      the CFG as needed.  */
 425   if (!bitmap_empty_p (need_eh_cleanup))
 426     {
 427       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 428       cleanup_tree_cfg ();
 429     }
 430
 431   BITMAP_FREE (need_eh_cleanup);
 432
 433   /* For now, just wipe the post-dominator information.  */
 434   free_dominance_info (CDI_POST_DOMINATORS);
 435   return 0;
 436 }
 437
 438 } // anon namespace
 439
 440 gimple_opt_pass *
 441 make_pass_dse (gcc::context *ctxt)
 442 {
 443   return new pass_dse (ctxt);
 444 }