How to create a new builtin in clang?

Hi,

I'd like to learn a little about how clang works on the inside, and would
like to have a go at implementing a new "builtin" function which forces an
expression to be folded to a constant. The idea would be that it would
either compile-time-evaluate the expression or halt compilation with an
error. I believe there isn't anything currently that does this for
arbitrary types, only integers.

What I envisage is something like...

   auto x = __builtin_fold(<expression>)

which returns a constant value of appropriate type for the expression.

I'd envisage it as a replacement for an already-possible two-step approach
as follows:

struct __fold_impl_1
    {
    static constexpr auto value = <expression>;
    };

...
auto x = __fold_impl_1::value;

The obvious down-side of the two-step approach is requiring a special macro
for generating __fold_impl_xxx for each folded expression, plus the
inconvenience and possible scope problems of having to use such a macro!
I'd also like it to work in non-C++11 code.

I could imagine that it should be very possible to get clang to generate
such a struct on-the-fly which avoided the scope problems and substitute the
expression for a reference to the value.

The questions I have are:

- how does one go about getting clang to build such substitutiary code in
this way?

- is this the best approach, or is there a better/simpler way?

I've been looking into how __builtin_constant_p and __extension__ work, as
well as the Expr::Evaluate* functions and
CodeGenFunction::tryEmitAsConstant, but to little gain I'm afraid! ;o)

Many thanks for any and all suggestions

Andy

Hello,

I'd like to learn a little about how clang works on the inside, and would
like to have a go at implementing a new "builtin" function which forces an
expression to be folded to a constant. The idea would be that it would
either compile-time-evaluate the expression or halt compilation with an
error. I believe there isn't anything currently that does this for
arbitrary types, only integers.

Maybe I'm missing something, but constexpr does exactly that:

struct Foo {
  constexpr Foo(int i) : i(i) {}
  Foo(int i, int dummy) : i(i) {}

  int i;
};

constexpr Foo myFoo = Foo(42);

constexpr Foo myFoo2 = Foo(42, 0);

As only <myFoo>, but not <myFoo2> can be initialized at compile-time, this results in
(TOT):

error: constexpr variable 'myFoo2' must be initialized by a constant expression
constexpr Foo myFoo2 = Foo(42, 0);
               ^ ~~~~~~~~~~

Jonathan

It does and it doesn't. If you declare a variable 'constexpr' then you can expect that a compile-time-evaluated constant is assigned to it. However, a 'constexpr'-declared variable is forever immutable (which may not be what you want) and if you do not declare a variable 'constexpr' then you cannot assume it will be given an initial value which is compile-time-evaluated. In this way, 'constexpr' can be considered merely a hint to the compiler, like 'inline' is: the compiler can choose whether to obey it or not, usually depending on the optimisation level. There is not, as far as I am aware, a way within the C++11 standard of actually forcing an expression to be evaluated by the compiler, except by tricks. On such way is as follows:

template <typename T, T Value>
struct Constant {
    static constexpr T value = Value;
};

#define CONST(X) Constant<decltype(X),(X)>::value

int value = CONST(... some expression ...);

This trick will not work, however, where 'T' is (for example) a double or a struct, since you cannot pass such a value as a template parameter.

Using __builtin_constant_p(...), it is possible to test whether an expression can be compile-time evaluated, the next logical step would be a builtin which returns the result of the evaluation itself. It would form a contract between user and compiler: the user would be sure that as long as his code compiles, his expression is evaluated by the compiler and never at runtime.

Andy

I’d like to learn a little about how clang works on the inside, and would
like to have a go at implementing a new “builtin” function which forces an
expression to be folded to a constant.

