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