Patch for review: enhancement to __builtin_strlen

Clang Frontend
1

Hi,

I would like to offer a patch for review that extends the use of the
compile-time evaluation of __builtin_strlen to include immutable
null-terminated const char arrays, i.e. beyond just standard string
literals. (It will still fall back to runtime use of library strlen, if
compile-time evaluation is not possible/required -- this side of the
functionality is not changed).

This is not a bug fix but a feature enhancement, which I believe may have
broader appeal to those developing with C++11 and, in particular, with
user-defined literals.

The target use for this would be in generating transparent wrapper classes
for user-defined literals, so that these may be used in situations wherever
normal strings may be used.

Let's say we have the following simplified setup:

template <char... String>
struct Literal {
  private:
  typedef const char type[sizeof...(String)+1];
  static constexpr type string = { String..., 0 };

  public:
  constexpr operator const type&() const { return string; }

  // room for more implementation, such as operator and
  // also string manipulation, such as operator+, and so on.
  }
};

template <char... String> constexpr char Literal<String...>::string;

template <char... String>
constexpr Literal<String...> operator"" _str() {
  return Literal<String...>();
}

With the attached patch, __builtin_strlen(12345_str) will now return 5,
rather than throw a compiler error, and so opens up the use of such a
wrapper class to macros which make use of __builtin_strlen.

The patch is intended to be very conservative in terms of what it will
accept, and so the extension only allows constant sized arrays of const char
(__builtin_strlen limits this to char, although wchar_t, etc. would work
otherwise) and where the compiler can evaluate the expression as a constant
array (i.e. not a pointer or an lvalue of an array that can be modified at
runtime, for example). I believe there are adequate checks to stop
incorrect compilation, for example, incorrectly doing a compile-time
evaluation of __builtin_strlen on a variable which is not immutable, but
please can this be particularly verified by someone.

I have included a test-case in the patch.

Please let me know if this interests anyone.

Thanks
Andy

strlen.diff (4.82 KB)

2

Hi,

I would like to offer a patch for review that extends the use of the
compile-time evaluation of __builtin_strlen to include immutable
null-terminated const char arrays, i.e. beyond just standard string
literals. (It will still fall back to runtime use of library strlen, if
compile-time evaluation is not possible/required -- this side of the
functionality is not changed).

This is not a bug fix but a feature enhancement, which I believe may have
broader appeal to those developing with C++11 and, in particular, with
user-defined literals.

This seems like a completely reasonable enhancement. As we inevitably
shift towards making more library functions usable in constant
expressions, this seems very much like a feature we will want.

The patch is intended to be very conservative in terms of what it will
accept, and so the extension only allows constant sized arrays of const char
(__builtin_strlen limits this to char, although wchar_t, etc. would work
otherwise) and where the compiler can evaluate the expression as a constant
array (i.e. not a pointer or an lvalue of an array that can be modified at
runtime, for example). I believe there are adequate checks to stop
incorrect compilation, for example, incorrectly doing a compile-time
evaluation of __builtin_strlen on a variable which is not immutable, but
please can this be particularly verified by someone.

I think the patch is actually too conservative. For instance, I would
like for the following to work:

  constexpr const char *p = "foobar";
  constexpr int n = __builtin_strlen(p);

More generally, the builtin should behave as if it were defined as:

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

... except that it should be faster (and not limited by the constexpr
recursion depth limit).

To this end, I suggest you always evaluate the pointer argument,
rather than only doing so if it has a constant array type. Use
EvaluatePointer rather than Expr::EvaluateAsRValue in order to pick up
values of constexpr function parameters and the like. Finally, to
extract characters from an LValue, you can repeatedly call
HandleLValueToRValueConversion and LValue::adjustIndex until you hit a
NUL. HandleLValueToRValueConversion will return false if you leave the
string, so you don't need to explicitly check for that case.

For efficiency, you should check whether the LValue's base is a
StringLiteralExpr, and if so, use a fast-path (be sure to take account
of the offset, in case the pointer doesn't point to the start of the
literal).

The above is still inefficient in the not-a-string-literal case, due
to the repeated work in HandleLValueToRValueConversion. To avoid that,
you could instead (after evaluating the pointer):
* Remove the last element from the LValue, if there is one (if not,
use the method above above -- this might be "__builtin_strlen(&c)",
where we might have "const char c = 0;").
* Use findMostDerivedSubobject to find the resulting type. If it's
not an array, use the method above -- this might be
"__builtin_strlen(&x.c)", where we might have "struct X { char c = 0;
} constexpr x;".
* Use HandleLValueToRValueConversion on the resulting LValue to get
an APValue. For efficiency, we don't build APValue::Array objects from
string literals, so you will either get an APValue::LValue
representation or you'll get an APValue::LValue which refers to a
string literal expression.
* Use the approach in your patch to deal with the array or string
literal, starting from the array index you removed in the first step.