OK. The first thing you need to be aware of is that ‘folded to a constant’ is not the same as ‘evaluated as a constant expression’. The former case just means “take an expression, and use any tricks we know to reduce it to a compile-time constant”. The latter means following the relevant language standards, which is a nebulous affair:

  • In C{89,99,11}, precise rules are given for “integer constant expressions” (ICEs, which are required in various contexts), as well as for “constant expressions in initializers”. However, implementations are allowed to accept other (non-standard) forms of constant expression in initializers, and we do not have an implementation of the standard rules: instead, Expr::isConstantInitializer checks whether an expression is something we can emit as a constant (this is a superset of the set of expressions we can fold to a constant), and we use that to check whether an expression is a constant expression for the purpose of initialization. Expr::isIntegerConstantExpr checks whether an expression is an integer constant expression, following the language standard.

  • The situation in C++98 is similar to C, except that “integer constant expression” is renamed to “integral constant expression”, and implementations are not allowed to extend what “constant expression” means. However, they are allowed to use constant initialization for dynamic initializers which they are able to evaluate, which has the same consequences.

  • The situation in C++11 is completely different. The term “constant expression” is defined to cover a much broader set of cases there (which can be checked by Expr::isCXX11ConstantExpr). Implementations are still permitted to convert dynamic initialization to constant initialization if they can fold an expression.

Additionally, the set of things we can fold is slightly different in the different languages. Anyway, the point is, outside of C++11, we don’t really have an implemented, checkable notion of ‘constant expression’ other than ‘integer constant expression’.

The idea would be that it would
either compile-time-evaluate the expression or halt compilation with an
error. I believe there isn’t anything currently that does this for
arbitrary types, only integers.

For what it’s worth, if you want something which folds expressions, I think you can already build that (horrifically):

// Outside C++11, where everything we can fold has a ‘!’
struct assert_foldable_t { int arr[1]; };

#define fold(expr) (__builtin_constant_p(1) ? (expr) : (expr))
#define ignore(expr) ((int)!(expr))
#define assert_foldable(expr) ((void)(struct assert_foldable_t){.arr[ignore(fold(expr))] = 1})
#define builtin_fold(expr) (assert_foldable(expr), fold(expr))

// In C++11, same as above, except:
template constexpr int ignore(T&&) { return 0; }

What I envisage is something like…

auto x = __builtin_fold()

which returns a constant value of appropriate type for the expression.

I’d envisage it as a replacement for an already-possible two-step approach
as follows:

struct __fold_impl_1
{
static constexpr auto value = ;
};


auto x = __fold_impl_1::value;

As noted above, this evaluates the expression as a constant expression, which isn’t the same as folding it.

The obvious down-side of the two-step approach is requiring a special macro
for generating __fold_impl_xxx for each folded expression, plus the
inconvenience and possible scope problems of having to use such a macro!

If you just wanted C++11 constant expression semantics, you could use something like this:

#define builtin_fold(expr)
([]{
struct S {
constexpr decltype(expr) get() const {
return (expr);
}
} s;
constexpr auto val = s.get(); (void)val;
return s;
}().get())

I’d also like it to work in non-C++11 code.

Then you will need to either fold rather than evaluate as a constant expression, or implement the full constant expression rules for non-C++11 languages (which would be a great thing to have – see llvm.org/PR4402).

I could imagine that it should be very possible to get clang to generate
such a struct on-the-fly which avoided the scope problems and substitute the
expression for a reference to the value.

The questions I have are:

  • how does one go about getting clang to build such substitutiary code in
    this way?

This is the wrong approach :slight_smile:

  • is this the best approach, or is there a better/simpler way?

If you want to add a new builtin for this, you should search through the codebase to find the places where builtins are currently handled, and add the relevant support for your builtin there. In particular, you will need to add a new builtin to include/clang/Basic/Builtins.def, add some code to Sema to check that the argument can be folded, and add some code to AST/ExprConstant.cpp to fold the argument. You shouldn’t need to change CodeGen, since ExprConstant should be able to fold all occurrences of this builtin.

However, I think a better feature (and one which I would definitely support pushing into trunk clang) would be an attribute which can be applied to declarations (maybe [[clang::const_init]]), which requires the declaration to be initialized by a constant expression. This isn’t equivalent to any kind of __builtin_fold, since it would work in cases where there is no expression to wrap in __builtin_fold (such as “T x(1, 2, 3);” or “T x = { 1, 2, 3 };”), and would allow constant initialization to be required for objects with constexpr constructors but non-trivial destructors.

– Richard

Hello Andy,

Maybe I'm missing something, but constexpr does exactly that

It does and it doesn't. If you declare a variable 'constexpr' then you can expect that a compile-time-evaluated constant is assigned to it. However, a 'constexpr'-declared variable is forever immutable (which may not be what you want) and if you do not declare a variable 'constexpr' then you cannot assume it will be given an initial value which is compile-time-evaluated.

