From 3daacdcd5f20d084294f2cc50f84e3e8769205f1 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Thu, 10 Dec 2015 09:34:43 -0700 Subject: re PR tree-optimization/68619 (error: loop with header 6 not in loop tree) 2015-12-10 Jeff Law PR tree-optimization/68619 * tree-ssa-dom.c (dom_opt_dom_walker::before_dom_children): Propgate return value from optimize_stmt. (dom_opt_dom_walker): Add new argument to dom_walker constructor. (pass_dominator:execute): If a block has an unreachable edge, remove all jump threads through any successor of the affected block. (record_equivalences_from_phis): Ignore alternative if the edge does not have EDGE_EXECUTABLE set. (single_incoming_edge_ignoring_loop_edges): Similarly. (optimize_stmt): If a gimple_code has a compile-time constant condition, return the edge taken for that constant value. Also change the condition to true/false as necessary. * domwalk.h (dom_walker::dom_walker): Add new argument skip_unreachable_blocks. Don't provide empty constructor body. (dom_walker::before_dom_children): Change return type. (dom_walker::bb_reachable): Declare new private method. (dom_walker::propagate_unreachable_to_edges): Likewise. (dom_walker::m_unreachable_dom): Declare new private data member. (dom_walker::m_skip_unreachable_blocks): Likewise. * domwalk.c: Include dumpfile.h. (dom_walker::dom_walker): New constructor. Initialize private data members. If needed, set EDGE_EXECUTABLE for all edges in the CFG, extracted from tree-ssa-sccvn.c. (dom_walker::bb_reachable): New method extracted from tree-ssa-sccvn.c (dom_walker::propagate_unreachable_to_edges): Likewise. (dom_walker::walk): Only call before_dom_children on reachable blocks. If before_dom_children returns an edge, then clear EDGE_EXECUTABLE for all other outgoing edges from the same block. For unreachable blocks, call propagate_unreachable_to_edges. Similarly, only call after_dom_children on reachable blocks. For unreachable blocks, conditionally clear m_unreachable_dom. * tree-ssa-sccvn.c (sccvn_dom_walker::unreachable_dom): Remove private data member. (sccvn_dom_walker::after_dom_children): Use methods from dom_walker class. (run_scc_vn): Likewise. (sccvn_dom_walker::before_dom_children): Likewise. Return the taken outgoing edge if a COND, SWITCH, or GOTO are optimized. * compare-elim.c (find_comparison_dom_walker::before_dom_children): Change return type to an edge. Always return NULL. * fwprop.c (single_def_use_dom_walker::before_dom_children): Likewise. * gimple-ssa-strength-reduction.c (find_candidates_dom_walker::before_dom_children): Likewise. * ipa-prop.c (analysis_dom_walker::before_dom_children): Likewise. (ipcp_modif_dom_walker::before_dom_children): Likewise. * tree-into-ssa.c (rewrite_dom_walker::before_dom_children): Likewise. (rewrite_update_dom_walker::before_dom_children): Likewise. (mark_def_dom_children::before_dom_children): Likewise. * tree-ssa-dse.c (dse_dom_walker::before_dom_children): Likewise. * tree-ssa-loop-im.c (invariantness_dom_walker::before_dom_children): Likewise. (move_computations_dom_walker::before_dom_walker): Likewise. * tree-ssa-phiopt.c (nontrapping_dom_walker::before_dom_children): Likewise. * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Likewise. * tree-ssa-propagate.c (substitute_and_fold_dom_walker::before_dom_children): Likewise. * tree-ssa-strlen.c (strlen_dom_walker::before_dom_children): Likewise. * tree-ssa-uncprop.c (uncprop_dom_walker::before_dom_children): Likewise. PR tree-optimization/68619 * gcc.dg/tree-ssa/pr68619-1.c: New test. * gcc.dg/tree-ssa/pr68619-2.c: New test. * gcc.dg/tree-ssa/pr68619-3.c: New test. * gcc.dg/tree-ssa/pr68619-4.c: New test. * gcc.dg/tree-ssa/pr68619-5.c: New test. From-SVN: r231527 --- gcc/tree-ssa-sccvn.c | 81 +++++++--------------------------------------------- 1 file changed, 11 insertions(+), 70 deletions(-) (limited to 'gcc/tree-ssa-sccvn.c') diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 3086f84..84e9563 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -4208,11 +4208,10 @@ class sccvn_dom_walker : public dom_walker { public: sccvn_dom_walker () - : dom_walker (CDI_DOMINATORS), fail (false), unreachable_dom (NULL), - cond_stack (vNULL) {} + : dom_walker (CDI_DOMINATORS, true), fail (false), cond_stack (vNULL) {} ~sccvn_dom_walker (); - virtual void before_dom_children (basic_block); + virtual edge before_dom_children (basic_block); virtual void after_dom_children (basic_block); void record_cond (basic_block, @@ -4221,7 +4220,6 @@ public: enum tree_code code, tree lhs, tree rhs, bool value); bool fail; - basic_block unreachable_dom; vec > > cond_stack; }; @@ -4302,9 +4300,6 @@ sccvn_dom_walker::record_conds (basic_block bb, void sccvn_dom_walker::after_dom_children (basic_block bb) { - if (unreachable_dom == bb) - unreachable_dom = NULL; - while (!cond_stack.is_empty () && cond_stack.last ().first == bb) { @@ -4319,56 +4314,14 @@ sccvn_dom_walker::after_dom_children (basic_block bb) /* Value number all statements in BB. */ -void +edge sccvn_dom_walker::before_dom_children (basic_block bb) { edge e; edge_iterator ei; if (fail) - return; - - /* If any of the predecessor edges that do not come from blocks dominated - by us are still marked as possibly executable consider this block - reachable. */ - bool reachable = false; - if (!unreachable_dom) - { - reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun); - FOR_EACH_EDGE (e, ei, bb->preds) - if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) - reachable |= (e->flags & EDGE_EXECUTABLE); - } - - /* If the block is not reachable all outgoing edges are not - executable. Neither are incoming edges with src dominated by us. */ - if (!reachable) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Marking all outgoing edges of unreachable " - "BB %d as not executable\n", bb->index); - - FOR_EACH_EDGE (e, ei, bb->succs) - e->flags &= ~EDGE_EXECUTABLE; - - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Marking backedge from BB %d into " - "unreachable BB %d as not executable\n", - e->src->index, bb->index); - e->flags &= ~EDGE_EXECUTABLE; - } - } - - /* Record the most dominating unreachable block. */ - if (!unreachable_dom) - unreachable_dom = bb; - - return; - } + return NULL; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Visiting BB %d\n", bb->index); @@ -4429,7 +4382,7 @@ sccvn_dom_walker::before_dom_children (basic_block bb) && !DFS (res)) { fail = true; - return; + return NULL; } } for (gimple_stmt_iterator gsi = gsi_start_bb (bb); @@ -4442,20 +4395,20 @@ sccvn_dom_walker::before_dom_children (basic_block bb) && !DFS (op)) { fail = true; - return; + return NULL; } } /* Finally look at the last stmt. */ gimple *stmt = last_stmt (bb); if (!stmt) - return; + return NULL; enum gimple_code code = gimple_code (stmt); if (code != GIMPLE_COND && code != GIMPLE_SWITCH && code != GIMPLE_GOTO) - return; + return NULL; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -4498,19 +4451,17 @@ sccvn_dom_walker::before_dom_children (basic_block bb) gcc_unreachable (); } if (!val) - return; + return NULL; edge taken = find_taken_edge (bb, vn_valueize (val)); if (!taken) - return; + return NULL; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as " "not executable\n", bb->index, bb->index, taken->dest->index); - FOR_EACH_EDGE (e, ei, bb->succs) - if (e != taken) - e->flags &= ~EDGE_EXECUTABLE; + return taken; } /* Do SCCVN. Returns true if it finished, false if we bailed out @@ -4520,7 +4471,6 @@ sccvn_dom_walker::before_dom_children (basic_block bb) bool run_scc_vn (vn_lookup_kind default_vn_walk_kind_) { - basic_block bb; size_t i; default_vn_walk_kind = default_vn_walk_kind_; @@ -4550,15 +4500,6 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) } } - /* Mark all edges as possibly executable. */ - FOR_ALL_BB_FN (bb, cfun) - { - edge_iterator ei; - edge e; - FOR_EACH_EDGE (e, ei, bb->succs) - e->flags |= EDGE_EXECUTABLE; - } - /* Walk all blocks in dominator order, value-numbering stmts SSA defs and decide whether outgoing edges are not executable. */ sccvn_dom_walker walker; -- cgit v1.1