Refactor SCEV DFS finding
diff mbox series

Message ID alpine.LSU.2.20.1908161520590.32458@zhemvz.fhfr.qr
State New
Headers show
Series
  • Refactor SCEV DFS finding
Related show

Commit Message

Richard Biener Aug. 16, 2019, 1:22 p.m. UTC
This refactors the code to have a more obivous call structure and
to avoid duplicate code.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2019-08-16  Richard Biener  <rguenther@suse.de>

	* tree-scalar-evolution.c (follow_ssa_edge_expr): Declare.
	(follow_ssa_edge_binary): Call follow_ssa_edge_expr instead of
	follow_ssa_edge.
	(follow_ssa_edge_in_condition_phi_branch): Likewise.
	(analyze_evolution_in_loop): Likewise.
	(follow_ssa_edge, follow_ssa_edge_in_rhs): Inline into ...
	(follow_ssa_edge_expr): ... here.  Refactor code.

Patch
diff mbox series

Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c	(revision 274563)
+++ gcc/tree-scalar-evolution.c	(working copy)
@@ -876,8 +876,8 @@  enum t_bool {
 };
 
 
-static t_bool follow_ssa_edge (class loop *loop, gimple *, gphi *,
-			       tree *, int);
+static t_bool follow_ssa_edge_expr (class loop *loop, gimple *, tree, gphi *,
+				    tree *, int);
 
 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
    Return true if the strongly connected component has been found.  */
