re PR tree-optimization/68619 (error: loop with header 6 not in loop tree)

2015-12-10  Jeff Law  <law@redhat.com>

	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

1 files changed, 105 insertions, 2 deletions

diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index 167fc38..2481e34 100644
--- a/gcc/domwalk.c
+++ b/gcc/domwalk.c
@@ -24,6 +24,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "backend.h"
 #include "cfganal.h"
 #include "domwalk.h"
+#include "dumpfile.h"
 
 /* This file implements a generic walker for dominator trees.
 
@@ -142,6 +143,91 @@ cmp_bb_postorder (const void *a, const void *b)
   return 1;
 }
 
+/* Constructor for a dom walker.
+
+   If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
+   EDGE_EXECUTABLE on every edge in the CFG. */
+dom_walker::dom_walker (cdi_direction direction,
+			bool skip_unreachable_blocks)
+  : m_dom_direction (direction),
+    m_skip_unreachable_blocks (skip_unreachable_blocks),
+    m_unreachable_dom (NULL)
+{
+  /* If we are not skipping unreachable blocks, then there is nothing
+     to do.  */
+  if (!m_skip_unreachable_blocks)
+    return;
+
+  basic_block bb;
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	e->flags |= EDGE_EXECUTABLE;
+    }
+}
+
+/* Return TRUE if BB is reachable, false otherwise.  */
+
+bool
+dom_walker::bb_reachable (struct function *fun, basic_block bb)
+{
+  /* If we're not skipping unreachable blocks, then assume everything
+     is reachable.  */
+  if (!m_skip_unreachable_blocks)
+    return true;
+
+  /* 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 (!m_unreachable_dom)
+    {
+      reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
+	  reachable |= (e->flags & EDGE_EXECUTABLE);
+    }
+
+  return reachable;
+}
+
+/* BB has been determined to be unreachable.  Propagate that property
+   to incoming and outgoing edges of BB as appropriate.  */
+
+void
+dom_walker::propagate_unreachable_to_edges (basic_block bb,
+					    FILE *dump_file,
+					    int dump_flags)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Marking all outgoing edges of unreachable "
+	     "BB %d as not executable\n", bb->index);
+
+  edge_iterator ei;
+  edge e;
+  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;
+	}
+    }
+
+  if (!m_unreachable_dom)
+    m_unreachable_dom = bb;
+}
+
 /* Recursively walk the dominator tree.
    BB is the basic block we are currently visiting.  */
 
@@ -171,9 +257,23 @@ dom_walker::walk (basic_block bb)
 	  || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
 	  || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
 	{
+
 	  /* Callback for subclasses to do custom things before we have walked
 	     the dominator children, but before we walk statements.  */
-	  before_dom_children (bb);
+	  if (this->bb_reachable (cfun, bb))
+	    {
+	      edge taken_edge = before_dom_children (bb);
+	      if (taken_edge)
+		{
+		  edge_iterator ei;
+		  edge e;
+		  FOR_EACH_EDGE (e, ei, bb->succs)
+		    if (e != taken_edge)
+		      e->flags &= ~EDGE_EXECUTABLE;
+		}
+	    }
+	  else
+	    propagate_unreachable_to_edges (bb, dump_file, dump_flags);
 
 	  /* Mark the current BB to be popped out of the recursion stack
 	     once children are processed.  */
@@ -203,7 +303,10 @@ dom_walker::walk (basic_block bb)
 
 	  /* Callback allowing subclasses to do custom things after we have
 	     walked dominator children, but before we walk statements.  */
-	  after_dom_children (bb);
+	  if (bb_reachable (cfun, bb))
+	    after_dom_children (bb);
+	  else if (m_unreachable_dom == bb)
+	    m_unreachable_dom = NULL;
 	}
       if (sp)
 	bb = worklist[--sp];