So far, so good. Although I don't see why the immutability should be a problem; after all, you
can simply say:

constexpr int firstValue = ...;
int i = firstValue;
...
constexpr int secondValue = ...;
i = secondValue;

In this way, 'constexpr' can be considered merely a hint to the compiler, like 'inline' is: the compiler can choose whether to obey it or not, usually depending on the optimisation level.

I don't think that's correct. When using constexpr on a variable, this means that the variable's value
must be a compile-time constant, or the code does not compile:

static int foo()
{
  return 42;
}

static void bar()
{
  constexpr int i = foo();
}

This results in (clang TOT):

error: constexpr variable 'i' must be initialized by a constant expression
   constexpr int i = foo();
                 ^ ~~~~~

Changing this to:

static constexpr int foo() // <=== now is constexpr
{
  return 42;
}

static void bar()
{
  constexpr int i = foo();
}

This compiles perfectly with clang TOTO.

Otherwise it would not be possible to use a constexpr variable as a non-type template parameter:

template <int>
struct Baz {};

static void bar()
{
  constexpr int i = 42;
  
  Baz<i> baz;
}

This compiles, but only because <i> is a constant expression, and constant expressions must be known
at compile-time.

Using __builtin_constant_p(...), it is possible to test whether an expression can be compile-time evaluated, the next logical step would be a builtin which returns the result of the evaluation itself. It would form a contract between user and compiler: the user would be sure that as long as his code compiles, his expression is evaluated by the compiler and never at runtime.

That's what using constexpr on a variable does :slight_smile:

(<www2.research.att.com/~bs/sac10-constexpr.pdf> explains about the rationale behind constexpr)

HTH,
Jonathan

Hi Jonathan,

Hello Andy,

Maybe I'm missing something, but constexpr does exactly that

It does and it doesn't. If you declare a variable 'constexpr'
then you can expect that a compile-time-evaluated constant is
assigned to it. However, a 'constexpr'-declared variable is
forever immutable [...]

So far, so good. Although I don't see why the immutability should
be a problem; after all, you can simply say:

constexpr int firstValue = ...;
int i = firstValue;
...
constexpr int secondValue = ...;
i = secondValue;

[...] When using constexpr on a variable, this means that the
variable's value must be a compile-time constant [...]