@@ -912,8 +912,8 @@  follow_ssa_edge_binary (class loop *loop
 		  (loop->num,
 		   chrec_convert (type, evol, at_stmt),
 		   code, rhs1, at_stmt);
-	      res = follow_ssa_edge
-		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
+	      res = follow_ssa_edge_expr
+		(loop, at_stmt, rhs0, halting_phi, &evol, limit);
 	      if (res == t_true)
 		*evolution_of_loop = evol;
 	      else if (res == t_false)
@@ -922,8 +922,8 @@  follow_ssa_edge_binary (class loop *loop
 		      (loop->num,
 		       chrec_convert (type, *evolution_of_loop, at_stmt),
 		       code, rhs0, at_stmt);
-		  res = follow_ssa_edge
-		    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
+		  res = follow_ssa_edge_expr
+		    (loop, at_stmt, rhs1, halting_phi,
 		     evolution_of_loop, limit);
 		  if (res == t_true)
 		    ;
@@ -943,8 +943,8 @@  follow_ssa_edge_binary (class loop *loop
 		  (loop->num, chrec_convert (type, *evolution_of_loop,
 					     at_stmt),
 		   code, rhs1, at_stmt);
-	      res = follow_ssa_edge
-		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
+	      res = follow_ssa_edge_expr
+		(loop, at_stmt, rhs0, halting_phi,
 		 evolution_of_loop, limit);
 	      if (res == t_true)
 		;	
@@ -961,8 +961,8 @@  follow_ssa_edge_binary (class loop *loop
 	      (loop->num, chrec_convert (type, *evolution_of_loop,
 					 at_stmt),
 	       code, rhs0, at_stmt);
-	  res = follow_ssa_edge
-	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
+	  res = follow_ssa_edge_expr
+	    (loop, at_stmt, rhs1, halting_phi,
 	     evolution_of_loop, limit);
 	  if (res == t_true)
 	    ;
@@ -993,8 +993,8 @@  follow_ssa_edge_binary (class loop *loop
 	  *evolution_of_loop = add_to_evolution
 	      (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
 	       MINUS_EXPR, rhs1, at_stmt);
-	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
-				 evolution_of_loop, limit);
+	  res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+				      evolution_of_loop, limit);
 	  if (res == t_true)
 	    ;
 	  else if (res == t_dont_know)
@@ -1014,140 +1014,6 @@  follow_ssa_edge_binary (class loop *loop
   return res;
 }
 
-/* Follow the ssa edge into the expression EXPR.
-   Return true if the strongly connected component has been found.  */
-
-static t_bool
-follow_ssa_edge_expr (class loop *loop, gimple *at_stmt, tree expr,
-		      gphi *halting_phi, tree *evolution_of_loop,
-		      int limit)
-{
-  enum tree_code code = TREE_CODE (expr);
-  tree type = TREE_TYPE (expr), rhs0, rhs1;
-  t_bool res;
-
-  /* The EXPR is one of the following cases:
-     - an SSA_NAME,
-     - an INTEGER_CST,
-     - a PLUS_EXPR,
-     - a POINTER_PLUS_EXPR,
-     - a MINUS_EXPR,
-     - an ASSERT_EXPR,
-     - other cases are not yet handled.  */
-
-  switch (code)
-    {
-    CASE_CONVERT:
-      /* This assignment is under the form "a_1 = (cast) rhs.  */
-      res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
-				  halting_phi, evolution_of_loop, limit);
-      *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
-      break;
-
-    case INTEGER_CST:
-      /* This assignment is under the form "a_1 = 7".  */
-      res = t_false;
-      break;
-
-    case SSA_NAME:
-      /* This assignment is under the form: "a_1 = b_2".  */
-      res = follow_ssa_edge
-	(loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
-      break;
-
-    case POINTER_PLUS_EXPR:
-    case PLUS_EXPR:
-    case MINUS_EXPR:
-      /* This case is under the form "rhs0 +- rhs1".  */
-      rhs0 = TREE_OPERAND (expr, 0);
-      rhs1 = TREE_OPERAND (expr, 1);
-      type = TREE_TYPE (rhs0);
-      STRIP_USELESS_TYPE_CONVERSION (rhs0);
-      STRIP_USELESS_TYPE_CONVERSION (rhs1);
-      res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
-				    halting_phi, evolution_of_loop, limit);
-      break;
-
-    case ADDR_EXPR:
-      /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
-      if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
-	{
-	  expr = TREE_OPERAND (expr, 0);
-	  rhs0 = TREE_OPERAND (expr, 0);
-	  rhs1 = TREE_OPERAND (expr, 1);
-	  type = TREE_TYPE (rhs0);
-	  STRIP_USELESS_TYPE_CONVERSION (rhs0);
-	  STRIP_USELESS_TYPE_CONVERSION (rhs1);
-	  res = follow_ssa_edge_binary (loop, at_stmt, type,
-					rhs0, POINTER_PLUS_EXPR, rhs1,
-					halting_phi, evolution_of_loop, limit);
-	}
-      else
-	res = t_false;
-      break;
-
-    case ASSERT_EXPR:
-      /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
-	 It must be handled as a copy assignment of the form a_1 = a_2.  */
-      rhs0 = ASSERT_EXPR_VAR (expr);
-      if (TREE_CODE (rhs0) == SSA_NAME)
-	res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
-			       halting_phi, evolution_of_loop, limit);
-      else
-	res = t_false;
-      break;
-
-    default:
-      res = t_false;
-      break;
-    }
-
-  return res;
-}
-
-/* Follow the ssa edge into the right hand side of an assignment STMT.
-   Return true if the strongly connected component has been found.  */
-
-static t_bool
-follow_ssa_edge_in_rhs (class loop *loop, gimple *stmt,
-			gphi *halting_phi, tree *evolution_of_loop,
-			int limit)
-{
-  enum tree_code code = gimple_assign_rhs_code (stmt);
-  tree type = gimple_expr_type (stmt), rhs1, rhs2;
-  t_bool res;
-
-  switch (code)
-    {
-    CASE_CONVERT:
-      /* This assignment is under the form "a_1 = (cast) rhs.  */
-      res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
-				  halting_phi, evolution_of_loop, limit);
-      *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
-      break;
-
-    case POINTER_PLUS_EXPR:
-    case PLUS_EXPR:
-    case MINUS_EXPR:
-      rhs1 = gimple_assign_rhs1 (stmt);
-      rhs2 = gimple_assign_rhs2 (stmt);
-      type = TREE_TYPE (rhs1);
-      res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
-				    halting_phi, evolution_of_loop, limit);
-      break;
-
-    default:
-      if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
-	res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
-				    halting_phi, evolution_of_loop, limit);
-      else
-	res = t_false;
-      break;
-    }
-
-  return res;
-}
-
 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
 
 static bool
