Merge from trunk revision fba228e259dd5112851527f2dbb62c5601100985.

1 files changed, 198 insertions, 174 deletions

diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 04138cb..a63a976 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -33,12 +33,13 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-threadupdate.h"
 #include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
-#include "tree-ssa-dom.h"
 #include "gimple-fold.h"
 #include "cfganal.h"
 #include "alloc-pool.h"
 #include "vr-values.h"
 #include "gimple-ssa-evrp-analyze.h"
+#include "gimple-range.h"
+#include "gimple-range-path.h"
 
 /* To avoid code explosion due to jump threading, we limit the
    number of statements we are going to copy.  This variable
@@ -61,8 +62,7 @@ set_ssa_name_value (tree name, tree value)
   ssa_name_values[SSA_NAME_VERSION (name)] = value;
 }
 
-jump_threader::jump_threader (jump_threader_simplifier *simplifier,
-			      jt_state *state)
+jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
 {
   /* Initialize the per SSA_NAME value-handles array.  */
   gcc_assert (!ssa_name_values.exists ());
@@ -228,8 +228,6 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
      when we're finished processing E.  */
   for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
     {
-      tree cached_lhs = NULL;
-
       stmt = gsi_stmt (gsi);
 
       /* Ignore empty statements and labels.  */
@@ -326,75 +324,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
 	    continue;
 	}
 
-      /* At this point we have a statement which assigns an RHS to an
-	 SSA_VAR on the LHS.  We want to try and simplify this statement
-	 to expose more context sensitive equivalences which in turn may
-	 allow us to simplify the condition at the end of the loop.
-
-	 Handle simple copy operations as well as implied copies from
-	 ASSERT_EXPRs.  */
-      if (gimple_assign_single_p (stmt)
-          && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
-	cached_lhs = gimple_assign_rhs1 (stmt);
-      else if (gimple_assign_single_p (stmt)
-               && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
-	cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
-      else
-	{
-	  /* A statement that is not a trivial copy or ASSERT_EXPR.
-	     Try to fold the new expression.  Inserting the
-	     expression into the hash table is unlikely to help.  */
-	  /* ???  The DOM callback below can be changed to setting
-	     the mprts_hook around the call to thread_across_edge,
-	     avoiding the use substitution.  The VRP hook should be
-	     changed to properly valueize operands itself using
-	     SSA_NAME_VALUE in addition to its own lattice.  */
-	  cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
-						       threadedge_valueize);
-          if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
-	      && (!cached_lhs
-                  || (TREE_CODE (cached_lhs) != SSA_NAME
-                      && !is_gimple_min_invariant (cached_lhs))))
-	    {
-	      /* We're going to temporarily copy propagate the operands
-		 and see if that allows us to simplify this statement.  */
-	      tree *copy;
-	      ssa_op_iter iter;
-	      use_operand_p use_p;
-	      unsigned int num, i = 0;
-
-	      num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
-	      copy = XALLOCAVEC (tree, num);
-
-	      /* Make a copy of the uses & vuses into USES_COPY, then cprop into
-		 the operands.  */
-	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-		{
-		  tree tmp = NULL;
-		  tree use = USE_FROM_PTR (use_p);
-
-		  copy[i++] = use;
-		  if (TREE_CODE (use) == SSA_NAME)
-		    tmp = SSA_NAME_VALUE (use);
-		  if (tmp)
-		    SET_USE (use_p, tmp);
-		}
-
-	      cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
-
-	      /* Restore the statement's original uses/defs.  */
-	      i = 0;
-	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-		SET_USE (use_p, copy[i++]);
-	    }
-	}
-
-      /* Record the context sensitive equivalence if we were able
-	 to simplify this statement.  */
-      if (cached_lhs
-	  && (TREE_CODE (cached_lhs) == SSA_NAME
-	      || is_gimple_min_invariant (cached_lhs)))
-	m_state->register_equiv (gimple_get_lhs (stmt), cached_lhs);
+      m_state->register_equivs_stmt (stmt, e->src, m_simplifier);
     }
   return stmt;
 }
