Re: Help on memchr() EGLIBC assembly code

[Richard Henderson <rth@twiddle.net>]

On 07/30/2009 09:29 AM, Aurelien Jarno wrote:
> Thanks for this patch I have tried it, and it does not have the original
> problem I have reported. Unfortunately it does not pass the glibc
> testsuite. I'll try to debug the problem later (I don't own an alpha
> machine, and need to have internet access to debug it remotely).

This one passes the test suite (on x86, with replacements for the alpha 
builtins).


r~

typedef unsigned long word;

#ifdef __alpha__
#define cmpbeq0(X)	__builtin_alpha_cmpbge(0, (X))
#define extql		__builtin_alpha_extql
#define extqh		__builtin_alpha_extqh
#define insbl		__builtin_alpha_insbl
#define zap		__builtin_alpha_zap
#else
static word
cmpbeq0(word y)
{
  word i, r = 0;
  for (i = 0; i < 8; ++i)
    {
      unsigned char yc = (y >> i*8);
      if (yc == 0)
	r |= 1 << i;
    }
  return r;
}

static word
extql(word x, word y)
{
  return x >> ((y & 7) * 8);
}

static word
extqh(word x, word y)
{
  return x << (64 - ((y & 7) * 8));
}

static word
zap(word x, word y)
{
  word i, mask = 0;
  for (i = 0; i < 8; ++i)
    if (y & (1 << i))
      mask |= (word)0xff << (i * 8);
  return x & ~mask;
}

static word
insbl(word x, word y)
{
  word byte_mask = 1ul << (y & 7);
  word byte_loc = (y & 7) * 8;
  return zap (x << byte_loc, ~byte_mask);
}
#endif

static inline word
ldq_u(word s)
{
  return *(const word *)(s & -8);
}

#define unlikely(X)	__builtin_expect ((X), 0)
#define prefetch(X)	__builtin_prefetch ((void *)(X), 0)

#define find(X, Y)	cmpbeq0 ((X) ^ (Y))

void *
memchr (const void *xs, int xc, word n)
{
  const word *s_align;
  const word s = (word) xs;
  word t, current, found;

  if (unlikely (n == 0))
    return 0;

  current = ldq_u (s);

  /* Replicate low byte of XC into all bytes of C.  */
  t = insbl (xc, 1);			/* 000000c0 */
  t = (xc & 0xff) | t;			/* 000000cc */
  t = (t << 16) | t;			/* 0000cccc */
  const word c = (t << 32) | t;		/* cccccccc */

  /* When N <= 8, we can perform the entire comparison in one go.
     Load the N bytes into the low part of CURRENT, via an unaligned
     quadword load sequence, and treat it as the last aligned word read.  */
  if (unlikely (n <= 8))
    {
      /* Tweak the standard unaligned quadword load sequence by issuing
	 the second ldq_u at (s + n - 1) instead of (s + 8 - 1).  This
	 avoids crossing a page boundary when S+N doesn't.  */
      word last = extqh (ldq_u (s + n - 1), s);
      word first = extql (current, s);
      current = first | last;
      s_align = (const word *) s;
      goto last_quad;
    }

  /* Align the source, and decrement the count by the number
     of bytes searched in the first word.  */
  s_align = (const word *)(s & -8);
  n += (s & 7);

  /* Deal with misalignment in the first word for the comparison.  */
  {
    word mask = -1ul << (s & 7);
    found = find (current, c) & mask;
    if (unlikely (found))
      goto found_it;
  }

  s_align++;
  n -= 8;

  /* If the block is sufficiently large, align to cacheline and prefetch.  */
  if (unlikely (n >= 256))
    {
      /* Prefetch 3 cache lines beyond the one we're working on.  */
      prefetch (s_align + 8);
      prefetch (s_align + 16);
      prefetch (s_align + 24);

      while ((word)s_align & 63)
	{
	  current = *s_align;
	  found = find (current, c);
	  if (found)
	    goto found_it;
	  s_align++;
	  n -= 8;
	}

	/* Within each cacheline, advance the load for the next word
	   before the test for the previous word is complete.  This
	   allows us to hide the 3 cycle L1 cache load latency.  We
	   only perform this advance load within a cacheline to prevent
	   reading across page boundary.  */
#define CACHELINE_LOOP				\
	do {					\
	  word i, next = s_align[0];		\
	  for (i = 0; i < 7; ++i)		\
	    {					\
	      current = next;			\
	      next = s_align[1];		\
	      found = find (current, c);	\
	      if (unlikely (found))		\
		goto found_it;			\
	      s_align++;			\
	    }					\
	  current = next;			\
	  found = find (current, c);		\
	  if (unlikely (found))			\
	    goto found_it;			\
	  s_align++;				\
	  n -= 64;				\
	} while (0)
      
      /* While there's still lots more data to potentially be read,
	 continue issuing prefetches for the 4th cacheline out.  */
      while (n >= 256)
	{
	  prefetch (s_align + 24);
	  CACHELINE_LOOP;
	}

      /* Up to 3 cache lines remaining.  Continue issuing advanced
	 loads, but stop prefetching.  */
      while (n >= 64)
	CACHELINE_LOOP;
    }

  /* Quadword aligned loop.  */
  current = *s_align;
  while (n > 8)
    {
      found = find (current, c);
      if (unlikely (found))
	goto found_it;
      current = *++s_align;
      n -= 8;
    }

 last_quad:
  {
    word mask = -1ul << n;
    found = find (current, c) & ~mask;
    if (found == 0)
      return 0;
  }

 found_it:
  {
    word offset;

#ifdef __alpha_cix__
    offset = __builtin_alpha_cttz (found);
#else
    /* Extract LSB.  */
    found &= -found;

    /* Binary search for the LSB.  */
    offset  = (found & 0x0f ? 0 : 4);
    offset += (found & 0x33 ? 0 : 2);
    offset += (found & 0x55 ? 0 : 1);
#endif

    return (void *)((word)s_align + offset);
  }
}