This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Optimize memcmp builtin for length zero or one
- From: Roger Sayle <roger at eyesopen dot com>
- To: <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 3 Dec 2001 20:48:30 -0700 (MST)
- Subject: [PATCH] Optimize memcmp builtin for length zero or one
The core of this patch optimizes expand_builtin_memcmp when the
length argument can be determined to be constant zero or one. For
zero, the generated code evaluates the side effects of the remaining
arguments and always returns zero. For constant one, the generated
code is reduced to *((const uchar*)arg1) - *((const uchar*)arg2).
The patch is the size it is because this change led to several other
minor improvements. The first is that expand_builtin_memcmp now
always exists (rather than being conditional on HAVE_cmpstrsi).
This in turn simplifies its callers, leading to a change of
indentation. These functions now also take the usual TARGET and
MODE parameters.
I also took the opportunity to correct the way that an internal call
to the builtins memcpy and memcmp were generated. Previously, if
the an inline implementation of memcpy or memcmp was not generated
for whatever reason the entire optimization was aborted. Now the
optimization is preserved with a call to the library function. For
example, strcpy(ptr,"foobar") is converted to memcpy(ptr,"foobar",7)
even if the memcpy can't be inlined, for example due to checking
memory usage.
Tested with bootstraps on i686-pc-cygwin and i686-pc-linux-gnu, and
"make -k check" on the later, with no new regressions. This patch
also includes a tescase, gcc.c-torture/execute/string-opt-15.c. The
file string-opt-14.c is associated with an earlier patch awaiting
approval.
Ok for mainline?
2001-12-01 Roger Sayle <roger@eyesopen.com>
* builtins.c (expand_builtin_memcmp): No longer conditional on
HAVE_cmpstrsi. Take an additional mode parameter. Optimize
the cases where len is either constant zero or one.
(expand_builtin_strcpy): Additional arguments TARGET and MODE.
Optimize to call to memcpy, even if the memcpy isn't inlined.
(expand_builtin_strncpy): Optimize to call memcpy, even if the
memcpy isn't inlined.
(expand_builtin_strcmp, expand_builtin_strncmp): Always attempt
to optimize to a call to memcmp.
(expand_builtin): expand_builtin_memcmp can always be called,
and pass the required parameters to expand_builtin_memcmp and
expand_builtin_strcpy.
* gcc.c-torture/execute/string-opt-15.c: New test case.
*** gcc/gcc/builtins.c Sat Nov 17 14:16:52 2001
--- patch/gcc/builtins.c Sun Dec 2 21:07:14 2001
*************** static rtx expand_builtin_next_arg PARAM
*** 100,108 ****
static rtx expand_builtin_va_start PARAMS ((int, tree));
static rtx expand_builtin_va_end PARAMS ((tree));
static rtx expand_builtin_va_copy PARAMS ((tree));
! #ifdef HAVE_cmpstrsi
! static rtx expand_builtin_memcmp PARAMS ((tree, tree, rtx));
! #endif
static rtx expand_builtin_strcmp PARAMS ((tree, rtx,
enum machine_mode));
static rtx expand_builtin_strncmp PARAMS ((tree, rtx,
--- 100,107 ----
static rtx expand_builtin_va_start PARAMS ((int, tree));
static rtx expand_builtin_va_end PARAMS ((tree));
static rtx expand_builtin_va_copy PARAMS ((tree));
! static rtx expand_builtin_memcmp PARAMS ((tree, tree, rtx,
! enum machine_mode));
static rtx expand_builtin_strcmp PARAMS ((tree, rtx,
enum machine_mode));
static rtx expand_builtin_strncmp PARAMS ((tree, rtx,
*************** static rtx expand_builtin_strspn PARAMS
*** 118,124 ****
static rtx expand_builtin_strcspn PARAMS ((tree, rtx,
enum machine_mode));
static rtx expand_builtin_memcpy PARAMS ((tree));
! static rtx expand_builtin_strcpy PARAMS ((tree));
static rtx builtin_strncpy_read_str PARAMS ((PTR, HOST_WIDE_INT,
enum machine_mode));
static rtx expand_builtin_strncpy PARAMS ((tree, rtx,
--- 117,124 ----
static rtx expand_builtin_strcspn PARAMS ((tree, rtx,
enum machine_mode));
static rtx expand_builtin_memcpy PARAMS ((tree));
! static rtx expand_builtin_strcpy PARAMS ((tree, rtx,
! enum machine_mode));
static rtx builtin_strncpy_read_str PARAMS ((PTR, HOST_WIDE_INT,
enum machine_mode));
static rtx expand_builtin_strncpy PARAMS ((tree, rtx,
*************** expand_builtin_memcpy (arglist)
*** 1911,1940 ****
if we failed the caller should emit a normal call. */
static rtx
! expand_builtin_strcpy (exp)
tree exp;
{
tree arglist = TREE_OPERAND (exp, 1);
! rtx result;
if (!validate_arglist (arglist, POINTER_TYPE, POINTER_TYPE, VOID_TYPE))
return 0;
- else
- {
- tree len = c_strlen (TREE_VALUE (TREE_CHAIN (arglist)));
-
- if (len == 0)
- return 0;
! len = size_binop (PLUS_EXPR, len, ssize_int (1));
! chainon (arglist, build_tree_list (NULL_TREE, len));
! }
!
! result = expand_builtin_memcpy (arglist);
! if (! result)
! TREE_CHAIN (TREE_CHAIN (arglist)) = 0;
! return result;
}
/* Callback routine for store_by_pieces. Read GET_MODE_BITSIZE (MODE)
--- 1911,1939 ----
if we failed the caller should emit a normal call. */
static rtx
! expand_builtin_strcpy (exp, target, mode)
tree exp;
+ rtx target;
+ enum machine_mode mode;
{
tree arglist = TREE_OPERAND (exp, 1);
! tree fn, len;
if (!validate_arglist (arglist, POINTER_TYPE, POINTER_TYPE, VOID_TYPE))
return 0;
! fn = built_in_decls[BUILT_IN_MEMCPY];
! if (!fn)
! return 0;
!
! len = c_strlen (TREE_VALUE (TREE_CHAIN (arglist)));
! if (len == 0)
! return 0;
! len = size_binop (PLUS_EXPR, len, ssize_int (1));
! chainon (arglist, build_tree_list (NULL_TREE, len));
! return expand_expr (build_function_call_expr (fn, arglist),
! target, mode, EXPAND_NORMAL);
}
/* Callback routine for store_by_pieces. Read GET_MODE_BITSIZE (MODE)
*************** expand_builtin_strncpy (arglist, target,
*** 1971,1976 ****
--- 1970,1976 ----
{
tree slen = c_strlen (TREE_VALUE (TREE_CHAIN (arglist)));
tree len = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
+ tree fn;
/* We must be passed a constant len parameter. */
if (TREE_CODE (len) != INTEGER_CST)
*************** expand_builtin_strncpy (arglist, target,
*** 2019,2025 ****
}
/* OK transform into builtin memcpy. */
! return expand_builtin_memcpy (arglist);
}
}
--- 2019,2029 ----
}
/* OK transform into builtin memcpy. */
! fn = built_in_decls[BUILT_IN_MEMCPY];
! if (!fn)
! return 0;
! return expand_expr (build_function_call_expr (fn, arglist),
! target, mode, EXPAND_NORMAL);
}
}
*************** expand_builtin_bzero (exp)
*** 2133,2166 ****
size = TREE_VALUE (TREE_CHAIN (arglist));
/* New argument list transforming bzero(ptr x, int y) to
! memset(ptr x, int 0, size_t y). */
!
newarglist = build_tree_list (NULL_TREE, convert (sizetype, size));
newarglist = tree_cons (NULL_TREE, integer_zero_node, newarglist);
newarglist = tree_cons (NULL_TREE, dest, newarglist);
TREE_OPERAND (exp, 1) = newarglist;
! result = expand_builtin_memset(exp);
!
/* Always restore the original arguments. */
TREE_OPERAND (exp, 1) = arglist;
return result;
}
- #ifdef HAVE_cmpstrsi
/* Expand expression EXP, which is a call to the memcmp or the strcmp builtin.
ARGLIST is the argument list for this call. Return 0 if we failed and the
caller should emit a normal call, otherwise try to get the result in
! TARGET, if convenient. */
static rtx
! expand_builtin_memcmp (exp, arglist, target)
tree exp;
tree arglist;
rtx target;
{
/* If we need to check memory accesses, call the library function. */
if (current_function_check_memory_usage)
return 0;
--- 2137,2174 ----
size = TREE_VALUE (TREE_CHAIN (arglist));
/* New argument list transforming bzero(ptr x, int y) to
! memset(ptr x, int 0, size_t y). This is done this way
! so that if it isn't expanded inline, we fallback to
! calling bzero instead of memset. */
!
newarglist = build_tree_list (NULL_TREE, convert (sizetype, size));
newarglist = tree_cons (NULL_TREE, integer_zero_node, newarglist);
newarglist = tree_cons (NULL_TREE, dest, newarglist);
TREE_OPERAND (exp, 1) = newarglist;
! result = expand_builtin_memset (exp);
!
/* Always restore the original arguments. */
TREE_OPERAND (exp, 1) = arglist;
return result;
}
/* Expand expression EXP, which is a call to the memcmp or the strcmp builtin.
ARGLIST is the argument list for this call. Return 0 if we failed and the
caller should emit a normal call, otherwise try to get the result in
! TARGET, if convenient (and in mode MODE, if that's convenient). */
static rtx
! expand_builtin_memcmp (exp, arglist, target, mode)
tree exp;
tree arglist;
rtx target;
+ enum machine_mode mode;
{
+ tree arg1, arg2, len;
+
/* If we need to check memory accesses, call the library function. */
if (current_function_check_memory_usage)
return 0;
*************** expand_builtin_memcmp (exp, arglist, tar
*** 2169,2179 ****
POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE, VOID_TYPE))
return 0;
{
- enum machine_mode mode;
- tree arg1 = TREE_VALUE (arglist);
- tree arg2 = TREE_VALUE (TREE_CHAIN (arglist));
- tree len = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
rtx arg1_rtx, arg2_rtx, arg3_rtx;
rtx result;
rtx insn;
--- 2177,2216 ----
POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE, VOID_TYPE))
return 0;
+ arg1 = TREE_VALUE (arglist);
+ arg2 = TREE_VALUE (TREE_CHAIN (arglist));
+ len = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
+
+ /* If the len parameter is zero, return zero. */
+ if (host_integerp (len, 1) && tree_low_cst (len, 1) == 0)
+ {
+ /* Evaluate and ignore arg1 and arg2 in case they have
+ side-effects. */
+ expand_expr (arg1, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ expand_expr (arg2, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ return const0_rtx;
+ }
+
+ /* If len parameter is one, return an expression corresponding to
+ (*(const unsigned char*)arg1 - (const unsigned char*)arg2). */
+ if (host_integerp (len, 1) && tree_low_cst (len, 1) == 1)
+ {
+ tree cst_uchar_node = build_type_variant (unsigned_char_type_node, 1, 0);
+ tree cst_uchar_ptr_node = build_pointer_type (cst_uchar_node);
+ tree ind1 =
+ fold (build1 (CONVERT_EXPR, integer_type_node,
+ build1 (INDIRECT_REF, cst_uchar_node,
+ build1 (NOP_EXPR, cst_uchar_ptr_node, arg1))));
+ tree ind2 =
+ fold (build1 (CONVERT_EXPR, integer_type_node,
+ build1 (INDIRECT_REF, cst_uchar_node,
+ build1 (NOP_EXPR, cst_uchar_ptr_node, arg2))));
+ tree result = fold (build (MINUS_EXPR, integer_type_node, ind1, ind2));
+ return expand_expr (result, target, mode, EXPAND_NORMAL);
+ }
+
+ #ifdef HAVE_cmpstrsi
{
rtx arg1_rtx, arg2_rtx, arg3_rtx;
rtx result;
rtx insn;
*************** expand_builtin_memcmp (exp, arglist, tar
*** 2228,2235 ****
else
return convert_to_mode (mode, result, 0);
}
! }
#endif
/* Expand expression EXP, which is a call to the strcmp builtin. Return 0
if we failed the caller should emit a normal call, otherwise try to get
--- 2265,2274 ----
else
return convert_to_mode (mode, result, 0);
}
! #else
! return 0;
#endif
+ }
/* Expand expression EXP, which is a call to the strcmp builtin. Return 0
if we failed the caller should emit a normal call, otherwise try to get
*************** expand_builtin_strcmp (exp, target, mode
*** 2242,2248 ****
enum machine_mode mode;
{
tree arglist = TREE_OPERAND (exp, 1);
! tree arg1, arg2;
const char *p1, *p2;
/* If we need to check memory accesses, call the library function. */
--- 2281,2287 ----
enum machine_mode mode;
{
tree arglist = TREE_OPERAND (exp, 1);
! tree arg1, arg2, len, len2, fn;
const char *p1, *p2;
/* If we need to check memory accesses, call the library function. */
*************** expand_builtin_strcmp (exp, target, mode
*** 2282,2339 ****
return expand_expr (result, target, mode, EXPAND_NORMAL);
}
! #ifdef HAVE_cmpstrsi
! if (! HAVE_cmpstrsi)
! return 0;
! {
! tree len = c_strlen (arg1);
! tree len2 = c_strlen (arg2);
! rtx result;
!
! if (len)
! len = size_binop (PLUS_EXPR, ssize_int (1), len);
! if (len2)
! len2 = size_binop (PLUS_EXPR, ssize_int (1), len2);
! /* If we don't have a constant length for the first, use the length
! of the second, if we know it. We don't require a constant for
! this case; some cost analysis could be done if both are available
! but neither is constant. For now, assume they're equally cheap
! unless one has side effects.
!
! If both strings have constant lengths, use the smaller. This
! could arise if optimization results in strcpy being called with
! two fixed strings, or if the code was machine-generated. We should
! add some code to the `memcmp' handler below to deal with such
! situations, someday. */
! if (!len || TREE_CODE (len) != INTEGER_CST)
! {
! if (len2 && !TREE_SIDE_EFFECTS (len2))
! len = len2;
! else if (len == 0)
! return 0;
! }
! else if (len2 && TREE_CODE (len2) == INTEGER_CST
! && tree_int_cst_lt (len2, len))
! len = len2;
! /* If both arguments have side effects, we cannot optimize. */
! if (TREE_SIDE_EFFECTS (len))
! return 0;
! chainon (arglist, build_tree_list (NULL_TREE, len));
! result = expand_builtin_memcmp (exp, arglist, target);
! if (! result)
! TREE_CHAIN (TREE_CHAIN (arglist)) = 0;
! return result;
! }
! #else
! return 0;
! #endif
}
/* Expand expression EXP, which is a call to the strncmp builtin. Return 0
--- 2321,2368 ----
return expand_expr (result, target, mode, EXPAND_NORMAL);
}
! len = c_strlen (arg1);
! len2 = c_strlen (arg2);
! if (len)
! len = size_binop (PLUS_EXPR, ssize_int (1), len);
! if (len2)
! len2 = size_binop (PLUS_EXPR, ssize_int (1), len2);
! /* If we don't have a constant length for the first, use the length
! of the second, if we know it. We don't require a constant for
! this case; some cost analysis could be done if both are available
! but neither is constant. For now, assume they're equally cheap
! unless one has side effects.
! If both strings have constant lengths, use the smaller. This
! could arise if optimization results in strcpy being called with
! two fixed strings, or if the code was machine-generated. We should
! add some code to the `memcmp' handler below to deal with such
! situations, someday. */
! if (!len || TREE_CODE (len) != INTEGER_CST)
! {
! if (len2 && !TREE_SIDE_EFFECTS (len2))
! len = len2;
! else if (len == 0)
! return 0;
! }
! else if (len2 && TREE_CODE (len2) == INTEGER_CST
! && tree_int_cst_lt (len2, len))
! len = len2;
! /* If both arguments have side effects, we cannot optimize. */
! if (TREE_SIDE_EFFECTS (len))
! return 0;
! fn = built_in_decls[BUILT_IN_MEMCMP];
! if (!fn)
! return 0;
! chainon (arglist, build_tree_list (NULL_TREE, len));
! return expand_expr (build_function_call_expr (fn, arglist),
! target, mode, EXPAND_NORMAL);
}
/* Expand expression EXP, which is a call to the strncmp builtin. Return 0
*************** expand_builtin_strncmp (exp, target, mod
*** 2347,2352 ****
--- 2376,2382 ----
enum machine_mode mode;
{
tree arglist = TREE_OPERAND (exp, 1);
+ tree fn, newarglist, len = 0;
tree arg1, arg2, arg3;
const char *p1, *p2;
*************** expand_builtin_strncmp (exp, target, mod
*** 2403,2447 ****
return expand_expr (result, target, mode, EXPAND_NORMAL);
}
- #ifdef HAVE_cmpstrsi
/* If c_strlen can determine an expression for one of the string
lengths, and it doesn't have side effects, then call
expand_builtin_memcmp() using length MIN(strlen(string)+1, arg3). */
! if (HAVE_cmpstrsi)
! {
! tree newarglist, len = 0;
!
! /* Perhaps one of the strings is really constant, if so prefer
! that constant length over the other string's length. */
! if (p1)
! len = c_strlen (arg1);
! else if (p2)
! len = c_strlen (arg2);
!
! /* If we still don't have a len, try either string arg as long
! as they don't have side effects. */
! if (!len && !TREE_SIDE_EFFECTS (arg1))
! len = c_strlen (arg1);
! if (!len && !TREE_SIDE_EFFECTS (arg2))
! len = c_strlen (arg2);
! /* If we still don't have a length, punt. */
! if (!len)
! return 0;
!
! /* Add one to the string length. */
! len = fold (size_binop (PLUS_EXPR, len, ssize_int (1)));
! /* The actual new length parameter is MIN(len,arg3). */
! len = fold (build (MIN_EXPR, TREE_TYPE (len), len, arg3));
! newarglist = build_tree_list (NULL_TREE, len);
! newarglist = tree_cons (NULL_TREE, arg2, newarglist);
! newarglist = tree_cons (NULL_TREE, arg1, newarglist);
! return expand_builtin_memcmp (exp, newarglist, target);
! }
! #endif
!
! return 0;
}
/* Expand expression EXP, which is a call to the strcat builtin.
--- 2433,2474 ----
return expand_expr (result, target, mode, EXPAND_NORMAL);
}
/* If c_strlen can determine an expression for one of the string
lengths, and it doesn't have side effects, then call
expand_builtin_memcmp() using length MIN(strlen(string)+1, arg3). */
!
! /* Perhaps one of the strings is really constant, if so prefer
! that constant length over the other string's length. */
! if (p1)
! len = c_strlen (arg1);
! else if (p2)
! len = c_strlen (arg2);
!
! /* If we still don't have a len, try either string arg as long
! as they don't have side effects. */
! if (!len && !TREE_SIDE_EFFECTS (arg1))
! len = c_strlen (arg1);
! if (!len && !TREE_SIDE_EFFECTS (arg2))
! len = c_strlen (arg2);
! /* If we still don't have a length, punt. */
! if (!len)
! return 0;
!
! fn = built_in_decls[BUILT_IN_MEMCMP];
! if (!fn)
! return 0;
!
! /* Add one to the string length. */
! len = fold (size_binop (PLUS_EXPR, len, ssize_int (1)));
! /* The actual new length parameter is MIN(len,arg3). */
! len = fold (build (MIN_EXPR, TREE_TYPE (len), len, arg3));
! newarglist = build_tree_list (NULL_TREE, len);
! newarglist = tree_cons (NULL_TREE, arg2, newarglist);
! newarglist = tree_cons (NULL_TREE, arg1, newarglist);
! return expand_expr (build_function_call_expr (fn, newarglist),
! target, mode, EXPAND_NORMAL);
}
/* Expand expression EXP, which is a call to the strcat builtin.
*************** expand_builtin_strncat (arglist, target,
*** 2517,2523 ****
{
tree newarglist =
tree_cons (NULL_TREE, dst, build_tree_list (NULL_TREE, src)),
! fn = built_in_decls[BUILT_IN_STRCAT];
/* If the replacement _DECL isn't initialized, don't do the
transformation. */
--- 2544,2550 ----
{
tree newarglist =
tree_cons (NULL_TREE, dst, build_tree_list (NULL_TREE, src)),
! fn = built_in_decls[BUILT_IN_STRCAT];
/* If the replacement _DECL isn't initialized, don't do the
transformation. */
*************** expand_builtin (exp, target, subtarget,
*** 3617,3623 ****
break;
case BUILT_IN_STRCPY:
! target = expand_builtin_strcpy (exp);
if (target)
return target;
break;
--- 3644,3650 ----
break;
case BUILT_IN_STRCPY:
! target = expand_builtin_strcpy (exp, target, mode);
if (target)
return target;
break;
*************** expand_builtin (exp, target, subtarget,
*** 3708,3728 ****
return target;
break;
- /* These comparison functions need an instruction that returns an actual
- index. An ordinary compare that just sets the condition codes
- is not enough. */
- #ifdef HAVE_cmpstrsi
case BUILT_IN_BCMP:
case BUILT_IN_MEMCMP:
! target = expand_builtin_memcmp (exp, arglist, target);
if (target)
return target;
break;
- #else
- case BUILT_IN_BCMP:
- case BUILT_IN_MEMCMP:
- break;
- #endif
case BUILT_IN_SETJMP:
target = expand_builtin_setjmp (arglist, target);
--- 3735,3746 ----
return target;
break;
case BUILT_IN_BCMP:
case BUILT_IN_MEMCMP:
! target = expand_builtin_memcmp (exp, arglist, target, mode);
if (target)
return target;
break;
case BUILT_IN_SETJMP:
target = expand_builtin_setjmp (arglist, target);
*** /dev/null Sun Dec 2 21:09:31 2001
--- string-opt-15.c Sun Dec 2 09:58:42 2001
***************
*** 0 ****
--- 1,46 ----
+ /* Copyright (C) 2001 Free Software Foundation.
+
+ Ensure that short builtin memcmp are optimized and perform correctly.
+ On architectures with a cmpstrsi instruction, this test doesn't determine
+ which optimization is being performed, but it does check for correctness.
+
+ Written by Roger Sayle, 12/02/2001. */
+
+ extern void abort (void);
+ typedef __SIZE_TYPE__ size_t;
+ extern int memcmp (const void *, const void *, size_t);
+ extern char *strcpy (char *, const char *);
+
+ int
+ main ()
+ {
+ char str[8];
+
+ strcpy (str, "3141");
+
+ if ( memcmp (str, str+2, 0) != 0 )
+ abort ();
+ if ( memcmp (str+1, str+3, 0) != 0 )
+ abort ();
+
+ if ( memcmp (str+1, str+3, 1) != 0 )
+ abort ();
+ if ( memcmp (str, str+2, 1) >= 0 )
+ abort ();
+ if ( memcmp (str+2, str, 1) <= 0 )
+ abort ();
+
+ return 0;
+ }
+
+ #ifdef __OPTIMIZE__
+ /* When optimizing, all the above cases should be transformed into
+ something else. So any remaining calls to the original function
+ should abort. */
+ static int
+ memcmp (const char *p1, const char *p2, size_t len)
+ {
+ abort ();
+ }
+ #endif
+
--
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-438-3470