new file mode 100644
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1" } */
+
+int a[2];
+void foo(int i, int k)
+{
+ a[0] = i;
+ if (k)
+ a[0] = a[i] + k;
+ else
+ a[0] = a[i] + 3;
+ a[0] = 0;
+}
+
+/* Only the last store remains. */
+/* { dg-final { scan-tree-dump-times " = " 1 "dse1" } } */
@@ -31,7 +31,6 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-dfa.h"
-#include "domwalk.h"
#include "tree-cfgcleanup.h"
#include "alias.h"
#include "tree-ssa-loop.h"
@@ -40,6 +39,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-fold.h"
#include "gimplify.h"
#include "tree-eh.h"
+#include "cfganal.h"
/* This file implements dead store elimination.
@@ -958,31 +958,6 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
}
-class dse_dom_walker : public dom_walker
-{
-public:
- dse_dom_walker (cdi_direction direction)
- : dom_walker (direction),
- m_live_bytes (param_dse_max_object_size),
- m_byte_tracking_enabled (false),
- m_need_cfg_cleanup (false) {}
-
- virtual edge before_dom_children (basic_block);
- unsigned todo () const;
-
-private:
- auto_sbitmap m_live_bytes;
- bool m_byte_tracking_enabled;
- bool m_need_cfg_cleanup;
- void dse_optimize_stmt (gimple_stmt_iterator *);
-};
-
-unsigned
-dse_dom_walker::todo () const
-{
- return m_need_cfg_cleanup ? TODO_cleanup_cfg : 0;
-}
-
/* Delete a dead call at GSI, which is mem* call of some kind. */
static void
delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type)
@@ -1054,8 +1029,8 @@ delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi, const char *type
is used precisely once by a later store to the same location which
post dominates the first store, then the first store is dead. */
-void
-dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
+static void
+dse_optimize_stmt (gimple_stmt_iterator *gsi, sbitmap live_bytes)
{
gimple *stmt = gsi_stmt (*gsi);
@@ -1104,17 +1079,17 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
dse_optimize_redundant_stores (stmt);
enum dse_store_status store_status;
- m_byte_tracking_enabled
- = setup_live_bytes_from_ref (&ref, m_live_bytes);
+ bool byte_tracking_enabled
+ = setup_live_bytes_from_ref (&ref, live_bytes);
store_status = dse_classify_store (&ref, stmt,
- m_byte_tracking_enabled,
- m_live_bytes);
+ byte_tracking_enabled,
+ live_bytes);
if (store_status == DSE_STORE_LIVE)
return;
if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
{
- maybe_trim_memstar_call (&ref, m_live_bytes, stmt);
+ maybe_trim_memstar_call (&ref, live_bytes, stmt);
return;
}
@@ -1150,18 +1125,18 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
;
else
{
- m_byte_tracking_enabled
- = setup_live_bytes_from_ref (&ref, m_live_bytes);
+ bool byte_tracking_enabled
+ = setup_live_bytes_from_ref (&ref, live_bytes);
enum dse_store_status store_status;
store_status = dse_classify_store (&ref, stmt,
- m_byte_tracking_enabled,
- m_live_bytes, &by_clobber_p);
+ byte_tracking_enabled,
+ live_bytes, &by_clobber_p);
if (store_status == DSE_STORE_LIVE)
return;
if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
{
- maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt);
+ maybe_trim_partially_dead_store (&ref, live_bytes, stmt);
return;
}
}
@@ -1178,64 +1153,6 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
}
}
-edge
-dse_dom_walker::before_dom_children (basic_block bb)
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
- {
- gimple *stmt = gsi_stmt (gsi);
-
- if (gimple_vdef (stmt))
- dse_optimize_stmt (&gsi);
- else if (def_operand_p def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
- {
- /* When we remove dead stores make sure to also delete trivially
- dead SSA defs. */
- if (has_zero_uses (DEF_FROM_PTR (def_p))
- && !gimple_has_side_effects (stmt)
- && !stmt_unremovable_because_of_non_call_eh_p (cfun, stmt))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Deleted trivially dead stmt: ");
- print_gimple_stmt (dump_file, stmt, 0, dump_flags);
- fprintf (dump_file, "\n");
- }
- if (gsi_remove (&gsi, true) && need_eh_cleanup)
- bitmap_set_bit (need_eh_cleanup, bb->index);
- release_defs (stmt);
- }
- }
- if (gsi_end_p (gsi))
- gsi = gsi_last_bb (bb);
- else
- gsi_prev (&gsi);
- }
- bool removed_phi = false;
- for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
- {
- gphi *phi = si.phi ();
- if (has_zero_uses (gimple_phi_result (phi)))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Deleted trivially dead PHI: ");
- print_gimple_stmt (dump_file, phi, 0, dump_flags);
- fprintf (dump_file, "\n");
- }
- remove_phi_node (&si, true);
- removed_phi = true;
- }
- else
- gsi_next (&si);
- }
- if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
- m_need_cfg_cleanup = true;
- return NULL;
-}
-
namespace {
const pass_data pass_data_dse =
@@ -1268,24 +1185,75 @@ public:
unsigned int
pass_dse::execute (function *fun)
{
+ unsigned todo = 0;
need_eh_cleanup = BITMAP_ALLOC (NULL);
+ auto_sbitmap live_bytes (param_dse_max_object_size);
renumber_gimple_stmt_uids (cfun);
- /* We might consider making this a property of each pass so that it
- can be [re]computed on an as-needed basis. Particularly since
- this pass could be seen as an extension of DCE which needs post
- dominators. */
- calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
- /* Dead store elimination is fundamentally a walk of the post-dominator
- tree and a backwards walk of statements within each block. */
- dse_dom_walker walker (CDI_POST_DOMINATORS);
- walker.walk (fun->cfg->x_exit_block_ptr);
- free_dominance_info (CDI_POST_DOMINATORS);
+ /* Dead store elimination is fundamentally a reverse program order walk. */
+ int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
+ int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
+ for (int i = n; i != 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);
+ gimple_stmt_iterator gsi;
- unsigned todo = walker.todo ();
+ for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
+ {
+ gimple *stmt = gsi_stmt (gsi);
+
+ if (gimple_vdef (stmt))
+ dse_optimize_stmt (&gsi, live_bytes);
+ else if (def_operand_p
+ def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
+ {
+ /* When we remove dead stores make sure to also delete trivially
+ dead SSA defs. */
+ if (has_zero_uses (DEF_FROM_PTR (def_p))
+ && !gimple_has_side_effects (stmt)
+ && !stmt_unremovable_because_of_non_call_eh_p (cfun, stmt))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Deleted trivially dead stmt: ");
+ print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+ fprintf (dump_file, "\n");
+ }
+ if (gsi_remove (&gsi, true) && need_eh_cleanup)
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+ release_defs (stmt);
+ }
+ }
+ if (gsi_end_p (gsi))
+ gsi = gsi_last_bb (bb);
+ else
+ gsi_prev (&gsi);
+ }
+ bool removed_phi = false;
+ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
+ {
+ gphi *phi = si.phi ();
+ if (has_zero_uses (gimple_phi_result (phi)))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Deleted trivially dead PHI: ");
+ print_gimple_stmt (dump_file, phi, 0, dump_flags);
+ fprintf (dump_file, "\n");
+ }
+ remove_phi_node (&si, true);
+ removed_phi = true;
+ }
+ else
+ gsi_next (&si);
+ }
+ if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
+ todo |= TODO_cleanup_cfg;
+ }
+ free (rpo);
/* Removal of stores may make some EH edges dead. Purge such edges from
the CFG as needed. */