3

Ok, attached then is a first patch towards this end. It works in most
scenarios, and I have found only one real place where it doesn't, which
is using __builtin_strlen inside a constexpr function with a function
parameter as the expression, but I am pretty sure this is not a fault
in my implementation, but rather that __builtin_strlen as it currently
stands doesn't work inside constexpr functions. I'll look into it.

I'd like to see if we can get this first patch committed, then I can
look at doing the next stage (otherwise, I just end up with massive
sets of patches that never get committed!...)

I haven't followed exactly your suggestions, but maybe you will spot
some of them in the code anyway. I actually made the bold step of
splitting out the functionality into its own function, namely
Expr::EvaluateAsString which then returns a folded, truncated
std::string result on success. __builtin_strlen then calls this
and returns the length of this string.

The approach I took was to consider that the StringLiteral (and I
extended it to include ObjCStringLiteral) is the standard case and
is therefore treated as a first-class citizen, and std::string is
extracted directly.

If it is not a StringLiteral then I check that the expression is either
a const char* or const char[n] type. I kept with EvaluateAsRValue,
since this works adequately and, I'm afraid to say, I couldn't get
EvaluatePointer to work at all. The generated APValue result will then
be either an Array or an LValue kind. If it is an LValue kind, then
it is examined to see whether it is a StringLiteral expression or a
VarDecl. The former drops out easily, the latter is then evaluated
(in most cases this is already done and it is the cached value that is
returned), and will in most cases drop out as an Array APValue. And,
finally, an Array kind is copied into std::string and returned if it
is null terminated.

Array and pointer offsets are handled, as is truncation at the first
null character following the offset.

Of your corner cases, I've supported:

constexpr char c = 0;
__builtin_strlen(&c);

The other, i.e.,

struct X { char a; };
__builtin_strlen(&x.c);

