This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Constant folding of trunc, floor and ceil builtins
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 28 Jun 2003 20:48:55 -0600 (MDT)
- Subject: [PATCH] Constant folding of trunc, floor and ceil builtins
The following patch implement constant folding optimizations of the
integer rounding functions trunc, floor and ceil and their float and
long double variants, truncf, truncl, floorf, floorl, ceilf and ceill.
The main improvement is the addition of real_trunc, real_floor and
real_ceil in real.[ch] that implement their respective functions on
GCC's internal floating point representation. This allows us to
evaluate rounding of a constant argument, e.g. floor(1.5), at compile
time. Care has to be taken that floor and ceil may set errno if
given NaN.
The next optimization is that all of the integer rounding functions
are idempotent, i.e. floor (floor (x)) produces the same result as
just floor(x). It is always safe to apply this optimization as
errno will be correctly set by the single invocation.
The expanding on this theme, the integer rounding functions may be
optimized away if the argument is known to be integer valued. For
example floor (ceil (x)) == ceil (x) and ceil (floor (x)) == floor(x).
To implement, this I've added a new predicate integer_valued_real_p
that is used to test whether a floating point expr is already rounded
to an integer. This also catches the following two cases for example:
double foo(int x)
{
return floor(x);
}
double bar(double x)
{
return floor(2.0*trunc(x)+3.0);
}
Finally, whilst developing integer_valued_real_p, I noticed that
there were some easy missing cases in tree_nonnegative_expr_p from
fold-const.c that are also added by this patch.
The following patch has been tested on i686-pc-linux-gnu, with a
full "make bootstrap", all languages except treelang, and regression
tested with a top-level "make -k check" with no new failures.
Ok for mainline?
2003-06-28 Roger Sayle <roger@eyesopen.com>
* real.c (real_trunc, real_floor, real_ceil): New functions
to implement trunc, floor and ceil respectively.
* real.h (real_trunc, real_floor, real_ceil): Prototype here.
* builtins.c (integer_valued_real_p): New function to test if
a floating point expression has an integer valued result.
(fold_trunc_transparent_mathfn): Optimize foo(foo(x)) as
foo(x) where foo is an integer rounding function. Similarly,
optimize foo(bar(x)) as bar(x), and foo((double)(int)x) as
(double)(int)x when both foo and bar are integer rounding
functions and we don't need to honor errno.
(fold_builtin_trunc, fold_builtin_floor, fold_builtin_ceil):
New functions to fold trunc, floor and ceil.
(fold_builtin): Use fold_builtin_trunc to fold BUILT_IN_TRUNC*,
fold_builtin_floor to fold BUILT_IN_FLOOR* and fold_builtin_ceil
to fold BUILT_IN_CEIL*.
* fold-const.c (tree_expr_nonnegative_p): Handle FLOAT_EXPR and
the remaining integer rounding functions.
* gcc.dg/builtins-25.c: New testcase.
* gcc.dg/builtins-26.c: New testcase.
Index: real.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/real.c,v
retrieving revision 1.121
diff -c -3 -p -r1.121 real.c
*** real.c 25 Jun 2003 00:11:29 -0000 1.121
--- real.c 28 Jun 2003 23:45:22 -0000
*************** real_powi (r, mode, x, n)
*** 4748,4750 ****
--- 4748,4796 ----
return inexact;
}
+ /* Round X to the nearest integer not larger in absolute value, i.e.
+ towards zero, placing the result in R in mode MODE. */
+
+ void
+ real_trunc (r, mode, x)
+ REAL_VALUE_TYPE *r;
+ enum machine_mode mode;
+ const REAL_VALUE_TYPE *x;
+ {
+ do_fix_trunc (r, x);
+ if (mode != VOIDmode)
+ real_convert (r, mode, r);
+ }
+
+ /* Round X to the largest integer not greater in value, i.e. round
+ down, placing the result in R in mode MODE. */
+
+ void
+ real_floor (r, mode, x)
+ REAL_VALUE_TYPE *r;
+ enum machine_mode mode;
+ const REAL_VALUE_TYPE *x;
+ {
+ do_fix_trunc (r, x);
+ if (! real_identical (r, x) && r->sign)
+ do_add (r, r, &dconstm1, 0);
+ if (mode != VOIDmode)
+ real_convert (r, mode, r);
+ }
+
+ /* Round X to the smallest integer not less then argument, i.e. round
+ up, placing the result in R in mode MODE. */
+
+ void
+ real_ceil (r, mode, x)
+ REAL_VALUE_TYPE *r;
+ enum machine_mode mode;
+ const REAL_VALUE_TYPE *x;
+ {
+ do_fix_trunc (r, x);
+ if (! real_identical (r, x) && ! r->sign)
+ do_add (r, r, &dconst1, 0);
+ if (mode != VOIDmode)
+ real_convert (r, mode, r);
+ }
+
Index: real.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/real.h,v
retrieving revision 1.68
diff -c -3 -p -r1.68 real.h
*** real.h 25 Jun 2003 00:11:32 -0000 1.68
--- real.h 28 Jun 2003 23:45:22 -0000
*************** extern bool real_powi PARAMS ((REAL_VA
*** 375,378 ****
--- 375,389 ----
const REAL_VALUE_TYPE *,
HOST_WIDE_INT));
+ /* Standard round to integer value functions. */
+ extern void real_trunc PARAMS ((REAL_VALUE_TYPE *,
+ enum machine_mode,
+ const REAL_VALUE_TYPE *));
+ extern void real_floor PARAMS ((REAL_VALUE_TYPE *,
+ enum machine_mode,
+ const REAL_VALUE_TYPE *));
+ extern void real_ceil PARAMS ((REAL_VALUE_TYPE *,
+ enum machine_mode,
+ const REAL_VALUE_TYPE *));
+
#endif /* ! GCC_REAL_H */
Index: builtins.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/builtins.c,v
retrieving revision 1.224
diff -c -3 -p -r1.224 builtins.c
*** builtins.c 27 Jun 2003 02:50:14 -0000 1.224
--- builtins.c 28 Jun 2003 23:45:23 -0000
*************** static tree fold_builtin_classify_type (
*** 149,160 ****
--- 149,164 ----
static tree fold_builtin_inf (tree, int);
static tree fold_builtin_nan (tree, tree, int);
static int validate_arglist (tree, ...);
+ static bool integer_valued_real_p (tree);
static tree fold_trunc_transparent_mathfn (tree);
static bool readonly_data_expr (tree);
static rtx expand_builtin_fabs (tree, rtx, rtx);
static rtx expand_builtin_cabs (tree, rtx);
static void init_builtin_dconsts (void);
static tree fold_builtin_cabs (tree, tree, tree);
+ static tree fold_builtin_trunc (tree);
+ static tree fold_builtin_floor (tree);
+ static tree fold_builtin_ceil (tree);
/* Initialize mathematical constants for constant folding builtins.
These constants need to be given to at least 160 bits precision. */
*************** fold_builtin_nan (tree arglist, tree typ
*** 5303,5321 ****
return build_real (type, real);
}
! /* EXP is assumed to me builtin call where truncation can be propagated
across (for instance floor((double)f) == (double)floorf (f).
Do the transformation. */
static tree
fold_trunc_transparent_mathfn (tree exp)
{
tree fndecl = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
tree arglist = TREE_OPERAND (exp, 1);
enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
! if (optimize && validate_arglist (arglist, REAL_TYPE, VOID_TYPE))
{
! tree arg0 = strip_float_extensions (TREE_VALUE (arglist));
tree ftype = TREE_TYPE (exp);
tree newtype = TREE_TYPE (arg0);
tree decl;
--- 5307,5424 ----
return build_real (type, real);
}
! /* Return true if the floating point expression T has an integer value.
! We also allow +Inf, -Inf and NaN to be considered integer values. */
!
! static bool
! integer_valued_real_p (tree t)
! {
! switch (TREE_CODE (t))
! {
! case FLOAT_EXPR:
! return true;
!
! case ABS_EXPR:
! case SAVE_EXPR:
! case NON_LVALUE_EXPR:
! return integer_valued_real_p (TREE_OPERAND (t, 0));
!
! case COMPOUND_EXPR:
! case MODIFY_EXPR:
! case BIND_EXPR:
! return integer_valued_real_p (TREE_OPERAND (t, 1));
!
! case PLUS_EXPR:
! case MINUS_EXPR:
! case MULT_EXPR:
! case MIN_EXPR:
! case MAX_EXPR:
! return integer_valued_real_p (TREE_OPERAND (t, 0))
! && integer_valued_real_p (TREE_OPERAND (t, 1));
!
! case COND_EXPR:
! return integer_valued_real_p (TREE_OPERAND (t, 1))
! && integer_valued_real_p (TREE_OPERAND (t, 2));
!
! case REAL_CST:
! if (! TREE_CONSTANT_OVERFLOW (t))
! {
! REAL_VALUE_TYPE c, cint;
!
! c = TREE_REAL_CST (t);
! real_trunc (&cint, TYPE_MODE (TREE_TYPE (t)), &c);
! return real_identical (&c, &cint);
! }
!
! case NOP_EXPR:
! {
! tree type = TREE_TYPE (TREE_OPERAND (t, 0));
! if (TREE_CODE (type) == INTEGER_TYPE)
! return true;
! if (TREE_CODE (type) == REAL_TYPE)
! return integer_valued_real_p (TREE_OPERAND (t, 0));
! break;
! }
!
! case CALL_EXPR:
! switch (builtin_mathfn_code (t))
! {
! case BUILT_IN_CEIL:
! case BUILT_IN_CEILF:
! case BUILT_IN_CEILL:
! case BUILT_IN_FLOOR:
! case BUILT_IN_FLOORF:
! case BUILT_IN_FLOORL:
! case BUILT_IN_NEARBYINT:
! case BUILT_IN_NEARBYINTF:
! case BUILT_IN_NEARBYINTL:
! case BUILT_IN_ROUND:
! case BUILT_IN_ROUNDF:
! case BUILT_IN_ROUNDL:
! case BUILT_IN_TRUNC:
! case BUILT_IN_TRUNCF:
! case BUILT_IN_TRUNCL:
! return true;
!
! default:
! break;
! }
! break;
!
! default:
! break;
! }
! return false;
! }
!
! /* EXP is assumed to be builtin call where truncation can be propagated
across (for instance floor((double)f) == (double)floorf (f).
Do the transformation. */
+
static tree
fold_trunc_transparent_mathfn (tree exp)
{
tree fndecl = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
tree arglist = TREE_OPERAND (exp, 1);
enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
+ tree arg;
! if (! validate_arglist (arglist, REAL_TYPE, VOID_TYPE))
! return 0;
!
! arg = TREE_VALUE (arglist);
! /* Integer rounding functions are idempotent. */
! if (fcode == builtin_mathfn_code (arg))
! return arg;
!
! /* If argument is already integer valued, and we don't need to worry
! about setting errno, there's no need to perform rounding. */
! if (! flag_errno_math && integer_valued_real_p (arg))
! return arg;
!
! if (optimize)
{
! tree arg0 = strip_float_extensions (arg);
tree ftype = TREE_TYPE (exp);
tree newtype = TREE_TYPE (arg0);
tree decl;
*************** fold_builtin_cabs (tree fndecl, tree arg
*** 5417,5422 ****
--- 5520,5616 ----
return NULL_TREE;
}
+ /* Fold function call to builtin trunc, truncf or truncl. Return
+ NULL_TREE if no simplification can be made. */
+
+ static tree
+ fold_builtin_trunc (tree exp)
+ {
+ tree arglist = TREE_OPERAND (exp, 1);
+ tree arg;
+
+ if (! validate_arglist (arglist, REAL_TYPE, VOID_TYPE))
+ return 0;
+
+ /* Optimize trunc of constant value. */
+ arg = TREE_VALUE (arglist);
+ if (TREE_CODE (arg) == REAL_CST && ! TREE_CONSTANT_OVERFLOW (arg))
+ {
+ REAL_VALUE_TYPE r, x;
+ tree type = TREE_TYPE (exp);
+
+ x = TREE_REAL_CST (arg);
+ real_trunc (&r, TYPE_MODE (type), &x);
+ return build_real (type, r);
+ }
+
+ return fold_trunc_transparent_mathfn (exp);
+ }
+
+ /* Fold function call to builtin floor, floorf or floorl. Return
+ NULL_TREE if no simplification can be made. */
+
+ static tree
+ fold_builtin_floor (tree exp)
+ {
+ tree arglist = TREE_OPERAND (exp, 1);
+ tree arg;
+
+ if (! validate_arglist (arglist, REAL_TYPE, VOID_TYPE))
+ return 0;
+
+ /* Optimize floor of constant value. */
+ arg = TREE_VALUE (arglist);
+ if (TREE_CODE (arg) == REAL_CST && ! TREE_CONSTANT_OVERFLOW (arg))
+ {
+ REAL_VALUE_TYPE x;
+
+ x = TREE_REAL_CST (arg);
+ if (! REAL_VALUE_ISNAN (x) || ! flag_errno_math)
+ {
+ tree type = TREE_TYPE (exp);
+ REAL_VALUE_TYPE r;
+
+ real_floor (&r, TYPE_MODE (type), &x);
+ return build_real (type, r);
+ }
+ }
+
+ return fold_trunc_transparent_mathfn (exp);
+ }
+
+ /* Fold function call to builtin ceil, ceilf or ceill. Return
+ NULL_TREE if no simplification can be made. */
+
+ static tree
+ fold_builtin_ceil (tree exp)
+ {
+ tree arglist = TREE_OPERAND (exp, 1);
+ tree arg;
+
+ if (! validate_arglist (arglist, REAL_TYPE, VOID_TYPE))
+ return 0;
+
+ /* Optimize ceil of constant value. */
+ arg = TREE_VALUE (arglist);
+ if (TREE_CODE (arg) == REAL_CST && ! TREE_CONSTANT_OVERFLOW (arg))
+ {
+ REAL_VALUE_TYPE x;
+
+ x = TREE_REAL_CST (arg);
+ if (! REAL_VALUE_ISNAN (x) || ! flag_errno_math)
+ {
+ tree type = TREE_TYPE (exp);
+ REAL_VALUE_TYPE r;
+
+ real_ceil (&r, TYPE_MODE (type), &x);
+ return build_real (type, r);
+ }
+ }
+
+ return fold_trunc_transparent_mathfn (exp);
+ }
+
/* Used by constant folding to eliminate some builtin calls early. EXP is
the CALL_EXPR of a call to a builtin function. */
*************** fold_builtin (tree exp)
*** 5874,5885 ****
--- 6068,6085 ----
case BUILT_IN_FLOOR:
case BUILT_IN_FLOORF:
case BUILT_IN_FLOORL:
+ return fold_builtin_floor (exp);
+
case BUILT_IN_CEIL:
case BUILT_IN_CEILF:
case BUILT_IN_CEILL:
+ return fold_builtin_ceil (exp);
+
case BUILT_IN_TRUNC:
case BUILT_IN_TRUNCF:
case BUILT_IN_TRUNCL:
+ return fold_builtin_trunc (exp);
+
case BUILT_IN_ROUND:
case BUILT_IN_ROUNDF:
case BUILT_IN_ROUNDL:
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.267
diff -c -3 -p -r1.267 fold-const.c
*** fold-const.c 26 Jun 2003 10:37:33 -0000 1.267
--- fold-const.c 28 Jun 2003 23:45:24 -0000
*************** tree_expr_nonnegative_p (t)
*** 8175,8180 ****
--- 8175,8182 ----
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
case NON_LVALUE_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
+ case FLOAT_EXPR:
+ return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
case RTL_EXPR:
return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
*************** tree_expr_nonnegative_p (t)
*** 8211,8216 ****
--- 8213,8227 ----
case BUILT_IN_FLOOR:
case BUILT_IN_FLOORF:
case BUILT_IN_FLOORL:
+ case BUILT_IN_NEARBYINT:
+ case BUILT_IN_NEARBYINTF:
+ case BUILT_IN_NEARBYINTL:
+ case BUILT_IN_ROUND:
+ case BUILT_IN_ROUNDF:
+ case BUILT_IN_ROUNDL:
+ case BUILT_IN_TRUNC:
+ case BUILT_IN_TRUNCF:
+ case BUILT_IN_TRUNCL:
return tree_expr_nonnegative_p (TREE_VALUE (arglist));
case BUILT_IN_POW:
/* Copyright (C) 2003 Free Software Foundation.
Check that constant folding of built-in math functions doesn't
break anything and produces the expected results.
Written by Roger Sayle, 28th June 2003. */
/* { dg-do link } */
/* { dg-options "-O2" } */
extern void link_error(void);
extern double trunc(double);
extern double floor(double);
extern double ceil(double);
extern float truncf(float);
extern float floorf(float);
extern float ceilf(float);
extern long double truncl(long double);
extern long double floorl(long double);
extern long double ceill(long double);
void test()
{
if (trunc (0.0) != 0.0)
link_error ();
if (floor (0.0) != 0.0)
link_error ();
if (ceil (0.0) != 0.0)
link_error ();
if (trunc (6.0) != 6.0)
link_error ();
if (floor (6.0) != 6.0)
link_error ();
if (ceil (6.0) != 6.0)
link_error ();
if (trunc (-8.0) != -8.0)
link_error ();
if (floor (-8.0) != -8.0)
link_error ();
if (ceil (-8.0) != -8.0)
link_error ();
if (trunc (3.2) != 3.0)
link_error ();
if (floor (3.2) != 3.0)
link_error ();
if (ceil (3.2) != 4.0)
link_error ();
if (trunc (-2.8) != -2.0)
link_error ();
if (floor (-2.8) != -3.0)
link_error ();
if (ceil (-2.8) != -2.0)
link_error ();
if (trunc (0.01) != 0.0)
link_error ();
if (floor (0.01) != 0.0)
link_error ();
if (ceil (0.01) != 1.0)
link_error ();
if (trunc (-0.7) != 0.0)
link_error ();
if (floor (-0.7) != -1.0)
link_error ();
if (ceil (-0.7) != 0.0)
link_error ();
}
void testf()
{
if (truncf (0.0f) != 0.0f)
link_error ();
if (floorf (0.0f) != 0.0f)
link_error ();
if (ceilf (0.0f) != 0.0f)
link_error ();
if (truncf (6.0f) != 6.0f)
link_error ();
if (floorf (6.0f) != 6.0f)
link_error ();
if (ceilf (6.0f) != 6.0f)
link_error ();
if (truncf (-8.0f) != -8.0f)
link_error ();
if (floorf (-8.0f) != -8.0f)
link_error ();
if (ceilf (-8.0f) != -8.0f)
link_error ();
if (truncf (3.2f) != 3.0f)
link_error ();
if (floorf (3.2f) != 3.0f)
link_error ();
if (ceilf (3.2f) != 4.0f)
link_error ();
if (truncf (-2.8f) != -2.0f)
link_error ();
if (floorf (-2.8f) != -3.0f)
link_error ();
if (ceilf (-2.8f) != -2.0f)
link_error ();
if (truncf (0.01f) != 0.0f)
link_error ();
if (floorf (0.01f) != 0.0f)
link_error ();
if (ceilf (0.01f) != 1.0f)
link_error ();
if (truncf (-0.7f) != 0.0f)
link_error ();
if (floorf (-0.7f) != -1.0f)
link_error ();
if (ceilf (-0.7f) != 0.0f)
link_error ();
}
void testl()
{
if (truncl (0.0l) != 0.0l)
link_error ();
if (floorl (0.0l) != 0.0l)
link_error ();
if (ceill (0.0l) != 0.0l)
link_error ();
if (truncl (6.0l) != 6.0l)
link_error ();
if (floorl (6.0l) != 6.0l)
link_error ();
if (ceill (6.0l) != 6.0l)
link_error ();
if (truncl (-8.0l) != -8.0l)
link_error ();
if (floorl (-8.0l) != -8.0l)
link_error ();
if (ceill (-8.0l) != -8.0l)
link_error ();
if (truncl (3.2l) != 3.0l)
link_error ();
if (floorl (3.2l) != 3.0l)
link_error ();
if (ceill (3.2l) != 4.0l)
link_error ();
if (truncl (-2.8l) != -2.0l)
link_error ();
if (floorl (-2.8l) != -3.0l)
link_error ();
if (ceill (-2.8l) != -2.0l)
link_error ();
if (truncl (0.01l) != 0.0l)
link_error ();
if (floorl (0.01l) != 0.0l)
link_error ();
if (ceill (0.01l) != 1.0l)
link_error ();
if (truncl (-0.7l) != 0.0l)
link_error ();
if (floorl (-0.7l) != -1.0l)
link_error ();
if (ceill (-0.7l) != 0.0l)
link_error ();
}
int main()
{
test ();
testf ();
testl ();
return 0;
}
/* Copyright (C) 2003 Free Software Foundation.
Check that constant folding of built-in math functions doesn't
break anything and produces the expected results.
Written by Roger Sayle, 28th June 2003. */
/* { dg-do link } */
/* { dg-options "-O2 -ffast-math" } */
extern void link_error(void);
extern double trunc(double);
extern double floor(double);
extern double ceil(double);
extern float truncf(float);
extern float floorf(float);
extern float ceilf(float);
extern long double truncl(long double);
extern long double floorl(long double);
extern long double ceill(long double);
void test(double x)
{
if (trunc (trunc (x)) != trunc (x))
link_error ();
if (trunc (floor (x)) != floor (x))
link_error ();
if (trunc (ceil (x)) != ceil (x))
link_error ();
if (floor (trunc (x)) != trunc (x))
link_error ();
if (floor (floor (x)) != floor (x))
link_error ();
if (floor (ceil (x)) != ceil (x))
link_error ();
if (ceil (trunc (x)) != trunc (x))
link_error ();
if (ceil (floor (x)) != floor (x))
link_error ();
if (ceil (ceil (x)) != ceil (x))
link_error ();
}
void testf(float x)
{
if (truncf (truncf (x)) != truncf (x))
link_error ();
if (truncf (floorf (x)) != floorf (x))
link_error ();
if (truncf (ceilf (x)) != ceilf (x))
link_error ();
if (floorf (truncf (x)) != truncf (x))
link_error ();
if (floorf (floorf (x)) != floorf (x))
link_error ();
if (floorf (ceilf (x)) != ceilf (x))
link_error ();
if (ceilf (truncf (x)) != truncf (x))
link_error ();
if (ceilf (floorf (x)) != floorf (x))
link_error ();
if (ceilf (ceilf (x)) != ceilf (x))
link_error ();
}
void testl(long double x)
{
if (truncl (truncl (x)) != truncl (x))
link_error ();
if (truncl (floorl (x)) != floorl (x))
link_error ();
if (truncl (ceill (x)) != ceill (x))
link_error ();
if (floorl (truncl (x)) != truncl (x))
link_error ();
if (floorl (floorl (x)) != floorl (x))
link_error ();
if (floorl (ceill (x)) != ceill (x))
link_error ();
if (ceill (truncl (x)) != truncl (x))
link_error ();
if (ceill (floorl (x)) != floorl (x))
link_error ();
if (ceill (ceill (x)) != ceill (x))
link_error ();
}
int main()
{
test (3.2);
testf (3.2f);
testl (3.2l);
return 0;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.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