5

The C++ standard mandates compilers to check for undefined behavior in C++ constexpr computations.

In this talk, Chandler Carruth states that "you will run out of the ability to detect errors" when checking for UB, and that in the general case, detecting UB is related to the halting problem, so provably impossible to decide.

He is not talking about UB in constexpr, but constexpr computations are as general as a regular programs since C++14, so this still applies.

So what do compilers do when they cannot decide if a program is UB or not? Do they still accept the program and go on compiling with fingers crossed? Or are they more conservative and reject the program, even if it is potentially correct? (My personnal feeling is they do that)

For me, this is of practical importance since I have a constexpr evaluation with non-trivial pointer arithmetics compiling fine with Clang but failing with GCC, and I am pretty sure this not UB. You can say it is a GCC bug, but if UB is undecidable, all compilers are and will be buggy in this regard.

More fundamentally, why is UB-free requested by the standard? Is there a technical reason? Or more a philosophical one ("if the compiler can't check, the programmer can trigger UB, and bad things will result")?

I think this is inconsistent with the rest of C++ that never prevents you from shooting yourself in the foot. I would prefer GCC to accept my constexpr code and crash, or emit trash if UB; rather than not compiling when it does not know if it is UB.

====== EDIT ======

As pointed out by M.M and Nicol Bolas, the standard specifies limitations (even in C++14) so that we are never in a halting problem type of UB. However, I am still wondering if checking for UB is maybe too complex and if compiler heuristics fail, then they flag it (potentially incorrectly) as non-constexpr.

But I have the feeling from the comments that this is more a problem of non-mature implementations.

Bérenger
  • 2,678
  • 2
  • 21
  • 42
  • 1
    (Bugs aside) Compilers might have different numbers limits (as for template recursion instantiation) for constexpr functions which might explain difference between those compilers – Jarod42 Oct 30 '19 at 23:55
  • @Jarod42 Yes but generally they say something like "step limit reached". Here, GCC just says "its not constexpr" (more precisely ""the value of ‘’ is not usable in a constant expression"") – Bérenger Oct 31 '19 at 00:00
  • 3
    There are limtations on what expressions are allowed in constexpr contexts and those rules by nature exclude all of the "difficult to detect" UB scenarios such as halting problems – M.M Oct 31 '19 at 00:00
  • @M.M Ok so assuming Clang is correct, it means GCC has a bug in the sense that it flags UB something that is provably not ? – Bérenger Oct 31 '19 at 00:05
  • You may find this blog post of relevance [What Every C Programmer Should Know About Undefined Behavior](http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html). – Eljay Oct 31 '19 at 00:11
  • @Bérenger I don't understand your last comment , is there a code sample where you think gcc has a bug? – M.M Oct 31 '19 at 00:15
  • 3
    @M.M Yes. Clang and GCC disagree, so either Clang accepts a constexpr it should not, or GCC does not accept a constexpr it should. But I can't extract the code easily (I will post a specific question if I can) – Bérenger Oct 31 '19 at 00:22
  • @Bérenger: If expansion of a 200-deep function call would allow a value to be recognized as a constant, would a compiler not be allowed to at its leisure either treat the value as a constant, or treat the expression as something that could be computed at runtime? – supercat Oct 31 '19 at 21:02
  • @supercat I am not sure I understand what you mean. If the function is constexpr and called in a constexpr context, then the standard requires the compiler to find the value no matter what – Bérenger Oct 31 '19 at 22:28
  • Or issue an error if it encounters UB (or incorrect syntax and the like) – Bérenger Oct 31 '19 at 22:29
  • @Bérenger: If a compiler doesn't have as much memory available to it as might be available at run-time, an expression that would require more memory to evaluate than the compiler has available would be a valid expression that could be evaluated in any context not requiring compile-time evaluation. The only sense in which the expression would be invalid is that it wouldn't be a constant. – supercat Nov 01 '19 at 13:01

2 Answers2

3

The point you are missing is that constant expressions only allow for a restricted subset of the language.

If you go outside that, you no longer have a constant expression, and if you are in a context needing one the standard mandates diagnosing the error.

A constexpr-function only has to have at least one input where it is a constant expression, no diagnostic required. All the rest might not be.

In the general case, compilers just note paths leading to UB to prune presumably dead code, and explore the freedom they have in optimizing what remains. They are not required to find all, most, or even any of those opportunities though.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
3

