The following changes the post-dominator domwalk done by GIMPLE DSE to a reverse program order walk. This enables 2% more stmts do be DSEd during bootstrap and in particular for testcases like the one added where it is important to visit post dominators in a particular order.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. 2021-05-03 Richard Biener <rguent...@suse.de> * tree-ssa-dse.c: Do not include domwalk.h but cfganal.h. (dse_dom_walker): Remove. (dse_dom_walker::dse_optimize_stmt): Rename... (dse_optimize_stmt): ... to this, pass in live_bytes sbitmap. (dse_dom_walker::before_dom_children): Inline ... (pass_dse::execute): ... here. Perform a reverse program order walk. * gcc.dg/tree-ssa/ssa-dse-41.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-41.c | 16 ++ gcc/tree-ssa-dse.c | 182 +++++++++------------ 2 files changed, 91 insertions(+), 107 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-41.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-41.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-41.c new file mode 100644 index 00000000000..9128eea1035 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-41.c @@ -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" } } */ diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 76929fa03c7..e0a944c704a 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -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. */ -- 2.26.2