This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Optimize strchr(x, 0), strcmp("a","b") and strstr("abc","bc")
- To: "Kaveh R. Ghazi" <ghazi at caip dot rutgers dot edu>, jsm28 at cam dot ac dot uk
- Subject: [PATCH] Optimize strchr(x, 0), strcmp("a","b") and strstr("abc","bc")
- From: Jakub Jelinek <jakub at redhat dot com>
- Date: Tue, 7 Nov 2000 17:25:50 +0100
- Cc: gcc-patches at gcc dot gnu dot org
- Reply-To: Jakub Jelinek <jakub at redhat dot com>
Hi!
This patch adds a few builtin optimizations:
1) c_strlen used to compute max incorrectly, which means that the
if (offset_node && TREE_CODE (offset_node) != INTEGER_CST) branch
never succeeded (it was checking if none of the characters in the
string are '\0' while it should check if none but the last char
is non-'\0'.
An example of what was not optimized is e.g.
strlen ("hello world" + (x++ & 7))
2) adds a c_getstr function which can be used to optimize out
most of the builtins if all arguments are constant by calling the
appropriate function during compile time and only insert the result
into rtl. So that c_getstr can return a character pointer the host
can use, it accepts only what c_strlen accepts minus the
offset_node && TREE_CODE (offset_node) != INTEGER_CST
case (thus c_getstr returns non-NULL only if the thing does not have
side-effects, stuff like "abc"+2 should be ok but "abcde" + (i&3)
will not).
3) optimizes strstr, strchr and strcmp if all arguments to it are constant
4) optimizes strchr(x, 0) into __builtin_strlen(x) (ie. on some machine
it will be even more optimized)
Bootstrapped on i386-redhat-linux, no regressions.
2000-11-07 Jakub Jelinek <jakub@redhat.com>
* builtins.c (c_strlen): Use TREE_STRING_LENGTH - 1 for max.
(c_getstr): New function.
(expand_builtin_strstr): Do nothing if -fcheck-memory-usage.
If both arguments are constant string, optimize out.
(expand_builtin_strchr): New function.
(expand_builtin_strcmp): Add MODE argument.
Use even if !HAVE_cmpstrsi.
Optimize the case when both arguments are constant strings.
(expand_builtin): Adjust expand_builtin_strcmp caller.
Call expand_builtin_strchr.
* c-common.c (c_common_nodes_and_builtins): Initialize
built_in_decls[BUILT_IN_STRLEN].
Add strchr builtin.
* gcc.c-torture/execute/string-opt-3.c: New test.
--- gcc/builtins.c.jj Mon Nov 6 09:38:23 2000
+++ gcc/builtins.c Tue Nov 7 16:17:56 2000
@@ -80,6 +80,7 @@ tree (*lang_type_promotes_to) PARAMS ((t
static int get_pointer_alignment PARAMS ((tree, unsigned));
static tree c_strlen PARAMS ((tree));
+static char *c_getstr PARAMS ((tree));
static rtx get_memory_rtx PARAMS ((tree));
static int apply_args_size PARAMS ((void));
static int apply_result_size PARAMS ((void));
@@ -100,8 +101,9 @@ static rtx expand_builtin_va_end PARAMS
static rtx expand_builtin_va_copy PARAMS ((tree));
#ifdef HAVE_cmpstrsi
static rtx expand_builtin_memcmp PARAMS ((tree, tree, rtx));
-static rtx expand_builtin_strcmp PARAMS ((tree, rtx));
#endif
+static rtx expand_builtin_strcmp PARAMS ((tree, rtx,
+ enum machine_mode));
static rtx expand_builtin_memcpy PARAMS ((tree));
static rtx expand_builtin_strcpy PARAMS ((tree));
static rtx expand_builtin_memset PARAMS ((tree));
@@ -109,6 +111,8 @@ static rtx expand_builtin_bzero PARAMS
static rtx expand_builtin_strlen PARAMS ((tree, rtx));
static rtx expand_builtin_strstr PARAMS ((tree, rtx,
enum machine_mode));
+static rtx expand_builtin_strchr PARAMS ((tree, rtx,
+ enum machine_mode));
static rtx expand_builtin_alloca PARAMS ((tree, rtx));
static rtx expand_builtin_ffs PARAMS ((tree, rtx, rtx));
static rtx expand_builtin_frame_address PARAMS ((tree));
@@ -208,7 +212,7 @@ c_strlen (src)
if (src == 0)
return 0;
- max = TREE_STRING_LENGTH (src);
+ max = TREE_STRING_LENGTH (src) - 1;
ptr = TREE_STRING_POINTER (src);
if (offset_node && TREE_CODE (offset_node) != INTEGER_CST)
@@ -261,6 +265,41 @@ c_strlen (src)
return ssize_int (strlen (ptr + offset));
}
+/* Return a char pointer for a C string if it is a string constant
+ or sum of string constant and integer constant. */
+
+static char *
+c_getstr (src)
+ tree src;
+{
+ tree offset_node;
+ int offset, max;
+ char *ptr;
+
+ src = string_constant (src, &offset_node);
+ if (src == 0)
+ return 0;
+
+ max = TREE_STRING_LENGTH (src) - 1;
+ ptr = TREE_STRING_POINTER (src);
+
+ if (!offset_node)
+ offset = 0;
+ else if (TREE_CODE (offset_node) != INTEGER_CST)
+ return 0;
+ else
+ {
+ /* Did we get a long long offset? If so, punt. */
+ if (TREE_INT_CST_HIGH (offset_node) != 0)
+ return 0;
+ offset = TREE_INT_CST_LOW (offset_node);
+ if (offset < 0 || offset > max)
+ return 0;
+ }
+
+ return ptr + offset;
+}
+
/* Given TEM, a pointer to a stack frame, follow the dynamic chain COUNT
times to get the address of either a higher stack frame, or a return
address located within it (depending on FNDECL_CODE). */
@@ -1414,48 +1453,110 @@ expand_builtin_strstr (arglist, target,
if (arglist == 0
|| TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) != POINTER_TYPE
|| TREE_CHAIN (arglist) == 0
- || TREE_CODE (TREE_TYPE (TREE_VALUE (TREE_CHAIN (arglist)))) != POINTER_TYPE)
+ || TREE_CODE (TREE_TYPE (TREE_VALUE (TREE_CHAIN (arglist)))) != POINTER_TYPE
+ || current_function_check_memory_usage)
return 0;
else
{
tree s1 = TREE_VALUE (arglist), s2 = TREE_VALUE (TREE_CHAIN (arglist));
- tree len = c_strlen (s2);
+ tree call_expr, fn;
+ char *p1, *p2;
- if (!len)
+ p2 = c_getstr (s2);
+ if (p2 == NULL)
return 0;
- switch (compare_tree_int (len, 1))
- {
- case -1: /* length is 0, return s1. */
- return expand_expr (s1, target, mode, EXPAND_NORMAL);
- case 0: /* length is 1, return strchr(s1, s2[0]). */
- {
- tree call_expr, fn = built_in_decls[BUILT_IN_STRCHR];
+ p1 = c_getstr (s1);
+ if (p1 != NULL)
+ {
+ char *r = strstr (p1, p2);
+ tree expr;
- if (!fn)
- return 0;
- STRIP_NOPS (s2);
- if (s2 && TREE_CODE (s2) == ADDR_EXPR)
- s2 = TREE_OPERAND (s2, 0);
-
- /* New argument list transforming strstr(s1, s2) to
- strchr(s1, s2[0]). */
- arglist =
- build_tree_list (NULL_TREE,
- build_int_2 (TREE_STRING_POINTER (s2)[0], 0));
- arglist = tree_cons (NULL_TREE, s1, arglist);
- call_expr = build1 (ADDR_EXPR,
- build_pointer_type (TREE_TYPE (fn)), fn);
- call_expr = build (CALL_EXPR, TREE_TYPE (TREE_TYPE (fn)),
- call_expr, arglist, NULL_TREE);
- TREE_SIDE_EFFECTS (call_expr) = 1;
- return expand_expr (call_expr, target, mode, EXPAND_NORMAL);
- }
- case 1: /* length is greater than 1, really call strstr. */
- return 0;
- default:
- abort();
+ if (r == NULL)
+ expr = null_pointer_node;
+ else
+ expr = build (PLUS_EXPR, TREE_TYPE (s1), s1,
+ build_int_2 (r - p1, 0));
+
+ return expand_expr (expr, target, mode, EXPAND_NORMAL);
+ }
+
+ if (p2[0] == '\0')
+ return expand_expr (s1, target, mode, EXPAND_NORMAL);
+
+ fn = built_in_decls[BUILT_IN_STRCHR];
+ if (!fn)
+ return 0;
+
+ /* New argument list transforming strstr(s1, s2) to
+ strchr(s1, s2[0]). */
+ arglist =
+ build_tree_list (NULL_TREE, build_int_2 (p2[0], 0));
+ arglist = tree_cons (NULL_TREE, s1, arglist);
+ call_expr = build1 (ADDR_EXPR,
+ build_pointer_type (TREE_TYPE (fn)), fn);
+ call_expr = build (CALL_EXPR, TREE_TYPE (TREE_TYPE (fn)),
+ call_expr, arglist, NULL_TREE);
+ TREE_SIDE_EFFECTS (call_expr) = 1;
+ return expand_expr (call_expr, target, mode, EXPAND_NORMAL);
+ }
+}
+
+/* Expand a call to the strchr builtin. Return 0 if we failed 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_strchr (arglist, target, mode)
+ tree arglist;
+ rtx target;
+ enum machine_mode mode;
+{
+ if (arglist == 0
+ || TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) != POINTER_TYPE
+ || TREE_CHAIN (arglist) == 0
+ || TREE_CODE (TREE_TYPE (TREE_VALUE (TREE_CHAIN (arglist)))) != INTEGER_TYPE
+ || current_function_check_memory_usage)
+ return 0;
+ else
+ {
+ tree s1 = TREE_VALUE (arglist), s2 = TREE_VALUE (TREE_CHAIN (arglist));
+ tree call_expr, fn;
+ char *p1;
+
+ if (TREE_CODE (s2) != INTEGER_CST)
+ return 0;
+
+ if ((p1 = c_getstr (s1)) != NULL)
+ {
+ char *r = strchr (p1, (char) TREE_INT_CST_LOW (s2));
+ tree expr;
+
+ if (r == NULL)
+ expr = null_pointer_node;
+ else
+ expr = build (PLUS_EXPR, TREE_TYPE (s1), s1,
+ build_int_2 (r - p1, 0));
+
+ return expand_expr (expr, target, mode, EXPAND_NORMAL);
}
+
+ if (!integer_zerop (s2))
+ return 0;
+
+ fn = built_in_decls[BUILT_IN_STRLEN];
+ if (!fn)
+ return 0;
+
+ /* New argument list transforming strchr(s1, '\0') to strlen(s1). */
+ arglist =
+ build_tree_list (NULL_TREE, s1);
+ call_expr = build1 (ADDR_EXPR,
+ build_pointer_type (TREE_TYPE (fn)), fn);
+ call_expr = build (CALL_EXPR, TREE_TYPE (TREE_TYPE (fn)),
+ call_expr, arglist, NULL_TREE);
+ TREE_SIDE_EFFECTS (call_expr) = 1;
+ return expand_expr (call_expr, target, mode, EXPAND_NORMAL);
}
}
@@ -1736,17 +1837,21 @@ expand_builtin_memcmp (exp, arglist, tar
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
the result in TARGET, if convenient. */
static rtx
-expand_builtin_strcmp (exp, target)
+expand_builtin_strcmp (exp, target, mode)
tree exp;
rtx target;
+ enum machine_mode mode;
{
tree arglist = TREE_OPERAND (exp, 1);
+ tree arg1, arg2;
+ char *p1, *p2;
/* If we need to check memory accesses, call the library function. */
if (current_function_check_memory_usage)
@@ -1760,11 +1865,27 @@ expand_builtin_strcmp (exp, target)
!= POINTER_TYPE))
return 0;
- else if (! HAVE_cmpstrsi)
+ arg1 = TREE_VALUE (arglist);
+ arg2 = TREE_VALUE (TREE_CHAIN (arglist));
+
+ p1 = c_getstr (arg1);
+ p2 = c_getstr (arg2);
+
+ if (p1 && p2)
+ {
+ int i = strcmp (p1, p2);
+
+ return expand_expr (i < 0 ? build_int_2 (-1, -1)
+ : i == 0 ? integer_zero_node
+ : integer_one_node,
+ target, mode, EXPAND_NORMAL);
+ }
+
+#ifdef HAVE_cmpstrsi
+ if (! HAVE_cmpstrsi)
return 0;
+
{
- tree arg1 = TREE_VALUE (arglist);
- tree arg2 = TREE_VALUE (TREE_CHAIN (arglist));
tree len = c_strlen (arg1);
tree len2 = c_strlen (arg2);
rtx result;
@@ -1804,8 +1925,10 @@ expand_builtin_strcmp (exp, target)
return result;
}
-}
+#else
+ return 0;
#endif
+}
/* Expand a call to __builtin_saveregs, generating the result in TARGET,
if that's convenient. */
@@ -2638,6 +2761,12 @@ expand_builtin (exp, target, subtarget,
return target;
break;
+ case BUILT_IN_STRCHR:
+ target = expand_builtin_strchr (arglist, target, mode);
+ if (target)
+ return target;
+ break;
+
case BUILT_IN_MEMCPY:
target = expand_builtin_memcpy (arglist);
if (target)
@@ -2656,16 +2785,16 @@ expand_builtin (exp, target, subtarget,
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_STRCMP:
- target = expand_builtin_strcmp (exp, target);
+ target = expand_builtin_strcmp (exp, target, mode);
if (target)
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);
@@ -2673,7 +2802,6 @@ expand_builtin (exp, target, subtarget,
return target;
break;
#else
- case BUILT_IN_STRCMP:
case BUILT_IN_BCMP:
case BUILT_IN_MEMCMP:
break;
@@ -2731,9 +2859,7 @@ expand_builtin (exp, target, subtarget,
case BUILT_IN_PUTS:
case BUILT_IN_FPUTC:
case BUILT_IN_FWRITE:
- case BUILT_IN_STRCHR:
break;
-
case BUILT_IN_FPUTS:
target = expand_builtin_fputs (arglist, ignore);
if (target)
--- gcc/c-common.c.jj Fri Nov 3 10:53:36 2000
+++ gcc/c-common.c Tue Nov 7 13:42:24 2000
@@ -5179,8 +5179,9 @@ c_common_nodes_and_builtins ()
BUILT_IN_STRCHR, BUILT_IN_NORMAL, "strchr");
builtin_function ("__builtin_strcpy", string_ftype_ptr_ptr,
BUILT_IN_STRCPY, BUILT_IN_NORMAL, "strcpy");
- builtin_function ("__builtin_strlen", strlen_ftype,
- BUILT_IN_STRLEN, BUILT_IN_NORMAL, "strlen");
+ built_in_decls[BUILT_IN_STRLEN] =
+ builtin_function ("__builtin_strlen", strlen_ftype,
+ BUILT_IN_STRLEN, BUILT_IN_NORMAL, "strlen");
builtin_function ("__builtin_sqrtf", float_ftype_float,
BUILT_IN_FSQRT, BUILT_IN_NORMAL, "sqrtf");
builtin_function ("__builtin_fsqrt", double_ftype_double,
@@ -5246,6 +5247,8 @@ c_common_nodes_and_builtins ()
builtin_function ("strcmp", int_ftype_string_string, BUILT_IN_STRCMP,
BUILT_IN_NORMAL, NULL_PTR);
builtin_function ("strstr", string_ftype_string_string, BUILT_IN_STRSTR,
+ BUILT_IN_NORMAL, NULL_PTR);
+ builtin_function ("strchr", string_ftype_string_int, BUILT_IN_STRCHR,
BUILT_IN_NORMAL, NULL_PTR);
builtin_function ("strcpy", string_ftype_ptr_ptr, BUILT_IN_STRCPY,
BUILT_IN_NORMAL, NULL_PTR);
--- gcc/testsuite/gcc.c-torture/execute/string-opt-3.c.jj Tue Nov 7 12:00:07 2000
+++ gcc/testsuite/gcc.c-torture/execute/string-opt-3.c Tue Nov 7 15:15:45 2000
@@ -0,0 +1,51 @@
+/* Copyright (C) 2000 Free Software Foundation.
+
+ Ensure all expected transformations of builtin strlen and strcmp
+ occur and perform correctly.
+
+ Written by Jakub Jelinek, 11/7/2000. */
+
+extern void abort(void);
+extern __SIZE_TYPE__ strlen (const char *);
+extern int strcmp (const char *, const char *);
+
+int x = 6;
+
+int main()
+{
+ const char *const foo = "hello world";
+
+ if (strlen (foo) != 11)
+ abort();
+ if (strlen (foo + 4) != 7)
+ abort();
+ if (strlen (foo + (x++ & 7)) != 5)
+ abort();
+ if (x != 7)
+ abort();
+ if (strcmp (foo, "hello") <= 0)
+ abort();
+ if (strcmp (foo, foo) != 0)
+ abort();
+ if (strcmp (foo, "hello world ") >= 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. */
+__SIZE_TYPE__
+strlen(const char *s)
+{
+ abort();
+}
+
+int
+strcmp (const char *s1, const char *s2)
+{
+ abort();
+}
+#endif
Jakub