In this talk, Chandler Carruth states that "you will run out of the ability to detect errors" when checking for UB, and that in the general case, detecting UB is related to the halting problem, so provably impossible to decide.

The Halting Problem is when you take a program and try to decide whether the program, if it were to execute, would definitely halt. By definition, the Halting Problem only looks at the program as a locked-off object.

Constant evaluation is... evaluation. You are executing the program, not merely looking at the source code.

Undefined behavior happens when your program's execution does something undefined. Most cases of UB cannot be determined to be well-defined or not just from inspecting the source code. Consider this code:

void foo(void *ptr)
{
  *reinterpret_cast<int*>(ptr) = 20;
}

Is that UB or not? It depends; if a pointer to an int were passed into foo, it would be well-defined. Whether this code is well-defined or not can only be determined by how it is executed.

Constant evaluation requires executing code; that's why we often refer to it as compile-time execution. When you're executing code, it is possible to know if a particular execution of foo has been passed a pointer to an actual int (ignore the fact that reinterpret_cast is forbidden in constexpr code). As such, at evaluation time, you can know whether UB is happening.

So what do compilers do when they cannot decide if a program is UB or not?

That's not actually a thing that can happen. Assuming the specification is complete and without holes, whether an execution of a program exhibits well-defined behavior or not is merely a matter of following the specification.

The problem you're having with GCC vs. Clang is not due to whether UB can be determined or not.

More fundamentally, why is UB-free requested by the standard? Is there a technical reason?

Hypothetically, we could rip all undefined behavior out of C++ or even C. We could have everything be a priori well-defined and remove anything from the language whose evaluation could not be definitely determinable from first principles.

The standard doesn't do that because it would be bad. It would prevent us from doing all kinds of useful, low-level things. It would prevent useful compiler optimizations. And so forth.

None of those reasons apply to compile-time code execution. Especially that whole "useful, low-level things" part. For compiled code, there is an actual real machine that the generated code executes on. So having a back door to talk to the real machine makes sense. At compile-time however, there is no real machine to talk to; there is only the C++-defined abstract machine. So what's the point of allowing UB?

The compiler doesn't generate machine language and execute it; constant evaluation is basically executing a scripting language within the compiler. And like most scripting languages, you want it to evaluate safely and correctly. You want errors (and UB is an error) to be caught quickly and provide a clean error message at the point of failure, rather than dying arbitrarily later in the process.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • Ok but then even if you can determine it. Isn't there some cases where you have a lot of pointer running around, and it is just too expansive to check whether they are all refering to something valid? Plus you have to ensure that pointer substraction is done from pointers of the same array and so on... – Bérenger Oct 31 '19 at 00:18
  • @Bérenger: It's *compile time*. Performance of execution is not the most important thing going on. It should also be noted that debugging code at compile time is exceedingly difficult. Better to stop those bugs from happening to begin with. – Nicol Bolas Oct 31 '19 at 00:18
  • Do we have an idea of the complexity of running the "UB-checker"? Because if it is exponential, it does'nt matter that this is decidable in theory – Bérenger Oct 31 '19 at 00:19
  • I mean at the end, the compilation time should still be reasonnable – Bérenger Oct 31 '19 at 00:20
  • @Bérenger: What makes you think it is a "UB-checker"? The compiler can implement constant evaluation however it wants. That "pointer" you're passing around doesn't have to have any relationship to what the computer uses. – Nicol Bolas Oct 31 '19 at 00:20
  • I mean, let's say I dereference a pointer. Then the compiler (interpreter part of it I should say) could just dereference it and take the value, whatever it is. But it also checks that it has the right to do that (what I call UB checker) – Bérenger Oct 31 '19 at 00:25
  • Or do I misunderstand something? – Bérenger Oct 31 '19 at 00:25
  • @Bérenger: Again, you assume that the implementation is such that the ability to dereference a pointer is decoupled from the ability to know whether you have the right to. – Nicol Bolas Oct 31 '19 at 00:34
  • I don't really understand. Even if it is done all at once, I would be very surprised if you don't need additionnal logic (and storage) in order to check this kind of things – Bérenger Oct 31 '19 at 00:38
  • @Bérenger: You're asking the question backwards. The question, as I stated in an update to my answer, really is about why C++ doesn't simply eliminate UB generally. Once you understand why UB exists, then it becomes apparent that most of those reasons just don't apply to compile-time code. And the only reason that might still apply (performance) isn't nearly as important at compile time because... it's *compile time*. – Nicol Bolas Oct 31 '19 at 01:10