@@ -899,6 +829,7 @@ jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
 	  if (!bitmap_bit_p (visited, taken_edge->dest->index))
 	    {
 	      m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+	      m_state->append_path (taken_edge->dest);
 	      bitmap_set_bit (visited, taken_edge->dest->index);
 	      return thread_around_empty_blocks (path, taken_edge, visited);
 	    }
@@ -940,6 +871,7 @@ jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
       bitmap_set_bit (visited, taken_edge->dest->index);
 
       m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+      m_state->append_path (taken_edge->dest);
 
       thread_around_empty_blocks (path, taken_edge, visited);
       return true;
@@ -970,7 +902,7 @@ int
 jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
 					    edge e, bitmap visited)
 {
-  m_state->register_equivs_on_edge (e);
+  m_state->register_equivs_edge (e);
 
   /* PHIs create temporary equivalences.
      Note that if we found a PHI that made the block non-threadable, then
@@ -1048,6 +980,7 @@ jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
 	    m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
 
 	  m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
+	  m_state->append_path (taken_edge->dest);
 
 	  /* See if we can thread through DEST as well, this helps capture
 	     secondary effects of threading without having to re-run DOM or
@@ -1263,6 +1196,9 @@ jump_threader::thread_outgoing_edges (basic_block bb)
   int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
   gimple *last;
 
+  if (!flag_thread_jumps)
+    return;
+
   /* If we have an outgoing edge to a block with multiple incoming and
      outgoing edges, then we may be able to thread the edge, i.e., we
      may be able to statically determine which of the outgoing edges
@@ -1290,26 +1226,18 @@ jump_threader::thread_outgoing_edges (basic_block bb)
     }
 }
 
-jt_state::jt_state (const_and_copies *copies,
-		    avail_exprs_stack *exprs,
-		    evrp_range_analyzer *evrp)
-{
-  m_copies = copies;
-  m_exprs = exprs;
-  m_evrp = evrp;
-}
+// Marker to keep track of the start of the current path.
+const basic_block jt_state::BB_MARKER = (basic_block) -1;
 
 // Record that E is being crossed.
 
 void
-jt_state::push (edge)
+jt_state::push (edge e)
 {
-  if (m_copies)
-    m_copies->push_marker ();
-  if (m_exprs)
-    m_exprs->push_marker ();
-  if (m_evrp)
-    m_evrp->push_marker ();
+  m_blocks.safe_push (BB_MARKER);
+  if (m_blocks.length () == 1)
+    m_blocks.safe_push (e->src);
+  m_blocks.safe_push (e->dest);
 }
 
 // Pop to the last pushed state.
@@ -1317,127 +1245,223 @@ jt_state::push (edge)
 void
 jt_state::pop ()
 {
-  if (m_copies)
-    m_copies->pop_to_marker ();
-  if (m_exprs)
-    m_exprs->pop_to_marker ();
-  if (m_evrp)
-    m_evrp->pop_to_marker ();
+  if (!m_blocks.is_empty ())
+    {
+      while (m_blocks.last () != BB_MARKER)
+	m_blocks.pop ();
+      // Pop marker.
+      m_blocks.pop ();
+    }
 }
 
-// Record an equivalence from DST to SRC.  If UPDATE_RANGE is TRUE,
-// update the value range associated with DST.
+// Add BB to the list of blocks seen.
 
 void
-jt_state::register_equiv (tree dst, tree src, bool update_range)
+jt_state::append_path (basic_block bb)
 {
-  if (m_copies)
-    m_copies->record_const_or_copy (dst, src);
+  gcc_checking_assert (!m_blocks.is_empty ());
+  m_blocks.safe_push (bb);
+}
 
-  /* If requested, update the value range associated with DST, using
-     the range from SRC.  */
-  if (m_evrp && update_range)
+void
+jt_state::dump (FILE *out)
+{
+  if (!m_blocks.is_empty ())
     {
-      /* Get new VR we can pass to push_value_range.  */
-      value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
-      new (new_vr) value_range_equiv ();
-
-      /* There are three cases to consider:
-
-	 First if SRC is an SSA_NAME, then we can copy the value range
-	 from SRC into NEW_VR.
-
-	 Second if SRC is an INTEGER_CST, then we can just set NEW_VR
-	 to a singleton range.  Note that even if SRC is a constant we
-	 need to set a suitable output range so that VR_UNDEFINED
-	 ranges do not leak through.
-
-	 Otherwise set NEW_VR to varying.  This may be overly
-	 conservative.  */
-      if (TREE_CODE (src) == SSA_NAME)
-	new_vr->deep_copy (m_evrp->get_value_range (src));
-      else if (TREE_CODE (src) == INTEGER_CST)
-	new_vr->set (src);
-      else
-	new_vr->set_varying (TREE_TYPE (src));
+      auto_vec<basic_block> path;
+      get_path (path);
+      dump_ranger (out, path);
+    }
+}
+
+void
+jt_state::debug ()
+{
+  push_dump_file save (stderr, TDF_DETAILS);
+  dump (stderr);
+}
+
+// Convert the current path in jt_state into a path suitable for the
+// path solver.  Return the resulting path in PATH.
+
+void
+jt_state::get_path (vec<basic_block> &path)
+{
+  path.truncate (0);
+
+  for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
+    {
+      basic_block bb = m_blocks[i];
 
-      /* This is a temporary range for DST, so push it.  */
-      m_evrp->push_value_range (dst, new_vr);
+      if (bb != BB_MARKER)
+	path.safe_push (bb);
     }
 }
 
+// Record an equivalence from DST to SRC.  If UPDATE_RANGE is TRUE,
+// update the value range associated with DST.
+
+void
+jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
+			  tree src ATTRIBUTE_UNUSED,
+			  bool update_range ATTRIBUTE_UNUSED)
+{
+}
+
 // Record any ranges calculated in STMT.  If TEMPORARY is TRUE, then
 // this is a temporary equivalence and should be recorded into the
 // unwind table, instead of the global table.
 
 void
