Programming

Why a ‘constexpr’ is just a return statement

A question recently asked why a ‘constexpr’ function in C++ may comprise only a return statement. It’s a good question. On quick glance the restriction seems somewhat arbitrary, and indeed quite limiting. I think the answer comes not from the desires of the users (us programmers) but from the implications on compiler vendors. In particular, how does it simplify the job of a compiler?

The original question is here.

What is constexpr

Just a quick background: ‘constexpr’ is a new keyword in the C++11 standard. It allows simple expressions to be used as part of constant expressions, where previously only a simple literal constant could be used (ex: hard-coded integer or string literal). One of these key locations is static member variable initialization. Allowing expressions can both improve code readability, and allow more variables to be ‘const’. In practice a ‘constexpr’ will be evaluated at compile time possibly resulting in more efficient code.

Compilers are not abstract machines

It may not be obvious that a compiler is not an abstract machine. While a compiler may be able to produce executable code, there is no general need for it to know how to execute code on its own. The role of the compiler is to translate your code into a lower form which can then be executed by an abstract machine. The high-level transformations can be quite oblivious to what your code is actually doing.

If we look at the optimizer however we see something similar to what we want. In order to produce efficient runtime code it is often necessary to evaluate the code. Some common optimizations are const-folding and inlining. An optimizer will trace through expressions involving constants and replace them with the resulting value. Beyond just saving some calculation time, it allows the optimizer to do things like remove constant branches, perform loop unrolling, and further inline code.

Since the optimizer can do constant exression evaluation, ‘constexpr’ must be easy to implement, right? Unfortunately the answer isn’t yes. Likely a compiler vendor cannot use any of their optimization code to do the ‘constexpr’ evaluation. The problem is that optimizations tend to be done at a much lower level. Usually a compiler has a front-end which processes the high-level language like C++ into a lower level form, often called IR (intermediate representation). Optimizations are often performed on this form (both clang and gcc work this way).

A ‘constexpr’ however needs to be evaluated at a higher level, directly in the C++ front-end. All constants, including things like default parameters, are already resolved prior to the generation of IR. ‘constexpr’ is essentially asking the compiler to implement an abstract machine at a very high level.

But not a full machine

That is the source of the restrictions on ‘constexpr’. It would be a lot of work to need an abstract machine at the highest level of the compiler. Not even the low-level optimizer does the full work required of an abstract machine. Sure, some languages actually run in virtual machines, but even there that machine is still quite separated from the source language itself (for example with Java).

Allowing any type of evaluation to be done in a ‘constexpr’ would likely have been resisted and not added to the standard. Even if it were added it would likely be years before it could be implemented. To simplify the implementation, and likely remove resistance, the ‘constexpr’ requirements are extremely strict. The key limitation is that a function can only return a value, and more obviously only call other ‘constexpr’ functions with constant parameters.

This makes evaluation rather easy. If you’ve ever done the calculator example with a parser you’ve done this type of work. Evaluating the expression is primarily a matter of reducing a parse tree. Let’s consider the following code.

constexpr int neg( int a ) {
	return -a;
}

constexpr int sub( int a, int b ) {
	return a + neg(b);
}

struct holder {
	static const int value = sub(2*sizeof(int),5);
};

The static member ‘value’ needs to be evaluated at compile-time. If all the parameters are replaced with their input values the following full tree of the evaluation results.

constexprYou should notice the leaves are all simple constant values. This allows us to collapse any branch since the value will be known at compile time. Indeed, since a constant branch also evaluates to a constant this entire tree reduces to the value ’11’. As long as an expression can be represented by such a tree it can be evaluated with a simple recursive algorithm.

An implementation

Be aware however that a compiler will not likely produce that expanded tree. The parameters to a function are generally evaluated prior to the evaluation of the function call (as opposed to substituted as I have done). The order of operations the compiler may roughly be:

  1. p1 = eval( 2*sizeof(int) )
  2. p2 = eval( 5 )
  3. return call( sub, p1, p2 )
  4. — p3 = call( neg, p2 )
  5. — — return eval( -p2 )
  6. — return eval( p1 + p3 )

The functions ‘eval’ and ‘call’ could be real functions in the compiler. As an example, I might write the functions with the below signatures. Here ‘const_value’ is an object which holds a constant value and ‘syntax_tree’ holds the parsed source code.

const_value eval( syntax_tree expr, map<const_value> variables );
const_value call( string func, map<const_value> params );

I should note that ‘call’ would likely be a fairly limited function. It would lookup the ‘syntax_tree’ for the provided function name then pass this on to the ‘eval’ function.

This brings us back to the limitations on ‘constexpr’. A compiler must already have types like ‘const_value’ and ‘syntax_tree’, otherwise it wouldn’t have been able to compile previous C++ code. With that already covered the ‘eval’ function is a rather modest addition rather than a fundamental change.

Curiously the ‘eval’ function might also exist. Prior to C++11, template parameters were already allowed to be integral expressions, and they had to resolved at compile-time. This new ‘eval’ function for ‘constexpr’ may just be an extension of that mechanism to allow more types. Given the close relationship between these features it’s surprising that the restrictions on templates weren’t lifted.

Conclusion

Does this answer our question of “Why a ‘constexpr’ is just a return statement?” It might, assuming the reason was primarily to reduce the effort required of compiler vendors. It does so by avoiding the need for a full abstract machine and instead builds upon concepts a compiler must already handle.

Categories: Programming

Tagged as: , ,

5 replies »

  1. Note that proposal N3597 argues for relaxing the constraints on constexpr functions for C++14: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3597.html

    “Proposed solution

    Promote constexpr to a largely unrestricted compile-time function evaluation mechanism. There is implementation experience of such a mechanism in the D programming language, where it is a popular feature (see the documentation for this feature). The programmer’s model would become simple: constexpr allows their code to run during compilation.”

    • I definitely agree this would be a good thing. I also think that already having the current ‘constexpr’ model makes the next step a lot easier to accept. The restriction on side-effects is still pretty severe, but it also makes it a lot easier to implement.

  2. “Given the close relationship between these features it’s surprising that the restrictions on templates weren’t lifted.”

    — I remember I asked a similar question a while back:
    https://groups.google.com/d/msg/comp.std.c++/YeJMtxTg1Jc/qA_UshFp5jEJ

    The answer, in short, was: for integral types, we know how to encode them when rendering concrete types from templates for the purposes of linking, and ABI in general. It is not clear how one could encode an arbitrary user-defined type and value. It is probably doable, but noone wants to impose this additional burden on compiler vendors unless there is good motivation for having such generalized templates.

    • That seems like kind of an unfortunate reason. For Leaf I actually have the same issue: I need to encode function names or arbitrary length/form. I’ll likely have to do a hash-like encoding of the names to produce the ABI symbols. C++ could do the same thing, but I guess that’d be a controversial change, and likely ABI incompatible between versions.

  3. Your opening sentence confused me because you dropped one word and changed another. You dropped the worst ‘function’ and you changed ‘must’ to ‘may’, which makes the question confusing. How about:

    “why a ‘constexpr’ *function* in C++ *must* comprise only a return statement”

    Otherwise it’s a good article and explains the topic well.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s