* tree-ssa-phiopt.c (minmax_replacement, blocks_in_phiopt_order):

	New functions.
	(tree_ssa_phiopt): Use blocks_in_phiopt_order and minmax_replacement.
	Remove unused removed_phis variable.
	(conditional_replacement): Use build1/build2.
	(abs_replacement): Use last_and_only_stmt and build1/build2.

	* gcc.dg/tree-ssa/phi-opt-5.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@96439 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 387 insertions, 76 deletions

diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index 6943c1732c1..3eedf9974e4 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -41,10 +41,13 @@ static bool conditional_replacement (basic_block, basic_block, basic_block,
 				     edge, edge, tree, tree, tree);
 static bool value_replacement (basic_block, basic_block, basic_block,
 			       edge, edge, tree, tree, tree);
+static bool minmax_replacement (basic_block, basic_block, basic_block,
+				edge, edge, tree, tree, tree);
 static bool abs_replacement (basic_block, basic_block, basic_block,
 			     edge, edge, tree, tree, tree);
 static void replace_phi_edge_with_variable (basic_block, basic_block, edge,
 					    tree, tree);
+static basic_block *blocks_in_phiopt_order (void);
 
 /* This pass eliminates PHI nodes which can be trivially implemented as
    an assignment from a conditional expression.  i.e. if we have something
@@ -102,6 +105,21 @@ static void replace_phi_edge_with_variable (basic_block, basic_block, edge,
      bb2:
       x = ABS_EXPR< a >;
 
+   Similarly,
+
+     bb0:
+      if (a <= b) goto bb2; else goto bb1;
+     bb1:
+      goto bb2;
+     bb2:
+      x = PHI (b (bb1), a (bb0));
+
+   Becomes
+
+     x = MIN_EXPR (a, b)
+
+   And the same transformation for MAX_EXPR.
+
    bb1 will become unreachable and bb0 and bb2 will almost always be merged
    into a single block.  Similar transformations are done by the ifcvt
    RTL optimizer.  */
@@ -110,15 +128,28 @@ static void
 tree_ssa_phiopt (void)
 {
   basic_block bb;
+  basic_block *bb_order;
+  unsigned n, i;
+
+  /* Search every basic block for COND_EXPR we may be able to optimize.
+
+     We walk the blocks in order that guarantees that a block with
+     a single predecessor is processed before the predecessor.
+     This ensures that we collapse inner ifs before visiting the
+     outer ones, and also that we do not try to visit a removed
+     block.  */
+  bb_order = blocks_in_phiopt_order ();
+  n = n_basic_blocks;
 
-  /* Search every basic block for COND_EXPR we may be able to optimize
-     in reverse order so we can find more.  */
-  FOR_EACH_BB_REVERSE (bb)
+  for (i = 0; i < n; i++)
     {
       tree cond_expr;
       tree phi;
       basic_block bb1, bb2;
       edge e1, e2;
+      tree arg0, arg1;
+
+      bb = bb_order[i];
 
       cond_expr = last_stmt (bb);
       /* Check to see if the last statement is a COND_EXPR.  */
@@ -174,25 +205,80 @@ tree_ssa_phiopt (void)
       /* Check to make sure that there is only one PHI node.
          TODO: we could do it with more than one iff the other PHI nodes
 	 have the same elements for these two edges.  */
-      if (phi && PHI_CHAIN (phi) == NULL)
-	{
-	  tree arg0 = NULL, arg1 = NULL;
+      if (!phi || PHI_CHAIN (phi) != NULL)
+	continue;
 
-	  arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
-	  arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
+      arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
+      arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
 
-	  /* We know something is wrong if we cannot find the edges in the PHI
-	     node.  */
-	  gcc_assert (arg0 != NULL && arg1 != NULL);
+      /* We know something is wrong if we cannot find the edges in the PHI
+	 node.  */
+      gcc_assert (arg0 != NULL && arg1 != NULL);
 
-	  /* Do the replacement of conditional if it can be done.  */
-	  if (conditional_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1)
-	      || value_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1)
-	      || abs_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
-	    {
-	    }
+      /* Do the replacement of conditional if it can be done.  */
+      if (conditional_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
+	;
+      else if (value_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
+	;
+      else if (abs_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
+	;
+      else
+	minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1);
+    }
+
+  free (bb_order);
+}
+
+/* Returns the list of basic blocks in the function in an order that guarantees
+   that if a block X has just a single predecessor Y, then Y is after X in the
+   ordering.  */
+
+static basic_block *
+blocks_in_phiopt_order (void)
+{
+  basic_block x, y;
+  basic_block *order = xmalloc (sizeof (basic_block) * n_basic_blocks);
+  unsigned n = n_basic_blocks, np, i;
+  sbitmap visited = sbitmap_alloc (last_basic_block + 2);
+
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
+
+  sbitmap_zero (visited);
+
+  MARK_VISITED (ENTRY_BLOCK_PTR);
+  FOR_EACH_BB (x)
+    {
+      if (VISITED_P (x))
+	continue;
+
+      /* Walk the predecessors of x as long as they have precisely one
+	 predecessor and add them to the list, so that they get stored
+	 after x.  */
+      for (y = x, np = 1;
+	   single_pred_p (y) && !VISITED_P (single_pred (y));
+	   y = single_pred (y))
+	np++;
+      for (y = x, i = n - np;
+	   single_pred_p (y) && !VISITED_P (single_pred (y));
+	   y = single_pred (y), i++)
+	{
+	  order[i] = y;
+	  MARK_VISITED (y);
 	}
+      order[i] = y;
+      MARK_VISITED (y);
+
+      gcc_assert (i == n - 1);
+      n -= np;
     }
+
+  sbitmap_free (visited);
+  gcc_assert (n == 0);
+  return order;
+
+#undef MARK_VISITED
+#undef VISITED_P
 }
 
 /* Return TRUE if block BB has no executable statements, otherwise return
@@ -324,11 +410,11 @@ conditional_replacement (basic_block cond_bb, basic_block middle_bb,
       if (!COMPARISON_CLASS_P (old_result))
 	return false;
 
-      new1 = build (TREE_CODE (old_result), TREE_TYPE (old_result),
-		    TREE_OPERAND (old_result, 0),
-		    TREE_OPERAND (old_result, 1));
+      new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
+		     TREE_OPERAND (old_result, 0),
+		     TREE_OPERAND (old_result, 1));
 
-      new1 = build (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
+      new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
     }
 
@@ -357,7 +443,7 @@ conditional_replacement (basic_block cond_bb, basic_block middle_bb,
       || (e1 == true_edge && integer_onep (arg1))
       || (e1 == false_edge && integer_zerop (arg1)))
     {
-      new = build (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
+      new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
     }
   else
     {
@@ -379,7 +465,7 @@ conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 	{
 	  tree temp = TREE_OPERAND (cond, 0);
 	  tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
-	  new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
+	  new = build2 (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 	  bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 	  cond = fold_convert (TREE_TYPE (result), new_var_1);
 	}
@@ -391,7 +477,7 @@ conditional_replacement (basic_block cond_bb, basic_block middle_bb,
 	  return false;
 	}
 
-      new = build (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
+      new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
     }
 
   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
@@ -482,6 +568,257 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
   return false;
 }
 
+/*  The function minmax_replacement does the main work of doing the minmax
+    replacement.  Return true if the replacement is done.  Otherwise return
+    false.
+    BB is the basic block where the replacement is going to be done on.  ARG0
+    is argument 0 from the PHI.  Likewise for ARG1.  */
+
+static bool
+minmax_replacement (basic_block cond_bb, basic_block middle_bb,
+		    basic_block phi_bb, edge e0, edge e1, tree phi,
+		    tree arg0, tree arg1)
+{
+  tree result, type;
+  tree cond, new;
+  edge true_edge, false_edge;
+  enum tree_code cmp, minmax, ass_code;
+  tree smaller, larger, arg_true, arg_false;
+  block_stmt_iterator bsi, bsi_from;
+
+  type = TREE_TYPE (PHI_RESULT (phi));
+
+  /* The optimization may be unsafe due to NaNs.  */
+  if (HONOR_NANS (TYPE_MODE (type)))
+    return false;
+
+  cond = COND_EXPR_COND (last_stmt (cond_bb));
+  cmp = TREE_CODE (cond);
+  result = PHI_RESULT (phi);
+
+  /* This transformation is only valid for order comparisons.  Record which
+     operand is smaller/larger if the result of the comparison is true.  */
+  if (cmp == LT_EXPR || cmp == LE_EXPR)
+    {
+      smaller = TREE_OPERAND (cond, 0);
+      larger = TREE_OPERAND (cond, 1);
+    }
+  else if (cmp == GT_EXPR || cmp == GE_EXPR)
+    {
+      smaller = TREE_OPERAND (cond, 1);
+      larger = TREE_OPERAND (cond, 0);
+    }
+  else
+    return false;
+
+  /* We need to know which is the true edge and which is the false
+      edge so that we know if have abs or negative abs.  */
+  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
+
+  /* Forward the edges over the middle basic block.  */
+  if (true_edge->dest == middle_bb)
+    true_edge = EDGE_SUCC (true_edge->dest, 0);
+  if (false_edge->dest == middle_bb)
+    false_edge = EDGE_SUCC (false_edge->dest, 0);
+
+  if (true_edge == e0)
+    {
+      gcc_assert (false_edge == e1);
+      arg_true = arg0;
+      arg_false = arg1;
+    }
+  else
+    {
+      gcc_assert (false_edge == e0);
+      gcc_assert (true_edge == e1);
+      arg_true = arg1;
+      arg_false = arg0;
+    }
+
+  if (empty_block_p (middle_bb))
+    {
+      if (operand_equal_for_phi_arg_p (arg_true, smaller)
+	  && operand_equal_for_phi_arg_p (arg_false, larger))
+	{
+	  /* Case
+	 
+	     if (smaller < larger)
+	     rslt = smaller;
+	     else
+	     rslt = larger;  */
+	  minmax = MIN_EXPR;
+	}
+      else if (operand_equal_for_phi_arg_p (arg_false, smaller)
+	       && operand_equal_for_phi_arg_p (arg_true, larger))
+	minmax = MAX_EXPR;
+      else
+	return false;
+    }
+  else
+    {
+      /* Recognize the following case, assuming d <= u:
+
+	 if (a <= u)
+	   b = MAX (a, d);
+	 x = PHI <b, u>
+
+	 This is equivalent to
+
+	 b = MAX (a, d);
+	 x = MIN (b, u);  */
+
+      tree assign = last_and_only_stmt (middle_bb);
+      tree lhs, rhs, op0, op1, bound;
+
+      if (!assign
+	  || TREE_CODE (assign) != MODIFY_EXPR)
+	return false;
+
+      lhs = TREE_OPERAND (assign, 0);
+      rhs = TREE_OPERAND (assign, 1);
+      ass_code = TREE_CODE (rhs);
+      if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
+	return false;
+      op0 = TREE_OPERAND (rhs, 0);
+      op1 = TREE_OPERAND (rhs, 1);
+
+      if (true_edge->src == middle_bb)
+	{
+	  /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
+	  if (!operand_equal_for_phi_arg_p (lhs, arg_true))
+	    return false;
+
+	  if (operand_equal_for_phi_arg_p (arg_false, larger))
+	    {
+	      /* Case
+
+		 if (smaller < larger)
+		   {
+		     r' = MAX_EXPR (smaller, bound)
+		   }
+		 r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
+	      if (ass_code != MAX_EXPR)
+		return false;
+
+	      minmax = MIN_EXPR;
+	      if (operand_equal_for_phi_arg_p (op0, smaller))
+		bound = op1;
+	      else if (operand_equal_for_phi_arg_p (op1, smaller))
+		bound = op0;
+	      else
+		return false;
+
+	      /* We need BOUND <= LARGER.  */
+	      if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
+						   bound, larger))))
+		return false;
+	    }
+	  else if (operand_equal_for_phi_arg_p (arg_false, smaller))
+	    {
+	      /* Case
+
+		 if (smaller < larger)
+		   {
+		     r' = MIN_EXPR (larger, bound)
+		   }
+		 r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
+	      if (ass_code != MIN_EXPR)
+		return false;
+
+	      minmax = MAX_EXPR;
+	      if (operand_equal_for_phi_arg_p (op0, larger))
+		bound = op1;
+	      else if (operand_equal_for_phi_arg_p (op1, larger))
+		bound = op0;
+	      else
+		return false;
+
+	      /* We need BOUND >= SMALLER.  */
+	      if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
+						   bound, smaller))))
+		return false;
+	    }
+	  else
+	    return false;
+	}
+      else
+	{
+	  /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
+	  if (!operand_equal_for_phi_arg_p (lhs, arg_false))
+	    return false;
+
+	  if (operand_equal_for_phi_arg_p (arg_true, larger))
+	    {
+	      /* Case
+
+		 if (smaller > larger)
+		   {
+		     r' = MIN_EXPR (smaller, bound)
+		   }
+		 r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
+	      if (ass_code != MIN_EXPR)
+		return false;
+
+	      minmax = MAX_EXPR;
+	      if (operand_equal_for_phi_arg_p (op0, smaller))
+		bound = op1;
+	      else if (operand_equal_for_phi_arg_p (op1, smaller))
+		bound = op0;
+	      else
+		return false;
+
+	      /* We need BOUND >= LARGER.  */
+	      if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
+						   bound, larger))))
+		return false;
+	    }
+	  else if (operand_equal_for_phi_arg_p (arg_true, smaller))
+	    {
+	      /* Case
+
+		 if (smaller > larger)
+		   {
+		     r' = MAX_EXPR (larger, bound)
+		   }
+		 r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
+	      if (ass_code != MAX_EXPR)
+		return false;
+
+	      minmax = MIN_EXPR;
+	      if (operand_equal_for_phi_arg_p (op0, larger))
+		bound = op1;
+	      else if (operand_equal_for_phi_arg_p (op1, larger))
+		bound = op0;
+	      else
+		return false;
+
+	      /* We need BOUND <= SMALLER.  */
+	      if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
+						   bound, smaller))))
+		return false;
+	    }
+	  else
+	    return false;
+	}
+
+      /* Move the statement from the middle block.  */
+      bsi = bsi_last (cond_bb);
+      bsi_from = bsi_last (middle_bb);
+      bsi_move_before (&bsi_from, &bsi);
+    }
+
+  /* Emit the statement to compute min/max.  */
+  result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
+  new = build2 (MODIFY_EXPR, type, result,
+		build2 (minmax, type, arg0, arg1));
+  SSA_NAME_DEF_STMT (result) = new;
+  bsi = bsi_last (cond_bb);
+  bsi_insert_before (&bsi, new, BSI_NEW_STMT);
+
+  replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
+  return true;
+}
+
 /*  The function absolute_replacement does the main work of doing the absolute
     replacement.  Return true if the replacement is done.  Otherwise return
     false.
@@ -497,9 +834,9 @@ abs_replacement (basic_block cond_bb, basic_block middle_bb,
   tree new, cond;
   block_stmt_iterator bsi;
   edge true_edge, false_edge;
-  tree assign = NULL;
+  tree assign;
   edge e;
-  tree rhs = NULL, lhs = NULL;
+  tree rhs, lhs;
   bool negate;
   enum tree_code cond_code;
 
@@ -510,57 +847,31 @@ abs_replacement (basic_block cond_bb, basic_block middle_bb,
 
   /* OTHER_BLOCK must have only one executable statement which must have the
      form arg0 = -arg1 or arg1 = -arg0.  */
-  bsi = bsi_start (middle_bb);
-  while (!bsi_end_p (bsi))
-    {
-      tree stmt = bsi_stmt (bsi);
-
-      /* Empty statements and labels are uninteresting.  */
-      if (TREE_CODE (stmt) == LABEL_EXPR
-          || IS_EMPTY_STMT (stmt))
-        {
-          bsi_next (&bsi);
-          continue;
-        }
-
-      /* If we found the assignment, but it was not the only executable
-	 statement in OTHER_BLOCK, then we can not optimize.  */
-      if (assign)
-	return false;
-
-      /* If we got here, then we have found the first executable statement
-	 in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
-	 arg1 = -arg0, then we can not optimize.  */
-      if (TREE_CODE (stmt) == MODIFY_EXPR)
-        {
-          lhs = TREE_OPERAND (stmt, 0);
-          rhs = TREE_OPERAND (stmt, 1);
-
-          if (TREE_CODE (rhs) == NEGATE_EXPR)
-            {
-              rhs = TREE_OPERAND (rhs, 0);
-
-              /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
-              if ((lhs == arg0 && rhs == arg1)
-		  || (lhs == arg1 && rhs == arg0))
-		{
-		  assign = stmt;
-		  bsi_next (&bsi);
-		}
-	      else
-		return false;
-            }
-	  else
-	    return false;
-        }
-      else
-	return false;
-    }
 
+  assign = last_and_only_stmt (middle_bb);
   /* If we did not find the proper negation assignment, then we can not
      optimize.  */
   if (assign == NULL)
     return false;
+      
+  /* If we got here, then we have found the only executable statement
+     in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
+     arg1 = -arg0, then we can not optimize.  */
+  if (TREE_CODE (assign) != MODIFY_EXPR)
+    return false;
+
+  lhs = TREE_OPERAND (assign, 0);
+  rhs = TREE_OPERAND (assign, 1);
+
+  if (TREE_CODE (rhs) != NEGATE_EXPR)
+    return false;
+
+  rhs = TREE_OPERAND (rhs, 0);
+              
+  /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
+  if (!(lhs == arg0 && rhs == arg1)
+      && !(lhs == arg1 && rhs == arg0))
+    return false;
 
   cond = COND_EXPR_COND (last_stmt (cond_bb));
   result = PHI_RESULT (phi);
@@ -607,8 +918,8 @@ abs_replacement (basic_block cond_bb, basic_block middle_bb,
     lhs = result;
 
   /* Build the modify expression with abs expression.  */
-  new = build (MODIFY_EXPR, TREE_TYPE (lhs),
-               lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
+  new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
+		lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
 
   bsi = bsi_last (cond_bb);
   bsi_insert_before (&bsi, new, BSI_NEW_STMT);
@@ -618,8 +929,8 @@ abs_replacement (basic_block cond_bb, basic_block middle_bb,
       /* Get the right BSI.  We want to insert after the recently
 	 added ABS_EXPR statement (which we know is the first statement
 	 in the block.  */
-      new = build (MODIFY_EXPR, TREE_TYPE (result),
-                   result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
+      new = build2 (MODIFY_EXPR, TREE_TYPE (result),
+		    result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
 
       bsi_insert_after (&bsi, new, BSI_NEW_STMT);
     }