It fails even if s1/s2/s are all const char [].
What cxx_eval_builtin_function_calls sees is after cxx_eval_constant_expression
as args[0] is
(const void *) &s1
and the middle-end obviously can't do anything with that.
While the var may have DECL_INITIAL, if it isn't const, we don't know if we can use it, and the middle-end I think will not look at DECL_INITIAL anyway.
Furthermore, what about cases like:
constexpr int foo (char x, char y)
{
  char a[10] = "abcde";
  a[2] = x;
  a[4] = y;
  return __builtin_memcmp (a, "abAdB", 6);
}
etc.?  Guess we'd need to be able to convert a CONSTRUCTOR to STRING_CST on the fly.  Furthermore, the generic folding will give us as return value say for strstr or similar functions that return pointers into the arguments something like STRING_CST + value, while we in the end need instead ADDR_EXPR of the variable plus something.
So perhaps we need to handle these builtins in the C++ FE?
Jason, any thoughts on this?

I think you need to handle some of the builtin folding in the C++ FE.

Perhaps we then need some helper function partly similar to cxx_eval_array_ref, that would for an object (or address of it?) and some uhwi index attempt to return some byte from the object, and then if the middle-end folding doesn't yield anything, handle these builtins by using that helper in a loop to grab bytes from one or two input strings, then perform the needed action on them as if we have open-coded those routines in trivial C loops.
As even
constexpr char
foo (int x)
{
  char a[] = { 'a', 'b', 'c', 'd', '\0' };
  char *b = &a[0];
  return ((unsigned char *)b)[x];
}

constexpr char a = foo (0);
is rejected, I think we can't use the existing routines here though, we want to be able to access bytes of anything initialized.

Meanwhile, maybe this could be punted to the library, making use of __builtin_constant as a building block?  I don't know what guarantees __builtin_constant officially gives in constexpr, but at least the below compiles fine with GCC 7, in both -std=gnu++14 and -std=gnu++17 modes.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <string>

constexpr size_t constexpr_strlen(const char* s) {
  return *s ? constexpr_strlen (s + 1) + 1 : 0;
}

template <class T>
struct ce_char_traits : std::char_traits<T> {
    using char_type = typename std::char_traits<T>::char_type;

    static constexpr std::size_t length(const char_type* s) noexcept {
      if (__builtin_constant_p (s))
	return constexpr_strlen (s);

      return __builtin_strlen (s);
    }
};

static_assert (ce_char_traits<char>::length ("") == 0);
static_assert (ce_char_traits<char>::length ("hello") == 5);
static_assert (ce_char_traits<char>::length ("he\0llo") == 2);

static const char array[] = "foo";
static_assert (ce_char_traits<char>::length (array) == 3);

That doesn't work in this case:

constexpr bool str()
{
  char s[] = "str";
  return ce_char_traits<char>::length(s) == 3;
}

static_assert( str() );

i.e. it works OK for C++11-style constant expressions, but not C++14 ones.

Hmm.  I'd argue that __builtin_constant_p should return true in that case, since we're in a constexpr?

In any case, changing the test like this:

-   if (__builtin_constant_p (s))
+   if (__builtin_constant_p (s[0]))

makes that work.  I.e, this compiles:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <string>

constexpr size_t constexpr_strlen(const char* s)
{
  size_t count = 0;

  while (*s++)
    count++;

  return count;
}

template <class T>
struct ce_char_traits : std::char_traits<T>
{
  using char_type = typename std::char_traits<T>::char_type;

  static constexpr std::size_t length(const char_type* s) noexcept
  {
    if (__builtin_constant_p (s[0]))
      return constexpr_strlen (s);

    return __builtin_strlen (s);
  }
};

static_assert (ce_char_traits<char>::length ("") == 0);
static_assert (ce_char_traits<char>::length ("hello") == 5);
static_assert (ce_char_traits<char>::length ("he\0llo") == 2);

static const char array[] = "foo";
static_assert (ce_char_traits<char>::length (array) == 3);

constexpr bool str()
{
  char s[] = "str";
  return ce_char_traits<char>::length(s) == 3;
}

constexpr bool str1()
{
  char s[] = "str";
  s[0] = 'l';
  s[1] = '\0';
  return ce_char_traits<char>::length(s) == 1;
}

constexpr bool str2()
{
  char s[3] {};
  s[0] = 'l';
  s[1] = '\0';
  return ce_char_traits<char>::length(s) == 1;
}

constexpr bool str3()
{
  char s = {};
  return ce_char_traits<char>::length(&s) == 0;
}

static_assert( str() );
static_assert( str1() );
static_assert( str2() );
static_assert( str3() );
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

TBH, though I do think being able to use different algorithms for compile/runtime is useful and a good idea, making the __builtin_strlen etc. builtins works OOTB would of course be great.  I'm merely suggesting the __builtin_constant_p idea here, in case it has a better chance of having P0426R1 addressed in GCC7.

