This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Optimize strcmp(ptr,ptr) and friends
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 14 Jul 2003 14:42:18 -0600 (MDT)
- Subject: [PATCH] Optimize strcmp(ptr,ptr) and friends
The following patch should provide a interesting topic for discussion.
It was recently suggested by a colleague that GCC could optimize many of
the <string.h> builtins when both pointer arguments compared equal. The
patch below implements precisely this optimization for memcpy, mempcpy,
memmove, strcpy, memcmp, strcmp and strncmp.
I believe the standards state that the resulting behaviour is undefined
for all but memmove, memcmp, strcmp and strncmp, but it does no harm to
provide "reasonable" interpretations for the rest. The obvious question
is whether those same standards require that memmove(ptr,ptr,n) or
memcmp(ptr,ptr,n) must actually access the indicated memory, for
read/write and read respectively. For memcmp, for example, we'll already
optimize away the "pure" call if the result isn't used, so there's some
precedent.
Food for thought.
The following patch has been tested on i686-pc-linux-gnu with a complete
"make boostrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures. It relies on the
fact that operand_equal_p returns false if either operand is a volatile
pointer or otherwise side-effects.
Ok for mainline?
2003-07-14 Roger Sayle <roger@eyesopen.com>
* builtins.c (expand_builtin_memcpy): Optimize case when the two
pointer arguments are the equal, non-volatile and side-effect free.
(expand_builtin_mempcpy): Likewise.
(expand_builtin_memmove): Likewise.
(expand_builtin_strcpy): Likewise.
(expand_builtin_memcmp): Likewise.
(expand_builtin_strcmp): Likewise.
(expand_builtin_strncmp): Likewise.
* gcc.c-torture/execute/string-opt-18.c: New testcase.
Index: builtins.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/builtins.c,v
retrieving revision 1.232
diff -c -3 -p -r1.232 builtins.c
*** builtins.c 11 Jul 2003 21:04:53 -0000 1.232
--- builtins.c 14 Jul 2003 14:51:13 -0000
*************** expand_builtin_memcpy (tree arglist, rtx
*** 2558,2563 ****
--- 2558,2571 ----
return expand_expr (dest, target, mode, EXPAND_NORMAL);
}
+ /* If SRC and DEST are the same (and not volatile), return DEST. */
+ if (operand_equal_p (src, dest, 0))
+ {
+ /* Evaluate and ignore LEN in case it has side-effects. */
+ expand_expr (len, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ return expand_expr (dest, target, mode, EXPAND_NORMAL);
+ }
+
/* If either SRC is not a pointer type, don't do this
operation in-line. */
if (src_align == 0)
*************** expand_builtin_mempcpy (tree arglist, rt
*** 2644,2652 ****
= get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
rtx dest_mem, src_mem, len_rtx;
! /* If DEST is not a pointer type or LEN is not constant,
! call the normal function. */
! if (dest_align == 0 || !host_integerp (len, 1))
return 0;
/* If the LEN parameter is zero, return DEST. */
--- 2652,2683 ----
= get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
rtx dest_mem, src_mem, len_rtx;
! /* If DEST is not a pointer type, call the normal function. */
! if (dest_align == 0)
! return 0;
!
! /* If SRC and DEST are the same (and not volatile), do nothing. */
! if (operand_equal_p (src, dest, 0))
! {
! tree expr;
!
! if (endp == 0)
! {
! /* Evaluate and ignore LEN in case it has side-effects. */
! expand_expr (len, const0_rtx, VOIDmode, EXPAND_NORMAL);
! return expand_expr (dest, target, mode, EXPAND_NORMAL);
! }
!
! if (endp == 2)
! len = fold (build (MINUS_EXPR, TREE_TYPE (len), dest,
! integer_one_node));
! len = convert (TREE_TYPE (dest), len);
! expr = fold (build (PLUS_EXPR, TREE_TYPE (dest), dest, len));
! return expand_expr (expr, target, mode, EXPAND_NORMAL);
! }
!
! /* If LEN is not constant, call the normal function. */
! if (! host_integerp (len, 1))
return 0;
/* If the LEN parameter is zero, return DEST. */
*************** expand_builtin_memmove (tree arglist, rt
*** 2740,2745 ****
--- 2771,2784 ----
return expand_expr (dest, target, mode, EXPAND_NORMAL);
}
+ /* If SRC and DEST are the same (and not volatile), return DEST. */
+ if (operand_equal_p (src, dest, 0))
+ {
+ /* Evaluate and ignore LEN in case it has side-effects. */
+ expand_expr (len, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ return expand_expr (dest, target, mode, EXPAND_NORMAL);
+ }
+
/* If either SRC is not a pointer type, don't do this
operation in-line. */
if (src_align == 0)
*************** expand_builtin_strcpy (tree arglist, rtx
*** 2802,2817 ****
if (!validate_arglist (arglist, POINTER_TYPE, POINTER_TYPE, VOID_TYPE))
return 0;
fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
if (!fn)
return 0;
- src = TREE_VALUE (TREE_CHAIN (arglist));
len = c_strlen (src, 1);
if (len == 0 || TREE_SIDE_EFFECTS (len))
return 0;
- dst = TREE_VALUE (arglist);
len = size_binop (PLUS_EXPR, len, ssize_int (1));
arglist = build_tree_list (NULL_TREE, len);
arglist = tree_cons (NULL_TREE, src, arglist);
--- 2841,2861 ----
if (!validate_arglist (arglist, POINTER_TYPE, POINTER_TYPE, VOID_TYPE))
return 0;
+ src = TREE_VALUE (TREE_CHAIN (arglist));
+ dst = TREE_VALUE (arglist);
+
+ /* If SRC and DST are equal (and not volatile), return DST. */
+ if (operand_equal_p (src, dst, 0))
+ return expand_expr (dst, target, mode, EXPAND_NORMAL);
+
fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
if (!fn)
return 0;
len = c_strlen (src, 1);
if (len == 0 || TREE_SIDE_EFFECTS (len))
return 0;
len = size_binop (PLUS_EXPR, len, ssize_int (1));
arglist = build_tree_list (NULL_TREE, len);
arglist = tree_cons (NULL_TREE, src, arglist);
*************** expand_builtin_memcmp (tree exp ATTRIBUT
*** 3164,3169 ****
--- 3208,3221 ----
return const0_rtx;
}
+ /* If both arguments are equal (and not volatile), return zero. */
+ if (operand_equal_p (arg1, arg2, 0))
+ {
+ /* Evaluate and ignore len in case it has side-effects. */
+ expand_expr (len, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ return const0_rtx;
+ }
+
p1 = c_getstr (arg1);
p2 = c_getstr (arg2);
*************** expand_builtin_strcmp (tree exp, rtx tar
*** 3293,3298 ****
--- 3345,3354 ----
arg1 = TREE_VALUE (arglist);
arg2 = TREE_VALUE (TREE_CHAIN (arglist));
+ /* If both arguments are equal (and not volatile), return zero. */
+ if (operand_equal_p (arg1, arg2, 0))
+ return const0_rtx;
+
p1 = c_getstr (arg1);
p2 = c_getstr (arg2);
*************** expand_builtin_strncmp (tree exp, rtx ta
*** 3430,3435 ****
--- 3486,3499 ----
side-effects. */
expand_expr (arg1, const0_rtx, VOIDmode, EXPAND_NORMAL);
expand_expr (arg2, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ return const0_rtx;
+ }
+
+ /* If arg1 and arg2 are equal (and not volatile), return zero. */
+ if (operand_equal_p (arg1, arg2, 0))
+ {
+ /* Evaluate and ignore arg3 in case it has side-effects. */
+ expand_expr (arg3, const0_rtx, VOIDmode, EXPAND_NORMAL);
return const0_rtx;
}
/* Copyright (C) 2003 Free Software Foundation.
Test equal pointer optimizations don't break anything.
Written by Roger Sayle, July 14, 2003. */
extern void abort ();
typedef __SIZE_TYPE__ size_t;
extern void *memcpy(void*, const void*, size_t);
extern void *mempcpy(void*, const void*, size_t);
extern void *memmove(void*, const void*, size_t);
extern char *strcpy(char*, const char*);
extern int memcmp(const void*, const void*, size_t);
extern int strcmp(const char*, const char*);
extern int strncmp(const char*, const char*, size_t);
void test1 (void *ptr)
{
if (memcpy(ptr,ptr,8) != ptr)
abort ();
}
void test2 (char *ptr)
{
if (mempcpy(ptr,ptr,8) != ptr+8)
abort ();
}
void test3 (void *ptr)
{
if (memmove(ptr,ptr,8) != ptr)
abort ();
}
void test4 (char *ptr)
{
if (strcpy(ptr,ptr) != ptr)
abort ();
}
void test5 (void *ptr)
{
if (memcmp(ptr,ptr,8) != 0)
abort ();
}
void test6 (const char *ptr)
{
if (strcmp(ptr,ptr) != 0)
abort ();
}
void test7 (const char *ptr)
{
if (strncmp(ptr,ptr,8) != 0)
abort ();
}
int main ()
{
char buf[10];
test1 (buf);
test2 (buf);
test3 (buf);
test4 (buf);
test5 (buf);
test6 (buf);
test7 (buf);
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