Yes, you are right: this is a work-around and certainly works. However, I wouldn't call it a clean solution, I'm afraid. In effect, it requires that every time we want to ensure something is compile-time folded (I'm trying to use the terms as Richard Smith in his post [1] defines them), we have to remember to explicitly declare a constexpr variable to hold the value and then assign the "working" variable to this value.

Let's extend the field of the problem a bit. Let's say, for arguments sake, we have a constexpr function which takes a string and calculates an arbitrary CRC value from it. Such a function may have a signature similar to:

    template <long Polynomial>
    constexpr auto calc_CRC(const char* string)
        -> poly_to_width<Polynomial>::type;

The function here takes the CRC polynomial as a template parameter, calculates the appropriate CRC from the provided string and returns the value in a suitably-sized integer (calculated by a helper struct named poly_to_width).

Since the polynomial can change, then a pre-calculated lookup table approach is not practical: instead the algorithm must use a bit-based approach. This is much, much less efficient than the lookup table method and wouldn't want to be used at runtime. However, there is nothing in the C++11 standard, that I know of, that stops someone using this algorithm in a non-constexpr way. As the library writer, I can say to my users, you must use this function this way:

constexpr int temp_value = calc_CRC<32>("string");
int value = temp_value;

but I can't stop them from simply doing:

char* string = ...
int value = calc_CRC<32>(string);

This is what I meant in my previous post regarding 'constexpr' being little more than a hint to the compiler like 'inline'. With constexpr you get the additional benefit of being able to use that function at compile-time (as long as you can rework your algorithm in a way that complies with the restrictions of a constexpr function) but you don't have a way of limiting its use solely to compile-time. Note that even the following is a runtime evaluation when compiled with clang without optimisations switched on:

int value = calc_CRC<32>("string");

Now at this point, we can start doing some tricks. We can hide the implementation behind a macro:

template <typename T, T V> struct Constant { static constexpr T value = V; };
#define calc_CRC(N,S) Constant<poly_to_width<N>::type, calc_CRC_impl<N>(S)>::value

Now the following use:

char* string = ...
int value = calc_CRC(32, string);

will result in a compiler error since string is not a constant expression.

In this case, our work-around works. However, it works because calc_CRC returns an integer type. If we had a constexpr function which returned a floating point value, or one wrapped in a struct, this work-around would fail. What I wish to create is the generic solution which works for all return types, such that the macro becomes:

#define my_func(...) __builtin_fold(my_func_impl(...))

In Richard Smith's post [1] is a really intriguing macro solution involving folding via __builtin_constant_p and ?: which I believe is a gcc extension(?), but I need to think this through thoroughly and test it.

Regards,
Andy

[1] http://lists.cs.uiuc.edu/pipermail/cfe-dev/2012-May/021549.html

OK. The first thing you need to be aware of is that ‘folded
to a constant’ is not the same as ‘evaluated as a constant
expression’. The former case just means “take an expression,
and use any tricks we know to reduce it to a compile-time
constant”. The latter means following the relevant language
standards, which is a nebulous affair […]

Firstly, thank you for such a detailed reply. I have read it through now several times to be sure I understand everything!

From what you say, just to be sure I do understand, the range of expressions that can be “folded” is a super-set of those “evaluated to a constant expression” in C++11 terms, which is in turn a super-set of those which are “integer constant expressions” of C++98 / C.

So, what I am looking for is the first thing, i.e. to use “any tricks we know” to reduce an expression to a compile-time constant, which should mean, as an example, any calls to functions should be eliminated. If they cannot be, then by extension the expression cannot be folded, and the compiler should at this point stop with an error message to that effect.

As I mentioned in my post to Jonathan Sauer (http://lists.cs.uiuc.edu/pipermail/cfe-dev/2012-May/021554.html), one such use case for this is to limit the possibility of using what may be necessarily-inefficient compile-time algorithms accidentally in a run-time environment.

Additionally, the set of things we can fold is slightly
different in the different languages. Anyway, the point is,
outside of C++11, we don’t really have an implemented,
checkable notion of ‘constant expression’ other than
‘integer constant expression’.

Doesn’t Expr::EvaluateAsRValue(…) fill this criteria?

For what it’s worth, if you want something which folds
expressions, I think you can already build that […]

Unfortunately, I couldn’t get your suggestion to work in my tests. Here’s some sample code:

struct assert_foldable_t { int arr[1]; };
#define fold(X) (__builtin_constant_p(1)?(X):(X))
#define ignore(X) ((int)!(X))
#define assert_foldable(X) ((void)(struct assert_foldable_t){.arr[ignore(fold(X))]=1})
#define builtin_fold(X) (assert_foldable(X),fold(X))

constexpr double X() {
return 5.0;
}

int main() {
double i = builtin_fold(12.0 / X());
printf("%f\n", i);
return 0;
}

It does at least stop compilation if the expression is not foldable, but it doesn’t produce code as though I had written “double i = 2.4” which is what my aim is (I checked the output using -S -emit-llvm).

I also liked your solution using lambdas (I’d actually considered a similar solution before), although as you say, it won’t work outside a C++11 environment. Also, you can’t use it to assign to a constexpr variable so it can’t be used as a generic solution, although this is in this case a minor thing.

If you want to add a new builtin for this, you should
search through the codebase to find the places where
builtins are currently handled, and add the relevant
support for your builtin there. […]

Thank you for the pointers; I will have a nose around and see what I can do! The way I have been approaching it so far is to use Parser::ParseAssignmentExpression then Expr::EvaluateAsRValue which returns an APValue which is the constant I’m looking for. If any of these steps fail, I can generate some diagnostics and stop. Next, my understanding and maybe you can confirm whether I’m right, is that I need to then turn my APValue into an Expr object. There doesn’t seem to be a direct function available for doing this, but I could use IntegerLiteral or FloatingLiteral for these types, and extract Expr directly from APValue if it is an LValue type. Other APValue types may be more difficult, but its a starting point. Is this the best route to take, do you think?

However, I think a better feature (and one which I would
definitely support pushing into trunk clang) would be an
attribute which can be applied to declarations (maybe
[[clang::const_init]]) […]

I agree that I can certainly see an advantage to this feature. I’ll have a look into this too.

Thanks again,

Andy