-jt_state::record_ranges_from_stmt (gimple *stmt, bool temporary)
+jt_state::record_ranges_from_stmt (gimple *,
+				   bool temporary ATTRIBUTE_UNUSED)
 {
-  if (m_evrp)
-    m_evrp->record_ranges_from_stmt (stmt, temporary);
 }
 
 // Record any equivalences created by traversing E.
 
 void
-jt_state::register_equivs_on_edge (edge e)
+jt_state::register_equivs_edge (edge)
 {
-  if (m_copies && m_exprs)
-    record_temporary_equivalences (e, m_copies, m_exprs);
 }
 
-jump_threader_simplifier::jump_threader_simplifier (vr_values *v)
+void
+jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
+				jt_simplifier *simplifier)
 {
-  m_vr_values = v;
+  /* At this point we have a statement which assigns an RHS to an
+     SSA_VAR on the LHS.  We want to try and simplify this statement
+     to expose more context sensitive equivalences which in turn may
+     allow us to simplify the condition at the end of the loop.
+
+     Handle simple copy operations as well as implied copies from
+     ASSERT_EXPRs.  */
+  tree cached_lhs = NULL;
+  if (gimple_assign_single_p (stmt)
+      && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
+    cached_lhs = gimple_assign_rhs1 (stmt);
+  else if (gimple_assign_single_p (stmt)
+	   && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
+    cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
+  else
+    {
+      /* A statement that is not a trivial copy or ASSERT_EXPR.
+	 Try to fold the new expression.  Inserting the
+	 expression into the hash table is unlikely to help.  */
+      /* ???  The DOM callback below can be changed to setting
+	 the mprts_hook around the call to thread_across_edge,
+	 avoiding the use substitution.  The VRP hook should be
+	 changed to properly valueize operands itself using
+	 SSA_NAME_VALUE in addition to its own lattice.  */
+      cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
+						   threadedge_valueize);
+      if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
+	  && (!cached_lhs
+	      || (TREE_CODE (cached_lhs) != SSA_NAME
+		  && !is_gimple_min_invariant (cached_lhs))))
+	{
+	  /* We're going to temporarily copy propagate the operands
+	     and see if that allows us to simplify this statement.  */
+	  tree *copy;
+	  ssa_op_iter iter;
+	  use_operand_p use_p;
+	  unsigned int num, i = 0;
+
+	  num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
+	  copy = XALLOCAVEC (tree, num);
+
+	  /* Make a copy of the uses & vuses into USES_COPY, then cprop into
+	     the operands.  */
+	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+	    {
+	      tree tmp = NULL;
+	      tree use = USE_FROM_PTR (use_p);
+
+	      copy[i++] = use;
+	      if (TREE_CODE (use) == SSA_NAME)
+		tmp = SSA_NAME_VALUE (use);
+	      if (tmp)
+		SET_USE (use_p, tmp);
+	    }
+
+	  cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
+
+	  /* Restore the statement's original uses/defs.  */
+	  i = 0;
+	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+	    SET_USE (use_p, copy[i++]);
+	}
+    }
+
+  /* Record the context sensitive equivalence if we were able
+     to simplify this statement.  */
+  if (cached_lhs
+      && (TREE_CODE (cached_lhs) == SSA_NAME
+	  || is_gimple_min_invariant (cached_lhs)))
+    register_equiv (gimple_get_lhs (stmt), cached_lhs,
+		    /*update_range=*/false);
 }
 