Also, AFAICS, GCC doesn't have __builtin_wcslen (and equivalents for  char16_t/char32_t), etc. yet.  The separate compile/runtime paths approach allows calling into the C runtime's optimized wcslen (etc.) when not in a compile-time context without having to depend on adding the built-ins.

I think there was a bug report in the last month or so asking for some builtin to detect when we're in a constexpr context.

FWIW, I've tried to poke a bit more at this, to try to make it _not_ work, but couldn't.  It seems to always do what we need.  These all work/compile too:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
constexpr int constexpr_strcmp(const char *s1, const char *s2)
{
  while (*s1 != '\0' && *s1 == *s2)
    {
      s1++;
      s2++;
    }

  if (*s1 < *s2)
    return -1;
  else if (*s1 > *s2)
    return 1;
  return 0;
}

constexpr int my_strcmp(const char *s1, const char *s2)
{
  if (__builtin_constant_p (s1[0])
      && __builtin_constant_p (s2[0]))
    return constexpr_strcmp (s1, s2);

  return strcmp (s1, s2);
}

constexpr bool str4()
{
  char s[4]= {};
  int i = 0;
  for (; i < 3; i++)
    s[i] = i + 1;
  return ce_char_traits<char>::length(s) == 3;
}

static_assert( str4() );

constexpr int foo (char x, char y)
{
  char a[10] = "abcde";
  a[2] = x;
  a[4] = y;
  return ce_char_traits<char>::length(a);
}

static_assert (foo ('1', '2') == 5);
static_assert (foo ('1', '\0') == 4);

bool runtime()
{
  char s[] = "str";
  s[0] = 'l';
  s[1] = '\0';
  return ce_char_traits<char>::length(s) == 1;
}

bool runtime2()
{
  char s[4]= {};
  int i = 0;
  for (; i < 3; i++)
    s[i] = i + 1;
  return ce_char_traits<char>::length(s) == 3;
}

bool runtime3()
{
  constexpr char s[] = "str";
  return ce_char_traits<char>::length(s) == 1;
}

int main ()
{
  assert (runtime ());
  assert (runtime2 ());
  assert (runtime3 ());
}

static_assert (my_strcmp("hello", "hello") == 0);
static_assert (my_strcmp("hello", "hell2") > 0);
static_assert (my_strcmp("hell2", "hello") < 0);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

And I confirmed that "constexpr_strlen" / "constexpr_strcmp" are NOT emitted / called as runtime functions, both at -O0 and -O2.

I don't think it works that well.
Consider:
int
str6 (int a)
{
  char s[] = "strabcdefgh";
  s[2] = a;
  return ce_char_traits<char>::length(s);
}

int
str7 (int a)
{
  char s[] = "strabcdefgh";
  s[2] = a;
  return __builtin_strlen(s);
}

The latter is compiled into standard strlen sequence, depending on tuning etc., the former is always the constexpr_strlen loop at runtime.

Ok, so s[2] is not constant, while s[0] is, in that case.

AFAICS, changing constexpr_strlen to this:

constexpr size_t constexpr_strlen(const char* s)
{
  const char *p = s;

  while (__builtin_constant_p (*p) && *p)
    p++;
  if (!__builtin_constant_p (p[0]))
    return p - s + __builtin_strlen (p);
  return p - s;
}

makes it work as expected.  All the previous static_assert tests compile without
error, and, we now get a call to strlen at run-time, AFAICS (I replaced that
__builtin_strlen call with a call to an "extern_strlen" function declared in another compile unit instead to verify).

Could you confirm?

This seems to work equally well (or better):

// true if the whole string is known at compile time.
static inline constexpr bool constant_string(const char *s)
{
  while (__builtin_constant_p (*s) && *s)
    s++;
  if (!__builtin_constant_p (*s))
    return false;
  return true;
}

constexpr size_t constexpr_strlen(const char* s)
{
  const char *p = s;
  while (*p)
    p++;
  return p - s;
}

and then use it in ce_char_traits like:

  static constexpr std::size_t length(const char_type* s) noexcept
  {
    if (constant_string(s))
      return constexpr_strlen (s);

    return __builtin_strlen (s);
  }

I.e., decouple the "is the whole string constant" from the strlen algorithm.
This should make it easier to reuse the "is compile-time string" in other compile-time algorithms, though the previous version in comment #11 potentially optimized the computing the length of the constant prefix part of the string.  (which is probably not a common use case to aim for anyway.)

Sorry for the constant spam...