I haven't supported in this patch. I have a mostly working solution
here, but it needs more thought. For example, is the above enough?
If it is, then like the first corner case, it can only be evaluated
where the value is 0 (which doesn't have many applications!). But
if you want the following to work...

struct X { int a; char b; char c; char d; float e; };
constexpr X x = { 1234, 'a', 'b', 0, 5.3f }
__builtin_strlen(&x.b);

then I need to think about packing, making sure that it only moves
across types that are char, and not any other types (due to byte
ordering on the target), etc. etc.

Beyond this, it would be as well to point out that I don't think
that you can do this with a constexpr function either...

With this in mind, is it really worthwhile to pursue it?

In the meantime, is the patch as it stands good enough to commit?!

Cheers
Andy

strlen.diff (9.46 KB)

4

I think the patch is actually too conservative. For instance, I would
like for the following to work:

constexpr const char *p = "foobar";
constexpr int n = __builtin_strlen(p);

More generally, the builtin should behave as if it were defined as:

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

... except that it should be faster (and not limited by the constexpr
recursion depth limit).

Ok, attached then is a first patch towards this end. It works in most
scenarios, and I have found only one real place where it doesn't, which
is using __builtin_strlen inside a constexpr function with a function
parameter as the expression, but I am pretty sure this is not a fault
in my implementation, but rather that __builtin_strlen as it currently
stands doesn't work inside constexpr functions. I'll look into it.

This will be because you're still using Expr::EvaluateAsRValue: that
won't work for references to constexpr function parameters, because it
doesn't operate in the same EvalInfo context.

I'd like to see if we can get this first patch committed, then I can
look at doing the next stage (otherwise, I just end up with massive
sets of patches that never get committed!...)

I haven't followed exactly your suggestions, but maybe you will spot
some of them in the code anyway. I actually made the bold step of
splitting out the functionality into its own function, namely
Expr::EvaluateAsString which then returns a folded, truncated
std::string result on success. __builtin_strlen then calls this
and returns the length of this string.

This approach has the downside of copying the string even when it's a
string literal. This construct appears pretty frequently in code using
various glibc functions which are implemented as macros, so that may
be a significant issue for some code.

I kept with EvaluateAsRValue,
since this works adequately and, I'm afraid to say, I couldn't get
EvaluatePointer to work at all.

What sort of issues were you having?

[...]

If it is, then like the first corner case, it can only be evaluated
where the value is 0 (which doesn't have many applications!). But
if you want the following to work...

struct X { int a; char b; char c; char d; float e; };
constexpr X x = { 1234, 'a', 'b', 0, 5.3f }
__builtin_strlen(&x.b);

We don't allow this for a constexpr function, so we don't need to
allow it here either. Indeed, there are simple cases where this would
be impossible:

struct X { char c[8]; void *p; };
constexpr X x = { 1, 2, 3, 4, 5, 6, 7, 8, &x; };
constexpr int n = __builtin_strlen(x.c); // ???

Beyond this, it would be as well to point out that I don't think
that you can do this with a constexpr function either...

With this in mind, is it really worthwhile to pursue it?

No, I don't think so.

5

Ok, attached then is a first patch towards this end. It works in most
scenarios, and I have found only one real place where it doesn't, which
is using __builtin_strlen inside a constexpr function with a function
parameter as the expression, but I am pretty sure this is not a fault
in my implementation, but rather that __builtin_strlen as it currently
stands doesn't work inside constexpr functions. I'll look into it.

This will be because you're still using Expr::EvaluateAsRValue: that
won't work for references to constexpr function parameters, because it
doesn't operate in the same EvalInfo context.

Ok, I didn't realise this was the reason -- I'm still learning how the code works!

I'd like to see if we can get this first patch committed, then I can
look at doing the next stage (otherwise, I just end up with massive
sets of patches that never get committed!...)

I haven't followed exactly your suggestions, but maybe you will spot
some of them in the code anyway. I actually made the bold step of
splitting out the functionality into its own function, namely
Expr::EvaluateAsString which then returns a folded, truncated
std::string result on success. __builtin_strlen then calls this
and returns the length of this string.

This approach has the downside of copying the string even when it's a
string literal. This construct appears pretty frequently in code using
various glibc functions which are implemented as macros, so that may
be a significant issue for some code.

Yes, this is a fair point and it is the unfortunate side-effect of my attempt to make what I saw as a useful feature out of the code. I have an alternative suggestion, please see below.

I kept with EvaluateAsRValue,
since this works adequately and, I'm afraid to say, I couldn't get
EvaluatePointer to work at all.

What sort of issues were you having?

There is an assert at the top of EvaluatePointer to ensure Expr is an rvalue, which is not necessarily the case. I'm afraid I don't have the code nor my test-cases in front of me right now so I can't give you an exact example. Since I wasn't aware (as I said above) of the disadvantages of using EvaluateAsRValue, and because I had found in my testing that using EvaluatePointer actually did not work in any case in the function argument case, I kept with EvaluateAsRValue since it worked in all other scenarios. Hence my thought (erroneous, from what you say) that this issue with function arguments was due to some other reason.

[...]

If it is, then like the first corner case, it can only be evaluated
where the value is 0 (which doesn't have many applications!). But
if you want the following to work...

struct X { int a; char b; char c; char d; float e; };
constexpr X x = { 1234, 'a', 'b', 0, 5.3f }
__builtin_strlen(&x.b);

We don't allow this for a constexpr function, so we don't need to
allow it here either. Indeed, there are simple cases where this would
be impossible:

struct X { char c[8]; void *p; };
constexpr X x = { 1, 2, 3, 4, 5, 6, 7, 8, &x; };
constexpr int n = __builtin_strlen(x.c); // ???

Beyond this, it would be as well to point out that I don't think
that you can do this with a constexpr function either...

With this in mind, is it really worthwhile to pursue it?

No, I don't think so.

Good, but you had me concerned by including it in your corner cases.

So, now for my suggestion. Actually, I have two. My first is this: as one coming from the outside, ExprConstant.cpp is quite a difficult block of code to follow, since a lot of different functionality is contained and interwoven. My suggestion would be to separate out ExprConstant.cpp into separate files in an ExprConstant subfolder. It could then be possible to have the Expr member functions in one file, general purpose utility functions in another (e.g. the IsGlobalLValue and similar), and then the Visitor classes then split out into their own .h/.cpp files, and so on. This approach would make it much easier for others to learn the intricacies of this particular part of the compiler. Now, I would be quite willing to undertake this work, *if* (and its a big if) I could feel that if I did the work, that it would be appreciated, and more importantly, committed. So please say. I don't mind either way, but I don't want to undertake it for it to be simply rejected.

My suggestion, then, for an alternative to my previous patch would be to implement a string length evaluation visitor class (sorry, I haven't thought up a groovy class name for it yet!). This would then visit the Expr object, calculating any pointer arithmetic operations as it goes, down to either a StringLiteral expression, or a DeclRefExpr pointing to a StringLiteral variable or constexpr char array. The length can be calculated direct from this and the precalculated offset. No unnecessary string copying or LValue generation! I should expect this is the most efficient way, better even than EvaluatePointer and all the HandleLValueToRValueConversion operations as per your previous suggestion?

As you know, I am still learning my way around the code; I really do appreciate your time in all your advice and corrections.

Please let me know what you think of my two suggestions. I stand by ready and willing...

Thanks again,
Andy