@@ -1187,8 +1053,8 @@  follow_ssa_edge_in_condition_phi_branch
   if (TREE_CODE (branch) == SSA_NAME)
     {
       *evolution_of_branch = init_cond;
-      return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
-			      evolution_of_branch, limit);
+      return follow_ssa_edge_expr (loop, condition_phi, branch, halting_phi,
+				   evolution_of_branch, limit);
     }
 
   /* This case occurs when one of the condition branches sets
@@ -1295,65 +1161,158 @@  follow_ssa_edge_inner_loop_phi (class lo
 			       evolution_of_loop, limit);
 }
 
-/* Follow an SSA edge from a loop-phi-node to itself, constructing a
-   path that is analyzed on the return walk.  */
+/* Follow the ssa edge into the expression EXPR.
+   Return true if the strongly connected component has been found.  */
 
 static t_bool
-follow_ssa_edge (class loop *loop, gimple *def, gphi *halting_phi,
-		 tree *evolution_of_loop, int limit)
+follow_ssa_edge_expr (class loop *loop, gimple *at_stmt, tree expr,
+		      gphi *halting_phi, tree *evolution_of_loop,
+		      int limit)
 {
-  class loop *def_loop;
+  enum tree_code code;
+  tree type, rhs0, rhs1 = NULL_TREE;
 
-  if (gimple_nop_p (def))
-    return t_false;
+  /* The EXPR is one of the following cases:
+     - an SSA_NAME,
+     - an INTEGER_CST,
+     - a PLUS_EXPR,
+     - a POINTER_PLUS_EXPR,
+     - a MINUS_EXPR,
+     - an ASSERT_EXPR,
+     - other cases are not yet handled.  */
 
-  /* Give up if the path is longer than the MAX that we allow.  */
-  if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
-    return t_dont_know;
-
-  def_loop = loop_containing_stmt (def);
-
-  switch (gimple_code (def))
-    {
-    case GIMPLE_PHI:
-      if (!loop_phi_node_p (def))
-	/* DEF is a condition-phi-node.  Follow the branches, and
-	   record their evolutions.  Finally, merge the collected
-	   information and set the approximation to the main
-	   variable.  */
-	return follow_ssa_edge_in_condition_phi
-	  (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
-	   limit);
-
-      /* When the analyzed phi is the halting_phi, the
-	 depth-first search is over: we have found a path from
-	 the halting_phi to itself in the loop.  */
-      if (def == halting_phi)
-	return t_true;
+  /* For SSA_NAME look at the definition statement, handling
+     PHI nodes and otherwise expand appropriately for the expression
+     handling below.  */
+  if (TREE_CODE (expr) == SSA_NAME)
+    {
+      gimple *def = SSA_NAME_DEF_STMT (expr);
 
-      /* Otherwise, the evolution of the HALTING_PHI depends
-	 on the evolution of another loop-phi-node, i.e. the
-	 evolution function is a higher degree polynomial.  */
-      if (def_loop == loop)
+      if (gimple_nop_p (def))
 	return t_false;
 
-      /* Inner loop.  */
-      if (flow_loop_nested_p (loop, def_loop))
-	return follow_ssa_edge_inner_loop_phi
-	  (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
-	   limit + 1);
+      /* Give up if the path is longer than the MAX that we allow.  */
+      if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
+	return t_dont_know;
 
-      /* Outer loop.  */
-      return t_false;
+      if (gphi *phi = dyn_cast <gphi *>(def))
+	{
+	  if (!loop_phi_node_p (phi))
+	    /* DEF is a condition-phi-node.  Follow the branches, and
+	       record their evolutions.  Finally, merge the collected
+	       information and set the approximation to the main
+	       variable.  */
+	    return follow_ssa_edge_in_condition_phi
+		(loop, phi, halting_phi, evolution_of_loop, limit);
+
+	  /* When the analyzed phi is the halting_phi, the
+	     depth-first search is over: we have found a path from
+	     the halting_phi to itself in the loop.  */
+	  if (phi == halting_phi)
+	    return t_true;
+
+	  /* Otherwise, the evolution of the HALTING_PHI depends
+	     on the evolution of another loop-phi-node, i.e. the
+	     evolution function is a higher degree polynomial.  */
+	  class loop *def_loop = loop_containing_stmt (def);
+	  if (def_loop == loop)
+	    return t_false;
+
+	  /* Inner loop.  */
+	  if (flow_loop_nested_p (loop, def_loop))
+	    return follow_ssa_edge_inner_loop_phi
+		(loop, phi, halting_phi, evolution_of_loop,
+		 limit + 1);
 
-    case GIMPLE_ASSIGN:
-      return follow_ssa_edge_in_rhs (loop, def, halting_phi,
-				     evolution_of_loop, limit);
+	  /* Outer loop.  */
+	  return t_false;
+	}
 
-    default:
       /* At this level of abstraction, the program is just a set
 	 of GIMPLE_ASSIGNs and PHI_NODEs.  In principle there is no
-	 other node to be handled.  */
+	 other def to be handled.  */
+      if (!is_gimple_assign (def))
+	return t_false;
+
+      code = gimple_assign_rhs_code (def);
+      switch (get_gimple_rhs_class (code))
+	{
+	case GIMPLE_BINARY_RHS:
+	  rhs0 = gimple_assign_rhs1 (def);
+	  rhs1 = gimple_assign_rhs2 (def);
+	  break;
+	case GIMPLE_UNARY_RHS:
+	case GIMPLE_SINGLE_RHS:
+	  rhs0 = gimple_assign_rhs1 (def);
+	  break;
+	default:
+	  return t_false;
+	}
+      type = TREE_TYPE (gimple_assign_lhs (def));
+      at_stmt = def;
+    }
+  else
+    {
+      code = TREE_CODE (expr);
+      type = TREE_TYPE (expr);
+      switch (code)
+	{
+	CASE_CONVERT:
+	  rhs0 = TREE_OPERAND (expr, 0);
+	  break;
+	case POINTER_PLUS_EXPR:
+	case PLUS_EXPR:
+	case MINUS_EXPR:
+	  rhs0 = TREE_OPERAND (expr, 0);
+	  rhs1 = TREE_OPERAND (expr, 1);
+	  break;
+	default:
+	  rhs0 = expr;
+	}
+    }
+
+  switch (code)
+    {
+    CASE_CONVERT:
+      {
+	/* This assignment is under the form "a_1 = (cast) rhs.  */
+	t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+					   evolution_of_loop, limit);
+	*evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
+	return res;
+      }
+
+    case INTEGER_CST:
+      /* This assignment is under the form "a_1 = 7".  */
+      return t_false;
+
+    case ADDR_EXPR:
+      {
+	/* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
+	if (TREE_CODE (TREE_OPERAND (rhs0, 0)) != MEM_REF)
+	  return t_false;
+	tree mem = TREE_OPERAND (rhs0, 0);
+	rhs0 = TREE_OPERAND (mem, 0);
+	rhs1 = TREE_OPERAND (mem, 1);
+	code = POINTER_PLUS_EXPR;
+      }
+      /* Fallthru.  */
+    case POINTER_PLUS_EXPR:
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      /* This case is under the form "rhs0 +- rhs1".  */
+      STRIP_USELESS_TYPE_CONVERSION (rhs0);
+      STRIP_USELESS_TYPE_CONVERSION (rhs1);
+      return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
+				     halting_phi, evolution_of_loop, limit);
+
+    case ASSERT_EXPR:
+      /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+	 It must be handled as a copy assignment of the form a_1 = a_2.  */
+      return follow_ssa_edge_expr (loop, at_stmt, ASSERT_EXPR_VAR (rhs0),
+				   halting_phi, evolution_of_loop, limit);
+
+    default:
       return t_false;
     }
 }
@@ -1447,7 +1406,6 @@  analyze_evolution_in_loop (gphi *loop_ph
   for (i = 0; i < n; i++)
     {
       tree arg = PHI_ARG_DEF (loop_phi_node, i);
-      gimple *ssa_chain;
       tree ev_fn;
       t_bool res;
 
@@ -1460,11 +1418,10 @@  analyze_evolution_in_loop (gphi *loop_ph
 	{
 	  bool val = false;
 
-	  ssa_chain = SSA_NAME_DEF_STMT (arg);
-
 	  /* Pass in the initial condition to the follow edge function.  */
 	  ev_fn = init_cond;
-	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
+	  res = follow_ssa_edge_expr (loop, loop_phi_node, arg,
+				      loop_phi_node, &ev_fn, 0);
 
 	  /* If ev_fn has no evolution in the inner loop, and the
 	     init_cond is not equal to ev_fn, then we have an