If we need the "if constexpr()" that is proposed for C++20, we might as well implement that (and enable it in system headers for C++17 if that's useful), it seems better than abusing __builtin_constant_p, which is getting contradictory requirements from its various uses:
- constexpr (forces very early lowering)
- warning/error (forbid splitting or anything that might create calls with constants that did not exist in the user's code, or lower to false before such transformation)
- optimization (wants to delay lowering to false quite late (though not so late that the code without __bcp isn't properly optimized) and likes isolating a path that makes the argument constant)
etc

(though at first glance your latest version seems likely to work well enough)

AFAIK, the "if constexpr()" proposal was sent back for more work [1], seems premature to support it, while I'd hope that the __builtin_constant_p approach would allow supporting constexpr char_traits in GCC7 (either 7.1 or some later point release).

(I don't exactly see where's the contradiction, but I'm not a real GCC hacker.)

[1] - https://botondballo.wordpress.com/2017/03/27/trip-report-c-standards-meeting-in-kona-february-2017/

(In reply to Pedro Alves from comment #6)
> Hmm.  I'd argue that __builtin_constant_p (s) should return true in that case,
> since we're in a constexpr?

No, the compiler is right; the address of the local array variable is not constant, only its contents.

(In reply to Marc Glisse from comment #13)
> it seems better than abusing __builtin_constant_p, which is getting
> contradictory requirements from its various uses:
> - constexpr (forces very early lowering)

I'm not sure what you mean here; constexpr specifically delays lowering within a constexpr function until we're actually trying to evaluate to a constant value.

(In reply to Jason Merrill from comment #16)
> (In reply to Marc Glisse from comment #13)
> > it seems better than abusing __builtin_constant_p, which is getting
> > contradictory requirements from its various uses:
> > - constexpr (forces very early lowering)
> 
> I'm not sure what you mean here; constexpr specifically delays lowering
> within a constexpr function until we're actually trying to evaluate to a
> constant value.

Evaluating a constexpr function forces the front-end to evaluate __builtin_constant_p. That's very early compared to usual __builtin_constant_p lowering during gimple optimizations. However, now that I think about it, I can't remember why I thought this would be an issue. constexpr evaluation only happens when required, not as an optimization, and when it happens the whole function gets evaluated at compile-time, so I can't think of when we would miss an optimization this way...

I sent a patch using the __builtin_constant_p idea:
 https://gcc.gnu.org/ml/gcc-patches/2017-04/msg00983.html

Author: palves
Date: Mon Jun 12 22:22:39 2017
New Revision: 249137

URL: https://gcc.gnu.org/viewcvs?rev=249137&root=gcc&view=rev
Log:
Finish implementing P0426R1 "Constexpr for std::char_traits" for C++17

As discussed in PR c++/80265 ("__builtin_{memcmp,memchr,strlen} are
not usable in constexpr functions"), use __builtin_constant_p to tell
whether we can defer to a constexpr algorithm.

I used __always_inline__ just to be thorough.  It isn't really really
necessary as far as I could determine.

Changes like these:

	 if (__n == 0)
	   return 0;
 -	return wmemcmp(__s1, __s2, __n);
 +	else
 +	  return wmemcmp(__s1, __s2, __n);

are necessary otherwise G++ complains that we're calling a
non-constexpr function, which looks like a a manifestation of PR67026
to me.

libstdc++-v3:
2017-06-12  Pedro Alves  <palves@redhat.com>

	* doc/xml/manual/status_cxx2017.xml: Update C++17 constexpr
	char_traits status.
	* doc/html/*: Regenerate.

	* include/bits/char_traits.h (_GLIBCXX_ALWAYS_INLINE): Define if
	not already defined.
	(__cpp_lib_constexpr_char_traits): Uncomment.
	(__constant_string_p, __constant_char_array_p): New.
	(std::char_traits<char>, std::char_traits<wchar_t>): Add
	_GLIBCXX17_CONSTEXPR on compare, length and find and use
	__constant_string_p, __constant_char_array_p and
	__builtin_constant_p to defer to __gnu_cxx::char_traits at compile
	time.

	* testsuite/21_strings/char_traits/requirements/
	constexpr_functions_c++17.cc: Uncomment
	__cpp_lib_constexpr_char_traits tests.  Uncomment
	test_compare<char>, test_length<char>, test_find<char>,
	test_compare<wchar_t>, test_length<wchar_t> and test_find<wchar_t>
	static_assert tests.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
    trunk/libstdc++-v3/include/bits/char_traits.h
    trunk/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++17.cc

Author: redi
Date: Tue Sep 12 16:27:01 2017
New Revision: 252030

URL: https://gcc.gnu.org/viewcvs?rev=252030&root=gcc&view=rev
Log:
Finish implementing P0426R1 "Constexpr for std::char_traits" for C++17

As discussed in PR c++/80265 ("__builtin_{memcmp,memchr,strlen} are
not usable in constexpr functions"), use __builtin_constant_p to tell
whether we can defer to a constexpr algorithm.

I used __always_inline__ just to be thorough.  It isn't really really
necessary as far as I could determine.

Changes like these:

	 if (__n == 0)
	   return 0;
 -	return wmemcmp(__s1, __s2, __n);
 +	else
 +	  return wmemcmp(__s1, __s2, __n);

are necessary otherwise G++ complains that we're calling a
non-constexpr function, which looks like a a manifestation of PR67026
to me.

libstdc++-v3:
2017-06-12  Pedro Alves  <palves@redhat.com>

	* doc/xml/manual/status_cxx2017.xml: Update C++17 constexpr
	char_traits status.
	* doc/html/*: Regenerate.

	* include/bits/char_traits.h (_GLIBCXX_ALWAYS_INLINE): Define if
	not already defined.
	(__cpp_lib_constexpr_char_traits): Uncomment.
	(__constant_string_p, __constant_char_array_p): New.
	(std::char_traits<char>, std::char_traits<wchar_t>): Add
	_GLIBCXX17_CONSTEXPR on compare, length and find and use
	__constant_string_p, __constant_char_array_p and
	__builtin_constant_p to defer to __gnu_cxx::char_traits at compile
	time.

	* testsuite/21_strings/char_traits/requirements/
	constexpr_functions_c++17.cc: Uncomment
	__cpp_lib_constexpr_char_traits tests.  Uncomment
	test_compare<char>, test_length<char>, test_find<char>,
	test_compare<wchar_t>, test_length<wchar_t> and test_find<wchar_t>
	static_assert tests.

Modified:
    branches/gcc-7-branch/libstdc++-v3/ChangeLog
    branches/gcc-7-branch/libstdc++-v3/doc/html/manual/status.html
    branches/gcc-7-branch/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
    branches/gcc-7-branch/libstdc++-v3/include/bits/char_traits.h
    branches/gcc-7-branch/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++17.cc

(In reply to palves from comment #19)
> Author: palves
> Date: Mon Jun 12 22:22:39 2017
> New Revision: 249137
> 
> URL: https://gcc.gnu.org/viewcvs?rev=249137&root=gcc&view=rev
> Log:
> Finish implementing P0426R1 "Constexpr for std::char_traits" for C++17
> 
> As discussed in PR c++/80265 ("__builtin_{memcmp,memchr,strlen} are
> not usable in constexpr functions"), use __builtin_constant_p to tell
> whether we can defer to a constexpr algorithm.
> 
> I used __always_inline__ just to be thorough.  It isn't really really
> necessary as far as I could determine.
> 
> Changes like these:
> 
> 	 if (__n == 0)
> 	   return 0;
>  -	return wmemcmp(__s1, __s2, __n);
>  +	else
>  +	  return wmemcmp(__s1, __s2, __n);
> 
> are necessary otherwise G++ complains that we're calling a
> non-constexpr function, which looks like a a manifestation of PR67026
> to me.
> 
> libstdc++-v3:
> 2017-06-12  Pedro Alves  <palves@redhat.com>
> 
> 	* doc/xml/manual/status_cxx2017.xml: Update C++17 constexpr
> 	char_traits status.
> 	* doc/html/*: Regenerate.
> 
> 	* include/bits/char_traits.h (_GLIBCXX_ALWAYS_INLINE): Define if
> 	not already defined.
> 	(__cpp_lib_constexpr_char_traits): Uncomment.
> 	(__constant_string_p, __constant_char_array_p): New.
> 	(std::char_traits<char>, std::char_traits<wchar_t>): Add
> 	_GLIBCXX17_CONSTEXPR on compare, length and find and use
> 	__constant_string_p, __constant_char_array_p and
> 	__builtin_constant_p to defer to __gnu_cxx::char_traits at compile
> 	time.
> 
> 	* testsuite/21_strings/char_traits/requirements/
> 	constexpr_functions_c++17.cc: Uncomment
> 	__cpp_lib_constexpr_char_traits tests.  Uncomment
> 	test_compare<char>, test_length<char>, test_find<char>,
> 	test_compare<wchar_t>, test_length<wchar_t> and test_find<wchar_t>
> 	static_assert tests.
> 
> Modified:
>     trunk/libstdc++-v3/ChangeLog
>     trunk/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
>     trunk/libstdc++-v3/include/bits/char_traits.h
>    
> trunk/libstdc++-v3/testsuite/21_strings/char_traits/requirements/
> constexpr_functions_c++17.cc

(In reply to Jonathan Wakely from comment #20)
> Author: redi
> Date: Tue Sep 12 16:27:01 2017
> New Revision: 252030
> 
> URL: https://gcc.gnu.org/viewcvs?rev=252030&root=gcc&view=rev
> Log:
> Finish implementing P0426R1 "Constexpr for std::char_traits" for C++17
> 
> As discussed in PR c++/80265 ("__builtin_{memcmp,memchr,strlen} are
> not usable in constexpr functions"), use __builtin_constant_p to tell
> whether we can defer to a constexpr algorithm.
> 
> I used __always_inline__ just to be thorough.  It isn't really really
> necessary as far as I could determine.
> 
> Changes like these:
> 
> 	 if (__n == 0)
> 	   return 0;
>  -	return wmemcmp(__s1, __s2, __n);
>  +	else
>  +	  return wmemcmp(__s1, __s2, __n);
> 
> are necessary otherwise G++ complains that we're calling a
> non-constexpr function, which looks like a a manifestation of PR67026
> to me.
> 
> libstdc++-v3:
> 2017-06-12  Pedro Alves  <palves@redhat.com>
> 
> 	* doc/xml/manual/status_cxx2017.xml: Update C++17 constexpr
> 	char_traits status.
> 	* doc/html/*: Regenerate.
> 
> 	* include/bits/char_traits.h (_GLIBCXX_ALWAYS_INLINE): Define if
> 	not already defined.
> 	(__cpp_lib_constexpr_char_traits): Uncomment.
> 	(__constant_string_p, __constant_char_array_p): New.
> 	(std::char_traits<char>, std::char_traits<wchar_t>): Add
> 	_GLIBCXX17_CONSTEXPR on compare, length and find and use
> 	__constant_string_p, __constant_char_array_p and
> 	__builtin_constant_p to defer to __gnu_cxx::char_traits at compile
> 	time.
> 
> 	* testsuite/21_strings/char_traits/requirements/
> 	constexpr_functions_c++17.cc: Uncomment
> 	__cpp_lib_constexpr_char_traits tests.  Uncomment
> 	test_compare<char>, test_length<char>, test_find<char>,
> 	test_compare<wchar_t>, test_length<wchar_t> and test_find<wchar_t>
> 	static_assert tests.
> 
> Modified:
>     branches/gcc-7-branch/libstdc++-v3/ChangeLog
>     branches/gcc-7-branch/libstdc++-v3/doc/html/manual/status.html
>     branches/gcc-7-branch/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
>     branches/gcc-7-branch/libstdc++-v3/include/bits/char_traits.h
>    
> branches/gcc-7-branch/libstdc++-v3/testsuite/21_strings/char_traits/
> requirements/constexpr_functions_c++17.cc

Did these fix it?

No, it worked around it by implementing char_traits a different way.

We also use these functions in <algorithm>, e.g. std::equal uses __builtin_memcmp, and that needs to be constexpr too.

We could keep using Pedro's trick everywhere, but it's not very scalable.

I think support in the compiler directly is likely to have better compile-time performance, and I've stated from the beginning that I'd prefer that, FWIW.

OTOH, meanwhile, AFAICT, there's nothing preventing factoring out the trick bits from char_traits into libstdc++-internal __constexpr_strlen/__constexpr_memcmp etc. functions, that fallback into the __builtin_xxx functions when arguments are not constexpr (just like the char_traits versions), and using those throughout instead in constexpr functions.

Yes, but then we'd have *three* versions of std::equal: the default implementation using a for-loop, the optimized one using memcmp for PODs, and the constexpr form of the latter which also uses a for-loop.

It would be more sensible to just use the default (not memcmp-optimized) one in constexpr contexts, but that requires using __builtin_constant_p in every function that is affected, instead of just replacing __builtin_memcmp with __constexpr_memcmp in the optimized version.

Also, the more work that the algorithm does, the more concerned I'd be that although the inputs are constant (and so we use the naive for-loop) the actual work done in the loop might be too much to inline, so we make a run-time call to the slow version when we could use memcmp.

(In reply to Jonathan Wakely from comment #24)
> Also, the more work that the algorithm does, the more concerned I'd be that
> although the inputs are constant (and so we use the naive for-loop) the
> actual work done in the loop might be too much to inline, so we make a

That should have read "might be too much to inline and/or unroll at compile-time".

> run-time call to the slow version when we could use memcmp.

I'm confused then -- how does making __builtin_memcmp natively work on constexpr contexts address the "but then we'd have *three* versions" concern?

Looking at the code, it does sound like you instead would want to 
tweak __equal_aux to end up with __simple==false when all __equal_aux's
arguments are constant.

As for the inlining/unrolling concern, if the compiler fails to completely optimize out an inline pure function where all its inputs are known constant, then it sounds like something that we'd want to fix in the compiler, regardless?

(In reply to Pedro Alves from comment #26)
> I'm confused then -- how does making __builtin_memcmp natively work on
> constexpr contexts address the "but then we'd have *three* versions" concern?

Because we wouldn't need to touch the code except to add 'constexpr' to the function definitions. The version using a for-loop would be valid in constant expressions, and the version using __builtin_memcmp would be valid in constant expressions. We wouldn't have to use any new __constexpr_memcmp function.

> Looking at the code, it does sound like you instead would want to 
> tweak __equal_aux to end up with __simple==false when all __equal_aux's
> arguments are constant.

Yes, that's what I meant by "It would be more sensible to just use the default (not memcmp-optimized) one ..."
 
> As for the inlining/unrolling concern, if the compiler fails to completely
> optimize out an inline pure function where all its inputs are known
> constant, then it sounds like something that we'd want to fix in the
> compiler, regardless?

Yes, maybe, but normal optimizations are allowed (maybe even expected?) to give up at some point aren't they? e.g. calling std::equal on two arrays with hundreds of thousands of elements - would that be expected to be optimized out?

When the std::equal call happens in a constant expression the compiler is *required* to evaluate it at compile-time (or fail to compile if it runs out of memory or some other implementation limit). When it's not in a constant expression the __builtin_constant_p result could be true but the compiler could still decide not to optimize out the actual for-loop and the comparisons, so we get the bad implementation at run-time when we could have called memcmp (I'm just guessing here, maybe that's not how the optimizers work).

> Looking at the code, it does sound like you instead would want to 
> tweak __equal_aux to end up with __simple==false when all __equal_aux's
> arguments are constant.

I suspect that wouldn't work, because we'd need to check whether the elements the iterator range point-to are themselves constant.

So back to the constexpr __builtin_memcmp, or __constexpr_memcmp ideas.

Though I still don't see how __constexpr_memcmp would make a difference wrt to number of __equal::equal implementations, but now I'm thinking that that's not what you meant.  From my view, __constexpr_memcmp implemented in a helper constexpr function or directly in the frontend (as __builtin_memcmp), is just an implementation detail of the function.  Ultimately, __constexpr_memcmp or constexpr __builtin_memcmp ends up interpreted in a similar way internally, I expect.

OK, our messages crossed.  Thanks for the clarification.  I can't really comment on the optimizers.

> I suspect that wouldn't work, because we'd need to check whether the
> elements the iterator range point-to are themselves constant.

I would like to add that the char_traits trick handles this by doing exactly that, checking whether all elements in the string/array are constant (__constant_string_p/__constant_char_array_p), before deferring to the naive for loop; a __constexpr_memcmp would do the same before falling back to __builtin_memcmp.  In my testing back then, the compiler/optimizer always folded away these loops.

(In reply to Pedro Alves from comment #28)
> So back to the constexpr __builtin_memcmp, or __constexpr_memcmp ideas.
> 
> Though I still don't see how __constexpr_memcmp would make a difference wrt
> to number of __equal::equal implementations, but now I'm thinking that
> that's not what you meant.

It's not what I meant :-)

What I mean is that when you call std::equal today, it either dispatches to a for-loop, or __builtin_memcmp. That's two.

If we replaced __builtin_memcmp with __constexpr_memcmp which either uses a for-loop or memcmp, then we have three. The foor-loop in __equal<false>::equal, or a for-loop in __constexpr_memcmp, or a call to __builtin_memcmp.

There are still only two versions of __equal<bool>::equal but we do have more code, and two for-loops that are effectively identical (one in __equal<false>::equal and one in __constexpr_memcmp). If the one in __constexpr_memcmp is guaranteed to always be optimized out that's great, but I don't know if it's guaranteed. Intuitively, adding more code doesn't seem like it's going to _help_ guarantee we optimize everything out :-)

> From my view, __constexpr_memcmp implemented in
> a helper constexpr function or directly in the frontend (as
> __builtin_memcmp), is just an implementation detail of the function. 
> Ultimately, __constexpr_memcmp or constexpr __builtin_memcmp ends up
> interpreted in a similar way internally, I expect.

I would hope so, but I'd like to be certain, not hopeful.


It would be nice if we could just add _GLIBCXX17_CONSTEXPR in a few places and then do:

--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -807,11 +807,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct __equal<true>
     {
       template<typename _Tp>
-	static bool
+	static _GLIBCXX14_CONSTEXPR bool
 	equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
 	{
 	  if (const size_t __len = (__last1 - __first1))
+	  {
+	    if (__builtin_constant_p( something something ))
+	      return __equal<false>::equal(__first1, __last1, __first2);
 	    return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len);
+	  }
 	  return true;
 	}
     };
 
(For some value of "something something", as you did for char_traits).

This is somewhere that https://wg21.link/p0595r0 would help again (and if the arguments aren't constants, we just get an error in __equal<false>::equal).

In that case, I think the "something something" you're looking for can be  char_trait's __constant_char_array_p:

+	      if (__constant_char_array_p(__first1, __len)
+		  && __constant_char_array_p(__first2, __len))
+		return __equal<false>::equal(__first1, __last1, __first2);

I've done a quick test here, and it works AFAICT.  Below's a standalone and slightly simplified version of std::equal with that change.  The static asserts don't fail, and the result at run time looks right too.

At -O0, the (runtime calls to) std::equal stay around, but AFAICT, there's no code generated for the __builtin_constant_p checks/loop in __constant_char_array_p.

Disassembling the generated code at -O2 I see that g++ fully optimizes out the equal1/equal2/equal2 calls to constant "1".  

Interestingly, the trick makes g++ optimize the test _better_ than the same code _without_ the __builtin_constant_p (i.e, better than current trunk).  Without the __builtin_char_array_p detour, we end up with calls to memcmp in the generated code instead of constant folding out everything.  (you'll need to comment out the static_assert calls too to try that out, of course.)
ISTR having observed something like this this too with the char_traits changes, though I'm not sure I ever mentioned it.

I've tried to increase the size of the arrays in the test to check whether that'd fool the optimizers, but it still works.  If you increase the size enough, you'll hit the -fconstexpr-loop-limit limit, in the loop inside __builtin_char_array_p, but you'd hit the exact same limit in the __equal<false>::equal's for loop anyway.  Bumping that limit, the test still works, though of course compilation takes noticeably longer.

~~~~~~~~~~~~~~~~~~~~~~~~
#include <algorithm>
#include <iterator>
#include <stdio.h>

namespace my_std
{
  /* This is currently in char_traits, could/should probably move
     elsewhere.  */
  template<typename _CharT>
    static _GLIBCXX_ALWAYS_INLINE constexpr bool
    __constant_char_array_p(const _CharT* __a, size_t __n)
    {
      size_t __i = 0;
      while (__builtin_constant_p(__a[__i]) && __i < __n)
	__i++;
      return __i == __n;
    }
	
  template<bool _BoolType>
    struct __equal
    {
      template<typename _II1, typename _II2>
	static constexpr bool
	equal(_II1 __first1, _II1 __last1, _II2 __first2)
	{
	  for (; __first1 != __last1; ++__first1, (void) ++__first2)
	    if (!(*__first1 == *__first2))
	      return false;
	  return true;
	}
    };

  template<>
    struct __equal<true>
    {
      template<typename _Tp>
      static constexpr bool
	equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
	{
	  if (const size_t __len = (__last1 - __first1))
	    {
#if 1
              // new bits are here
	      if (__constant_char_array_p(__first1, __len)
		  && __constant_char_array_p(__first2, __len))
		return __equal<false>::equal(__first1, __last1, __first2);
#endif

	      return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len);
	    }
	  return true;
	}
    };

  template<typename _II1, typename _II2>
  constexpr inline bool
  equal(_II1 __first1, _II1 __last1, _II2 __first2)
  {
      typedef typename std::iterator_traits<_II1>::value_type _ValueType1;
      typedef typename std::iterator_traits<_II2>::value_type _ValueType2;
      const bool __simple = ((std::__is_integer<_ValueType1>::__value
			      || std::__is_pointer<_ValueType1>::__value)
			     && std::__is_pointer<_II1>::__value
			     && std::__is_pointer<_II2>::__value
			     && std::__are_same<_ValueType1, _ValueType2>::__value);

      return my_std::__equal<__simple>::equal(__first1, __last1, __first2);
    }
}

struct S
{
  constexpr bool operator==(const S& rhs)
  {
    return i == rhs.i;
  }

  int i = 0;
};

template<typename T>
constexpr bool equal1()
{
  T s1[400] = {1, 2, 3, 1, 2, 3};
  T s2[400] = {1, 2, 3, 1, 2, 3};

  const size_t count = sizeof (s1) / sizeof (s1[0]);

  return (my_std::equal(s1, s1 + 3, s2 + 3)
	  && !my_std::equal(s1, s1 + 1, s2 + 1)
	  && my_std::equal(s1, s1 + count, s2));
}

constexpr bool equal2()
{
  int i1 = 0;
  int i2 = 0;

  return (my_std::equal(&i1, &i1 + 1, &i2));
}

constexpr bool equal3()
{
  S s1[400];
  S s2[400];

  const size_t count = sizeof (s1) / sizeof (s1[0]);
  
  for (size_t i = 0; i < count; i++)
    s1[i].i = s2[i].i = i;
  
  return (my_std::equal(s1, s1 + count, s2)
	  && !my_std::equal(s1, s1 + 1, s2 + 1));
}

// disable if you disable the new bits above too.
#if 1
static_assert (equal1<char>());
static_assert (equal1<int>());
static_assert (equal1<unsigned long long>());
static_assert (equal2());
static_assert (equal3());
#endif

int
main ()
{
#define TEST(EXPR) \
  printf (#EXPR " = %d\n", (int) EXPR)

  TEST (equal1<char>());
  TEST (equal1<int>());
  TEST (equal1<unsigned long long>());
  TEST (equal2());
  TEST (equal3());

  return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~

(In reply to Jonathan Wakely from comment #8)
> I think there was a bug report in the last month or so asking for some
> builtin to detect when we're in a constexpr context.

Now that we have (__builtin_)is_constant_evaluated, does __constant_string_p still serve a purpose, or could we replace it? ISTR __constant_string_p was causing various issues (including PR 86590).

(In reply to Jason Merrill from comment #16)
> (In reply to Marc Glisse from comment #13)
> > it seems better than abusing __builtin_constant_p, which is getting
> > contradictory requirements from its various uses:
> > - constexpr (forces very early lowering)
> 
> I'm not sure what you mean here; constexpr specifically delays lowering
> within a constexpr function until we're actually trying to evaluate to a
> constant value.

Bug 85746 for instance, where the problem is how hard we should "try".

Created attachment 45467 [details]
gcc9-pr86590.patch

Untested patch to use __builtin_is_constant_evaluated() here.  I believe it should help, the inliner should be able to see smaller inline functions and could make better decisions.

I just noticed that Jonathan has already written such a patch in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86590#c28 but didn't commit it (maybe because is_constant_evaluated was not committed yet, or because it was not sufficient to solve that PR).

(In reply to Marc Glisse from comment #35)
> I just noticed that Jonathan has already written such a patch in
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86590#c28 but didn't commit it
> (maybe because is_constant_evaluated was not committed yet, or because it
> was not sufficient to solve that PR).

I think in the exact PR86590 case in the end __builtin_is_constant_evaluated() hasn't helped, but it can in other cases; without it, the __builtin_constant_p isn't folded at least in the most common case where the argument is not constant early enough, it isn't folded during/after early inlining, nor soon after IPA inlining, it is just fab pass.  While with __builtin_is_constant_evaluated(), it can be optimized either before early inlining (if it is used directly in the function), or soon after early inlining (otherwise).

Hi, I ran into what I think is a variant of this bug.

Here's the problem presented with godbolt: https://godbolt.org/z/SP-4uG

And the contents of that link, as reproduced on my machine, are:

#include <string_view>
#include <cwchar>
static const std::wstring_view foo = L"foo";
static constexpr std::wstring_view bar = L"bar";

$ g++ --version
g++ (GCC) 8.2.1 20181127
$ g++ -c test.cpp -Wall -Wextra -std=c++17 # exit code 0
$ gcc9/bin/g++ --version
g++ (GCC) 9.0.1 20190225 (experimental)
$ gcc9/bin/g++ -c test.cpp -Wall -Wextra -std=c++17 # exit code 0
$ clang++ --version
clang version 7.0.1 (tags/RELEASE_701/final)
$ clang++ -c -Wall -Wextra test.cpp -std=c++17 -Wno-unused-const-variable -stdlib=libc++ # exit code 0
$ clang++ -c -Wall -Wextra test.cpp -std=c++17
test.cpp:4:36: error: constexpr variable 'bar' must be initialized by a constant expression
static constexpr std::wstring_view bar = L"bar";
                                   ^     ~~~~~~
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../include/c++/8.2.1/bits/char_traits.h:431:11: note: non-constexpr function 'wcslen' cannot be used in a constant expression
          return wcslen(__s);
                 ^
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../include/c++/8.2.1/string_view:100:39: note: in call to 'length(&L"bar"[0])'
      : _M_len{__str == nullptr ? 0 : traits_type::length(__str)},
                                      ^
test.cpp:4:42: note: in call to 'basic_string_view(&L"bar"[0])'
static constexpr std::wstring_view bar = L"bar";
                                         ^
1 error generated.

Relevant piece of code from libstdc++: https://github.com/gcc-mirror/gcc/blob/9fb89fa845c1b2e0a18d85ada0b077c84508ab78/libstdc%2B%2B-v3/include/bits/char_traits.h#L426-L431

Unfortunately, I can't really test clang with libstdc++ trunk. Please let me know if it is sufficient to leave this comment here or should I open another ticket?

char_traits<wchar_t> now uses either __builtin_constant_p or __builtin_is_constant_evaluated to avoid using wcslen in constant expressions.

If that isn't working with clang for some reason that's a separate issue (and maybe something clang needs to fix, e.g. by implementing __builtin_is_constant_evaluated).

It seems that clang doesn't support using __builtin_constant_p this way, so using char_traits<wchar_t> in constant expressions isn't going to work until they implement is_constant_evaluated.

The __constant_string_p function does work with the Intel compiler though (since icc 17.0.0 by the look of it), so is worth keeping.

I'm not sure if we really need these builtins in constexpr functions now, as we can use is_constant_evaluated to avoid dispatching to optimised implementations using memcmp. Maybe we can close this.

The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:69dc042f91c70458ffb6e7b147f093799cee2100

commit r10-5927-g69dc042f91c70458ffb6e7b147f093799cee2100
Author: Jason Merrill <jason@redhat.com>
Date:   Fri Jan 10 15:38:34 2020 -0500

    PR c++/80265 - constexpr __builtin_mem*.
    
    The library has already worked around this issue, but I was curious about
    why it wasn't working.  The answer: because we were passing &var to fold,
    which doesn't know about the constexpr values hash table.  Fixed by passing
    &"str" instead.
    
    	* constexpr.c (cxx_eval_builtin_function_call): Expose STRING_CST
    	to str/mem builtins.

Implemented.