-// Return the singleton that resolves STMT, if it is possible to
-// simplify it.
-//
-// STMT may be a dummy statement, not necessarily in the CFG, in which
-// case WITHIN_STMT can be used to determine the position in the CFG
-// where STMT should be evaluated as being in.
+// Hybrid threader implementation.
+
+
+hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
+					    path_range_query *q)
+{
+  m_ranger = r;
+  m_query = q;
+}
 
 tree
-jump_threader_simplifier::simplify (gimple *stmt,
-				    gimple *within_stmt,
-				    basic_block,
-				    jt_state *)
+hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
+				jt_state *state)
 {
-  if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+  int_range_max r;
+
+  compute_ranges_from_state (stmt, state);
+
+  if (gimple_code (stmt) == GIMPLE_COND
+      || gimple_code (stmt) == GIMPLE_ASSIGN)
     {
-      simplify_using_ranges simplifier (m_vr_values);
-      return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
-						  gimple_cond_lhs (cond_stmt),
-						  gimple_cond_rhs (cond_stmt),
-						  within_stmt);
+      tree ret;
+      if (m_query->range_of_stmt (r, stmt) && r.singleton_p (&ret))
+	return ret;
     }
-  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
+  else if (gimple_code (stmt) == GIMPLE_SWITCH)
     {
-      tree op = gimple_switch_index (switch_stmt);
-      if (TREE_CODE (op) != SSA_NAME)
-	return NULL_TREE;
-
-      const value_range_equiv *vr = m_vr_values->get_value_range (op);
-      return find_case_label_range (switch_stmt, vr);
+      gswitch *switch_stmt = dyn_cast <gswitch *> (stmt);
+      tree index = gimple_switch_index (switch_stmt);
+      if (m_query->range_of_expr (r, index, stmt))
+	return find_case_label_range (switch_stmt, &r);
     }
-   if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+  return NULL;
+}
+
+// Use STATE to generate the list of imports needed for the solver,
+// and calculate the ranges along the path.
+
+void
+hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state)
+{
+  auto_bitmap imports;
+  gori_compute &gori = m_ranger->gori ();
+
+  state->get_path (m_path);
+
+  // Start with the imports to the final conditional.
+  bitmap_copy (imports, gori.imports (m_path[0]));
+
+  // Add any other interesting operands we may have missed.
+  if (gimple_bb (stmt) != m_path[0])
     {
-      tree lhs = gimple_assign_lhs (assign_stmt);
-      if (TREE_CODE (lhs) == SSA_NAME
-	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
-	      || POINTER_TYPE_P (TREE_TYPE (lhs)))
-	  && stmt_interesting_for_vrp (stmt))
+      for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
 	{
-	  edge dummy_e;
-	  tree dummy_tree;
-	  value_range_equiv new_vr;
-	  m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
-						&new_vr);
-	  tree singleton;
-	  if (new_vr.singleton_p (&singleton))
-	    return singleton;
+	  tree op = gimple_op (stmt, i);
+	  if (op
+	      && TREE_CODE (op) == SSA_NAME
+	      && irange::supports_type_p (TREE_TYPE (op)))
+	    bitmap_set_bit (imports, SSA_NAME_VERSION (op));
 	}
     }
-   return NULL;
+  m_query->compute_ranges (m_path, imports);
 }