<ctype.h>: more optimization.
clang is pretty good at turning something like
(c >= '0' && c <= '9')
into the equivalent of an array bounds check:
((unsigned c)-'0' < 10).
Unfortunately, it struggles if you combine two or more of these
comparisons.
So although it generates [afaik] optimal code for isdigit(), and can
separately do the same for
(c >= 'a' && c <= 'f'),
or
(c >= 'A' && c <= 'F'),
or even
(_tolower(c) >= 'a' && _tolower(c) <= 'f'),
when you combine them (as in isxdigit()) it no longer recognizes any of
these as something it can optimize and puts all the branches back in.
To avoid this, let's add a macro that does the optimized range check and
use that throughout <ctype.h>.
With the new more accurate <ctype.h> benchmarks, we see improvements
of around 40-50MiB/s more for arm64 (not counting isspace(), which
skews the statistics by being roughly twice as fast, going from
216MiB/s to 438MiB/s). arm32 benefits less, from "not at all" for
isprint() or isspace(), to 40MiB/s better for islower().
Only ispunct() still has an explicit branch for arm64; all the arm32
functions lose their branches, if you don't count the `bxlo lr` in
the same part of ispunct().
Test: treehugger
Change-Id: I663ff7e31b0f4173d6dd27f16bb2d8d3485c8e06
diff --git a/libc/include/ctype.h b/libc/include/ctype.h
index c15ee56..cb926a4 100644
--- a/libc/include/ctype.h
+++ b/libc/include/ctype.h
@@ -73,9 +73,35 @@
/** Internal implementation detail. Do not use. */
extern const char* _ctype_;
+/**
+ * Returns the corresponding lower-case character if `ch` is upper-case, or undefined otherwise.
+ *
+ * Prefer tolower() instead.
+ */
+__BIONIC_CTYPE_INLINE int _tolower(int __ch) {
+ return __ch | 0x20;
+}
+
+/**
+ * Returns the corresponding upper-case character if `ch` is lower-case, or undefined otherwise.
+ *
+ * Prefer toupper() instead.
+ */
+__BIONIC_CTYPE_INLINE int _toupper(int __ch) {
+ // Using EOR rather than AND makes no difference on arm, but saves an
+ // instruction on arm64.
+ return __ch ^ 0x20;
+}
+
+/** Internal implementation detail. Do not use. */
+__attribute__((__no_sanitize__("unsigned-integer-overflow")))
+static inline int __bionic_ctype_in_range(unsigned __lo, int __ch, unsigned __hi) {
+ return (__BIONIC_CAST(static_cast, unsigned, __ch) - __lo) < (__hi - __lo + 1);
+}
+
/** Returns true if `ch` is in `[A-Za-z]`. */
__BIONIC_CTYPE_INLINE int isalpha(int __ch) {
- return (__ch >= 'A' && __ch <= 'Z') || (__ch >= 'a' && __ch <= 'z');
+ return __bionic_ctype_in_range('a', _tolower(__ch), 'z');
}
/** Returns true if `ch` is a space or tab. */
@@ -90,37 +116,37 @@
/** Returns true if `ch` is in `[0-9]`. */
__BIONIC_CTYPE_INLINE int isdigit(int __ch) {
- return (__ch >= '0' && __ch <= '9');
+ return __bionic_ctype_in_range('0', __ch, '9');
}
/** Returns true if `ch` is `[A-Za-z0-9]` or punctuation. */
__BIONIC_CTYPE_INLINE int isgraph(int __ch) {
- return (__ch >= '!' && __ch <= '~');
+ return __bionic_ctype_in_range('!', __ch, '~');
}
/** Returns true if `ch` is in `[a-z]`. */
__BIONIC_CTYPE_INLINE int islower(int __ch) {
- return (__ch >= 'a' && __ch <= 'z');
+ return __bionic_ctype_in_range('a', __ch, 'z');
}
/** Returns true if `ch` is `[A-Za-z0-9]` or punctuation or space. */
__BIONIC_CTYPE_INLINE int isprint(int __ch) {
- return (__ch >= ' ' && __ch <= '~');
+ return __bionic_ctype_in_range(' ', __ch, '~');
}
/** Returns true if `ch` is in `[ \f\n\r\t\v]`. */
__BIONIC_CTYPE_INLINE int isspace(int __ch) {
- return __ch == ' ' || (__ch >= '\t' && __ch <= '\r');
+ return __ch == ' ' || __bionic_ctype_in_range('\t', __ch, '\r');
}
/** Returns true if `ch` is in `[A-Z]`. */
__BIONIC_CTYPE_INLINE int isupper(int __ch) {
- return (__ch >= 'A' && __ch <= 'Z');
+ return __bionic_ctype_in_range('A', __ch, 'Z');
}
/** Returns true if `ch` is in `[0-9A-Fa-f]`. */
__BIONIC_CTYPE_INLINE int isxdigit(int __ch) {
- return (__ch >= '0' && __ch <= '9') || (__ch >= 'a' && __ch <= 'f') || (__ch >= 'A' && __ch <= 'F');
+ return isdigit(__ch) || __bionic_ctype_in_range('a', _tolower(__ch), 'f') ;
}
/** Returns true if `ch` is in `[A-Za-z0-9]`. */
@@ -133,36 +159,14 @@
return isgraph(__ch) && !isalnum(__ch);
}
-/**
- * Returns the corresponding lower-case character if `ch` is upper-case, or undefined otherwise.
- *
- * Prefer tolower() instead.
- */
-__BIONIC_CTYPE_INLINE int _tolower(int __ch) {
- return __ch | 0x20;
-}
-
/** Returns the corresponding lower-case character if `ch` is upper-case, or `ch` otherwise. */
__BIONIC_CTYPE_INLINE int tolower(int __ch) {
- if (__ch >= 'A' && __ch <= 'Z') return _tolower(__ch);
- return __ch;
-}
-
-/**
- * Returns the corresponding upper-case character if `ch` is lower-case, or undefined otherwise.
- *
- * Prefer toupper() instead.
- */
-__BIONIC_CTYPE_INLINE int _toupper(int __ch) {
- // Using EOR rather than AND makes no difference on arm, but saves an
- // instruction on arm64.
- return __ch ^ 0x20;
+ return (__bionic_ctype_in_range('A', __ch, 'Z')) ? _tolower(__ch) : __ch;
}
/** Returns the corresponding upper-case character if `ch` is lower-case, or `ch` otherwise. */
__BIONIC_CTYPE_INLINE int toupper(int __ch) {
- if (__ch >= 'a' && __ch <= 'z') return _toupper(__ch);
- return __ch;
+ return (__bionic_ctype_in_range('a', __ch, 'z')) ? _toupper(__ch) : __ch;
}
/** Returns true if `ch` is less than 0x80. */