Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
|
|

Optimizers exploiting UB

Optimizers exploiting UB

Posted Jul 15, 2024 14:48 UTC (Mon) by farnz (subscriber, #17727)
In reply to: Optimizers exploiting UB by Wol
Parent article: New features in C++26

That runs into the problem of macro expansion, constexpr functions, inlining and more. while(1) is clearly intended to be an infinite loop, but from a C99 or C11 compiler's point of view, while(true) is the same as while(HOW_BIG_IS_THAT_FISH), since true is not a value, but a macro that expands to the value 1.

And the problem with your description is that the program doesn't know that the "test folded to false", it knows that there's a conditional that's always false - but it can't tell whether it's intentionally always false, or whether that's an accident. Compilers can't read developer minds, yet.

Remember that, for a lot of the key optimizations, it's not working at the level of the source language - it's working with something like LLVM IR, and what it's seeing is a conditional jump where the condition is a constant, but it has no clue that the condition was "meant" to be variable, since the optimizations aren't working at that level. And it could be hundreds of optimization passes in before the condition becomes constant, at which point it's really hard to work out whether it's constant because the compiler has assumed no UB, or whether it's constant because the fully-defined behaviour of the language makes it constant.


to post comments

Optimizers exploiting UB

Posted Jul 15, 2024 15:55 UTC (Mon) by Wol (subscriber, #4433) [Link] (1 responses)

> And the problem with your description is that the program doesn't know that the "test folded to false", it knows that there's a conditional that's always false - but it can't tell whether it's intentionally always false, or whether that's an accident.

And the compiler doesn't track whether a constant expression was constant when first met, or a previous optimisation pass has folded it. And as you say macros screw things up.

I wasn't asking it to read minds - it was as simple as "did the programmer write "while(true)", or "while(a==b)"", but I'm not surprised you're saying even something that simple is hard to track. Because if the latter evaluates to a constant there's a good chance the programmer didn't mean it (but if that code was in a macro, then it might not always evaluate to a constant for the programmer who wrote the macro, but does for the programmer using the macro :-(

Cheers,
Wol

Detecting UB involves reading minds :-(

Posted Jul 15, 2024 17:27 UTC (Mon) by farnz (subscriber, #17727) [Link]

Unfortunately, it becomes impossible for the compiler to even determine what the programmer wrote at the point where it's interesting to know if a condition is constant, especially since defensive programming means that a condition might be known to be constant, even though it's variable at source level. Consider the following C function:


static int fetch_update_package_epoch(epochs *epoch_area) {
    if (epoch_area == NULL) {
         return 0;
    }
    epoch_area->package += 1;
    return epoch_area->package;
}

At source level, this is clearly not attempting to invoke UB, and there's no constant comparisons involved. As a result, by the time the optimizer is relying on assuming no UB, what it will be looking at (after optimizing the function's IR over many passes) is something like:


define dso_local i32 @fetch_update_package_epoch(ptr noundef %epoch_area) local_unnamed_addr {
entry:
  %cmp = icmp eq ptr %epoch_area, null
  br i1 %cmp, label %return, label %if.end

if.end:
  %0 = load i32, ptr %epoch_area, align 4
  %add = add nsw i32 %0, 1
  store i32 %add, ptr %epoch_area, align 4
  br label %return

return:
  %retval.0 = phi i32 [ %add, %if.end ], [ 0, %entry ]
  ret i32 %retval.0
}

This is short enough to inline; when it's inlined, the optimizer will replace a %call = call noundef i32 @fetch_update_package_epoch(epochs*)(ptr noundef nonnull %epochs) with the function body, making the right substitution for epoch_area. Now, because the call tells us that epoch_area is nonnull, the comparison becomes a constant, the branch can be made unconditional, and then dead code elimination removes the NULL check.

But the problem is that what's triggered the comparison becoming a constant is the compiler identifying that epoch_area in the call at IR level is nonnull. The optimizer can't warn you that it's eliding the NULL check based on this, because it cannot distinguish "this is nonnull because otherwise there is UB in the program" from "this is nonnull because the source lines are epoch_area epochs = { package = 1 }; pkg = fetch_update_package_epoch(&epochs);. Both of those are the same IR at this point - a call with a non-NULL annotation on the pointer - how should the optimizer know that one of those annotations is fine to ignore, but the other matters? And note that you also don't want to warn just because a pointer is marked as non-NULL because it'd be UB to be NULL, since that would cause you to warn on:


static int fetch_update_package_epoch(epochs *epoch_area) {
    epoch_area->package += 1;
    return epoch_area->package;
}

But it might be perfectly clear from the rest of the source code context that, in this case, epoch_area will never be NULL, because no function calls this with a possibly-NULL pointer.

Optimizers exploiting UB

Posted Jul 15, 2024 19:35 UTC (Mon) by unilynx (guest, #114305) [Link] (1 responses)

> That runs into the problem of macro expansion, constexpr functions, inlining and more. while(1) is clearly intended to be an infinite loop, but from a C99 or C11 compiler's point of view, while(true) is the same as while(HOW_BIG_IS_THAT_FISH), since true is not a value, but a macro that expands to the value 1.

eslint has a nice fix for this exact situation in JavaScript - you can configure it to require for(;;) to build an endless loop. no constant folding happens so no confusion

https://eslint.org/docs/latest/rules/no-constant-condition

JavaScript not a good source of analogies or fixes, unfortunately.

Posted Jul 15, 2024 19:54 UTC (Mon) by farnz (subscriber, #17727) [Link]

That only works because the output language is still JavaScript, with JavaScript semantics; the issue in this case is that the compiler has read in C (or Rust, or whatever) source code, translated it to an IR like GIMPLE or LLVM IR (with different semantics to the source language) on the basis that the translation only has UB in the IR if the source code had UB, optimized the IR on the assumption of no UB in the IR output, and then ended up with IR that it translates to machine code that has different semantics to the one the programmer intended, because the programmer did not intend to write code with UB.

Note, for example, that C++'s "forward progress" assumption also allows for endless loops, as long as they're "trivial", change state visible to another thread, or they contain I/O. It's only pure computational loops that can be elided if they do not terminate, and only if they're non-trivial in the original source - so for(;;) {} is trivial, and therefore cannot be elided, while for(;;) do_the_thing() is non-trivial, and can be elided if do_the_thing() has no effects visible outside the current thread. This is useful for compilers, since once it's able to show that do_the_thing() is a no-op, it can elide the whole loop - even if do_the_thing is actually a macro containing a break; statement.

There is no real equivalent of this stack of languages in the JavaScript ecosystem, because the "machine code" you execute is also JavaScript.


Copyright © 2024, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds