[PATCH] Fold sqrt comparisons against constants (take 2)

[Roger Sayle <roger at www dot eyesopen dot com>]

Many thanks to all those who've commented on my original patch,
particularly Geoff's suggestions.  The revised patch below addresses
the overflow issues that have been raised.

The version now checks whether c*c overflows, i.e. that c2 becomes
+Inf either from the multiplication or through overflowing the type
of the comparison.  If which case, we now return either true or
false depending upon the operator.  I've also added "x >= 0" checks
when we need to worry about NaNs, and removed it when we don't.

The only remaining discrepancy is that "sqrt(+Inf) < +Inf" is
considered true with this transformation and false without.
I believe that this philosophical/metaphysical anomaly is
reasonable under -funsafe-math-optimizations :>


The following patch has been tested on i686-pc-linux-gnu, with a
full "make bootstrap", all languages except Ada and treelang, and
regression tested with a top-level "make -k check" with no new
failures.  I've also added DBL_MAX tests to the new test case.

Ok for mainline?


2003-03-18  Roger Sayle  <roger at eyesopen dot com>

	* fold-const.c (fold_mathfn_compare): New function to simplify
	comparisons against built-in math functions.  Fold comparisons
	of sqrt against constants.
	(fold): Call fold_mathfn_compare when appropriate.

	* gcc.dg/builtins-6.c: New test case.


Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.238
diff -c -3 -p -r1.238 fold-const.c
*** fold-const.c	22 Feb 2003 04:16:16 -0000	1.238
--- fold-const.c	18 Mar 2003 14:42:39 -0000
*************** static int count_cond		PARAMS ((tree, in
*** 112,117 ****
--- 112,119 ----
  static tree fold_binary_op_with_conditional_arg
    PARAMS ((enum tree_code, tree, tree, tree, int));
  static bool fold_real_zero_addition_p	PARAMS ((tree, tree, int));
+ static tree fold_mathfn_compare	PARAMS ((enum built_in_function,
+ 					 enum tree_code, tree, tree, tree));

  /* The following constants represent a bit based encoding of GCC's
     comparison operators.  This encoding simplifies transformations
*************** fold_real_zero_addition_p (type, addend,
*** 4661,4666 ****
--- 4663,4774 ----
    return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
  }

+ /* Subroutine of fold() that checks comparisons of built-in math
+    functions against real constants.
+
+    FCODE is the DECL_FUNCTION_CODE of the built-in, CODE is the comparison
+    operator: EQ_EXPR, NE_EXPR, GT_EXPR, LT_EXPR, GE_EXPR or LE_EXPR.  TYPE
+    is the type of the result and ARG0 and ARG1 are the operands of the
+    comparison.  ARG1 must be a TREE_REAL_CST.
+
+    The function returns the constant folded tree if a simplification
+    can be made, and NULL_TREE otherwise.  */
+
+ static tree
+ fold_mathfn_compare (fcode, code, type, arg0, arg1)
+      enum built_in_function fcode;
+      enum tree_code code;
+      tree type, arg0, arg1;
+ {
+   REAL_VALUE_TYPE c;
+
+   if (fcode == BUILT_IN_SQRT
+       || fcode == BUILT_IN_SQRTF
+       || fcode == BUILT_IN_SQRTL)
+     {
+       tree arg = TREE_VALUE (TREE_OPERAND (arg0, 1));
+       enum machine_mode mode = TYPE_MODE (TREE_TYPE (arg0));
+
+       c = TREE_REAL_CST (arg1);
+       if (REAL_VALUE_NEGATIVE (c))
+ 	{
+ 	  /* sqrt(x) < y is always false, if y is negative.  */
+ 	  if (code == EQ_EXPR || code == LT_EXPR || code == LE_EXPR)
+ 	    return omit_one_operand (type,
+ 				     convert (type, integer_zero_node),
+ 				     arg);
+
+ 	  /* sqrt(x) > y is always true, if y is negative and we
+ 	     don't care about NaNs, i.e. negative values of x.  */
+ 	  if (! HONOR_NANS (mode))
+ 	    return omit_one_operand (type,
+ 				     convert (type, integer_one_node),
+ 				     arg);
+
+ 	  /* sqrt(x) > y is the same as x >= 0, if y is negative.  */
+ 	  return fold (build (GE_EXPR, type, arg,
+ 			      build_real (TREE_TYPE (arg), dconst0)));
+ 	}
+       else if (code == GT_EXPR || code == GE_EXPR)
+ 	{
+ 	  REAL_VALUE_TYPE c2;
+
+ 	  REAL_ARITHMETIC (c2, MULT_EXPR, c, c);
+ 	  real_convert (&c2, mode, &c2);
+
+ 	  /* sqrt(x) > y, where y is very large is always false.  */
+ 	  if (REAL_VALUE_ISINF (c2))
+ 	    return omit_one_operand (type,
+ 				     convert (type, integer_zero_node),
+ 				     arg);
+
+ 	  /* sqrt(x) > c is the same as x > c*c.  */
+ 	  return fold (build (code, type, arg,
+ 			      build_real (TREE_TYPE (arg), c2)));
+ 	}
+       else if (code == LT_EXPR || code == LE_EXPR)
+ 	{
+ 	  REAL_VALUE_TYPE c2;
+
+ 	  REAL_ARITHMETIC (c2, MULT_EXPR, c, c);
+ 	  real_convert (&c2, mode, &c2);
+
+ 	  /* sqrt(x) < y, where y is a very large value is always
+ 	     true, if we don't care about NaNs.  */
+ 	  if (REAL_VALUE_ISINF (c2) && !HONOR_NANS (mode))
+ 	    return omit_one_operand (type,
+ 				     convert (type, integer_one_node),
+ 				     arg);
+
+ 	  /* sqrt(x) < y is the same as x >= 0 when y is very large.  */
+ 	  if (REAL_VALUE_ISINF (c2))
+ 	    return fold (build (GE_EXPR, type, arg,
+ 				build_real (TREE_TYPE (arg), dconst0)));
+
+ 	  /* sqrt(x) < c is the same as x < c*c, if we ignore NaNs.  */
+ 	  if (! HONOR_NANS (mode))
+ 	    return fold (build (code, type, arg,
+ 				build_real (TREE_TYPE (arg), c2)));
+
+ 	  /* sqrt(x) < c is the same as x >= 0 && x < c*c.  */
+ 	  if ((*lang_hooks.decls.global_bindings_p) () == 0
+ 	      && ! contains_placeholder_p (arg))
+ 	    {
+ 	      arg = save_expr (arg);
+ 	      return fold (build (TRUTH_ANDIF_EXPR, type,
+ 				  fold (build (GE_EXPR, type, arg,
+ 					       build_real (TREE_TYPE (arg),
+ 							   dconst0))),
+ 				  fold (build (code, type, arg,
+ 					       build_real (TREE_TYPE (arg),
+ 							   c2)))));
+ 	    }
+ 	}
+     }
+
+   return NULL_TREE;
+ }
+

  /* Perform constant folding and related simplification of EXPR.
     The related simplifications include x*1 => x, x*0 => 0, etc.,
*************** fold (expr)
*** 6193,6198 ****
--- 6301,6321 ----
  					  arg1, TREE_OPERAND (arg0, 1), 0))
  	      && ! TREE_CONSTANT_OVERFLOW (tem))
  	    return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
+
+ 	  /* Fold comparisons against built-in math functions.  */
+ 	  if (TREE_CODE (arg1) == REAL_CST
+ 	      && flag_unsafe_math_optimizations
+ 	      && ! flag_errno_math)
+ 	    {
+ 	      enum built_in_function fcode = builtin_mathfn_code (arg0);
+
+ 	      if (fcode != END_BUILTINS)
+ 		{
+ 		  tem = fold_mathfn_compare (fcode, code, type, arg0, arg1);
+ 		  if (tem != NULL_TREE)
+ 		    return tem;
+ 		}
+ 	    }
  	}

        /* Convert foo++ == CONST into ++foo == CONST + INCR.


/* Copyright (C) 2003  Free Software Foundation.

   Verify that constant folding comparisons against built-in math functions
   don't cause any problems for the compiler, and produce expected results.

   Written by Roger Sayle, 15th March 2003.  */

/* { dg-do run } */
/* { dg-options "-O2 -ffast-math" } */

#include <float.h>

extern void abort (void);
extern double sqrt (double);

int test1(double x)
{
  return sqrt(x) < -9.0;
}

int test2(double x)
{
  return sqrt(x) > -9.0;
}

int test3(double x)
{
  return sqrt(x) < 9.0;
}

int test4(double x)
{
  return sqrt(x) > 9.0;
}

int test5(double x)
{
  return sqrt(x) < DBL_MAX;
}

int test6(double x)
{
  return sqrt(x) > DBL_MAX;
}

int main()
{
  double x;

  x = 80.0;
  if (test1 (x))
    abort ();
  if (! test2 (x))
    abort ();
  if (! test3 (x))
    abort ();
  if (test4 (x))
    abort ();
  if (! test5 (x))
    abort ();
  if (test6 (x))
    abort ();

  x = 100.0;
  if (test1 (x))
    abort ();
  if (! test2 (x))
    abort ();
  if (test3 (x))
    abort ();
  if (! test4 (x))
    abort ();
  if (! test5 (x))
    abort ();
  if (test6 (x))
    abort ();

  return 0;
}


Roger
--
Roger Sayle,                         E-mail: roger at eyesopen dot com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833