Re: The speed of the compiler, was: Re: Combine four insns

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, Aug 10, 2010 at 4:48 PM, Andi Kleen <andi@firstfloor.org> wrote:
> Chris Lattner <clattner@apple.com> writes:
>>
>> ? e. General speedups: Clang's preprocessor is roughly 2x faster than GCC's and the frontend is generally much faster. ?For example, it uses hash tables instead of lists where appropriate, so it doesn't get N^2 cases in silly situations as often. ?I don't what what else GCC is doing wrong, I haven't looked at its frontends much.
>
> I looked at this a weekend or two ago. The two hot functions in the
> preprocessor are cpp_clean_line and the lexer.
>
> At least cpp_clean_line was pretty easy to speed up using SSE 4.2
> string instructions and vectorizing it.
>
> That change made it drop down from top 10 in a unoptimized build to
> lower top 40 or so. I suspect with that change the clang advantage
> is much less than 2x.
>
> Drawback: the patch broke some of the PCH test cases in the test
> suite and I never quite figured out why (that's why I didn't post
> the patch)
>
> Other drawback: the optimization only helps on x86 systems
> that support SSE 4.2 (but presumably that's a popular build system)
>
> Here's the patch if anyone is interested.
>
> Vectorizing the lexer might be possible too, but it's somewhat
> harder.
>
> The other problem I found is that cpplib is not using profile
> feedback, that is likely giving some performance away too.

I'm sure there is a way to open-code this using integer math.
Likely the performance issue is both that we use byte loads
and 4 comparisons per char.  Maybe 4 parallel strchr optimized
searches are comparable fast?

Richard.

> -Andi
>
>
> diff --git a/libcpp/init.c b/libcpp/init.c
> index c5b8c28..769aa50 100644
> --- a/libcpp/init.c
> +++ b/libcpp/init.c
> @@ -137,6 +137,8 @@ init_library (void)
> ?#ifdef ENABLE_NLS
> ? ? ? ?(void) bindtextdomain (PACKAGE, LOCALEDIR);
> ?#endif
> +
> + ? ? ? init_vectorized_lexer ();
> ? ? }
> ?}
>
> diff --git a/libcpp/internal.h b/libcpp/internal.h
> index 9209b55..10ed033 100644
> --- a/libcpp/internal.h
> +++ b/libcpp/internal.h
> @@ -725,6 +725,8 @@ ufputs (const unsigned char *s, FILE *f)
> ? return fputs ((const char *)s, f);
> ?}
>
> +extern void init_vectorized_lexer (void);
> +
> ?#ifdef __cplusplus
> ?}
> ?#endif
> diff --git a/libcpp/lex.c b/libcpp/lex.c
> index f628272..589fa64 100644
> --- a/libcpp/lex.c
> +++ b/libcpp/lex.c
> @@ -96,6 +96,82 @@ add_line_note (cpp_buffer *buffer, const uchar *pos, unsigned int type)
> ? buffer->notes_used++;
> ?}
>
> +#if (GCC_VERSION >= 4005) && (defined(__i386__) || defined(__x86_64__))
> +
> +#define HAVE_SSE42 1
> +
> +#include <stdint.h>
> +#include "../gcc/config/i386/cpuid.h"
> +
> +bool cpu_has_sse42;
> +
> +/* Check if CPU supports vectorized string instructions. */
> +
> +void
> +init_vectorized_lexer (void)
> +{
> + ?unsigned dummy, ecx;
> +
> + ?if (__get_cpuid (1, &dummy, &dummy, &ecx, &dummy))
> + ? ? ?cpu_has_sse42 = !!(ecx & (1 << 20));
> +}
> +
> +/* Fast path to find line special characters using SSE 4.2 vectorized string
> + ? instructions. Anything complicated falls back to the slow path below.
> + ? Since this loop is very hot it's worth doing these kinds of
> + ? optimizations. Returns true if stopper character found.
> +
> + ? We should be using the _mm intrinsics, but the xxxintr headers do things
> + ? not allowed in gcc. So instead use direct builtins. */
> +
> +static bool __attribute__((__target__("sse4.2")))
> +search_line_sse42 (const uchar *s, const uchar *end, const uchar **out)
> +{
> + ?typedef char m128i __attribute__ ((__vector_size__ (16)));
> + ?int left;
> + ?int index;
> + ?static char searchstr[16] __attribute__ ((aligned(16))) = "\n\r?\\";
> + ?m128i search = *(m128i *)searchstr;
> + ?m128i data;
> +
> + ?for (left = end - (uchar *)s; left > 0; left -= 16)
> + ? ?{
> + ? ? ?if (((uintptr_t)s & 0xfff) > 0xff0)
> + ? ? ? {
> + ? ? ? ? /* Too near page boundary. Use slow path. This could be
> + ? ? ? ? ? ?avoided if we ensure suitable padding or alignment in
> + ? ? ? ? ? ?the input buffer. */
> + ? ? ? ? *out = s;
> + ? ? ? ? return false;
> + ? ? ? }
> +
> + ? ? ?/* Use vectorized string comparison, looking for the 4 stoppers. */
> + ? ? ?data = (m128i) __builtin_ia32_loaddqu((const char *)s);
> + ? ? ?index = __builtin_ia32_pcmpestri128 (search, 4, data, left, 0);
> + ? ? ?if (index < 16)
> + ? ? ? {
> + ? ? ? ? *out = s + index;
> + ? ? ? ? return true;
> + ? ? ? }
> + ? ? ?s += 16;
> + ? ?}
> +
> + ?/* Ran out of buffer. Should not happen? */
> + ?*out = end;
> + ?return false;
> +}
> +
> +#else
> +
> +/* Dummy */
> +
> +void
> +init_vectorized_lexer (void)
> +{
> +}
> +
> +#endif
> +
> ?/* Returns with a logical line that contains no escaped newlines or
> ? ?trigraphs. ?This is a time-critical inner loop. ?*/
> ?void
> @@ -109,12 +185,41 @@ _cpp_clean_line (cpp_reader *pfile)
> ? buffer->cur_note = buffer->notes_used = 0;
> ? buffer->cur = buffer->line_base = buffer->next_line;
> ? buffer->need_line = false;
> - ?s = buffer->next_line - 1;
> + ?s = buffer->next_line;
>
> ? if (!buffer->from_stage3)
> ? ? {
> ? ? ? const uchar *pbackslash = NULL;
>
> +#ifdef HAVE_SSE42
> + ? ? ?if (cpu_has_sse42)
> + ? ? ? {
> + ? ? ? ? for (;;)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? /* Drop into slow path if ? or nothing is found. */
> + ? ? ? ? ? ? if (search_line_sse42 (s, buffer->rlimit, &s) == false
> + ? ? ? ? ? ? ? ? || *s == '?')
> + ? ? ? ? ? ? ? break;
> +
> + ? ? ? ? ? ? c = *s;
> +
> + ? ? ? ? ? ? /* Special case for backslash which is reasonably common.
> + ? ? ? ? ? ? ? ?Continue searching using the fast path */
> + ? ? ? ? ? ? if (c == '\\')
> + ? ? ? ? ? ? ? {
> + ? ? ? ? ? ? ? ? pbackslash = s;
> + ? ? ? ? ? ? ? ? s++;
> + ? ? ? ? ? ? ? ? continue;
> + ? ? ? ? ? ? ? }
> +
> + ? ? ? ? ? ? /* \n or \r here. Process it below. */
> + ? ? ? ? ? ? goto found;
> + ? ? ? ? ? }
> + ? ? ? }
> +#endif
> +
> + ? ? ?s--;
> +
> ? ? ? /* Short circuit for the common case of an un-escaped line with
> ? ? ? ? no trigraphs. ?The primary win here is by not writing any
> ? ? ? ? data back to memory until we have to. ?*/
> @@ -124,6 +229,9 @@ _cpp_clean_line (cpp_reader *pfile)
> ? ? ? ? ?if (__builtin_expect (c == '\n', false)
> ? ? ? ? ? ? ?|| __builtin_expect (c == '\r', false))
> ? ? ? ? ? ?{
> +#ifdef HAVE_SSE42
> + ? ? ? ? ? found:
> +#endif
> ? ? ? ? ? ? ?d = (uchar *) s;
>
> ? ? ? ? ? ? ?if (__builtin_expect (s == buffer->rlimit, false))
>
>
>
> --
> ak@linux.intel.com -- Speaking for myself only.
>