gcc/tree-ssa-dse.c

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