Exploiting Undefined Behavior in C/C++ Programs: The Performance Impact [pdf]

https://web.ist.utl.pt/nuno.lopes/pubs/ub-pldi25.pdf

by luu • 1 year ago

97 78 1 year ago

web.ist.utl.pt

jonstewart2• 1 year ago

The results show that, in the cases we evaluated, the performance gains from exploiting UB are minimal. Furthermore, in the cases where performance regresses, it can often be recovered by either small to moderate changes to the compiler or by using link-time optimizations.

_THANK YOU._

ryao3• 1 year ago

by using link-time optimizations

These are almost never used by software.

mgaunard2• 1 year ago

Only places where I've seen LTO not be used are places with bad and unreliable build systems that systematically introduce undefined behaviour by violating the ODR.

jandrewrogers• 1 year ago

LTO is heavily used in my experience. If it breaks something that is indicative of other issues that need to be addressed.

steveklabnik3• 1 year ago

It's on by default for Rust release builds, so at least the codepaths in LLVM for it are well-exercised.

Rusky• 1 year ago

It's worth noting (and the paper does go into this) that this is limited to a very specific subset of UB, which they call "guardable."

They are not removing UB around things like out-of-bounds or use-after-free, which would likely be more expensive.

jonstewart2• 1 year ago

I don’t understand the down votes. Conducting empirical research on the performance impact of undefined behavior is fantastically needed, as the C++ committee’s obsession with undefined behavior strictness (in contrast with longstanding semantics, e.g., uninitialized memory accesses being just fine) has been justified largely by how they enable optimizing compilers. This research shows that many types of UB have a negligible impact on performance.

saagarjha2• 1 year ago

You're getting downvoted because you're looking for a particular result ("UB optimizations don't help performance") rather than actually evaluating the quality of this analysis (which doesn't really support what you want anyway).

atq21192• 1 year ago

Possibly somebody downvoted because "thank you" in all caps is not a substantial contribution to discussion. It feels like the kind of low effort stuff you'd see on reddit.

Also, commenting on downvotes is generally frowned upon.

mwkaufma2• 1 year ago

Reading e.g. the 13% perf regression in simdjson from disabling UB:

  A simpler alternative is to compile the program with LTO. We confirmed that LLVM’s inter-procedural analyses can propagate both alignment and dereferenceability information for this function, which allows the LTO build to recover the performance loss.

"can" is doing a lot of heavy-lifting here. Guaranteeing expected optimizations "will" be applied are hard-enough, without leaving it entirely to an easily-derailed indirect side-effect.

UebVar• 1 year ago

This is "can" has exactly the same meaning as in "UB can make your programms faster". You could replace it with "it does, at least with clang". LTO is, in this regard, the same as UB, and unlike guaranteed optimizations, such as the single member optimization, or the empty base optimization.

mwkaufma2• 1 year ago

Concretely, here, the UB-exploitation in question in this case is assuming that the "this" pointer in C++ is aligned and non-null, meaning it's a pervasive annotation throughout C++ codebases, not an edge-case.

Relying on LTO to "discover" this annotation through interprocedural analysis -- based on my experience of looking at LTO in practice -- will not be as comprehensive, and even when it works it accomplishes its task in an achingly-slow and expensive way.

This is a real devil-is-in-the-details case.

quotemstr• 1 year ago

I love when papers disagree with their own abstracts.

gitroom• 1 year ago

perfect, this is right up my alley - honestly i keep wondering if teams avoid optimizations like lto just because build pain sucks or if theres some deeper trust issues around letting the toolchain be clever. you think peopled deal with slow builds if it bought way more speed for the final product?

pcwalton8• 1 year ago

I notice that the paper doesn't claim to eliminate all reasoning about undefined behavior for optimizations. For example:

    int f() {
        int arr[3], i = 0;
        arr[3] = 5;
        return i;
    }

Optimizing this to "return 0" is relying on UB, because it's assuming that i wasn't laid out directly after arr in the stack frame. I believe this is what the paper calls "non-guardable UB".

I don't agree with the claim in the paper that their semantics offers a "flat memory model". A flat memory model would rule out the optimization above. Rather, the memory model still has the notion of object bounds; it's just simplified in some ways.

throwawayqqq11• 1 year ago

Sorry, i dont get why the memory layout should have any effect, when its clear in the AST that i=0 should be returned.

bregma• 1 year ago

It's clear in the AST that there is undefined behaviour and it is malformed code. It is not valid C code, so what the compiler chooses to do with it is not defined by the language.

maartenscholl• 1 year ago

I think in the example the parent gave `arr[3]` is past the end of the 3 element array, where `i` might reside, potentially changing its value.

dooglius3• 1 year ago

it's assuming that i wasn't laid out directly after arr in the stack frame

The compiler isn't "assuming" that so much as choosing not to put i in the stack frame at all. And I don't think it's correct to view the lack of a register spill as an "optimization" per se. It does remain true that code writing past the end of an array will be UB in typical scenarios (i.e. when not using asan/valgrind).

(Now, if the compiler also removed the store, that could legitimately be called an optimization based on assuming no-UB)

pcwalton8• 1 year ago

"Exploiting undefined behavior" occurs when a simple semantics (however one defines "simple") results in behavior A, but the compiler chooses behavior B instead based on the actual, more complex, language semantics. The code snippet in question passes that test. If I flip the declaration order of i and arr, then I get this [1] at -O0 (the "simple" semantics):

        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], 0
        mov     dword ptr [rbp - 4], 5
        mov     eax, dword ptr [rbp - 4]
        pop     rbp
        ret

Which indeed returns 5. But at -O2 clang optimizes it to this:

        xor     eax, eax
        ret

Which returns 0. So the simple semantics produces one result, and the complex semantics produces another. Hence, it's exploiting undefined behavior.

[1] https://godbolt.org/z/df4dhzT5a

artikae• 1 year ago

What about this: https://godbolt.org/z/xP9xG3Ee3

Here the compiler "register allocates" i for some reads but not for others.

i gets stack allocated, but some uses of it act as though they were register allocated.

jcranmer2• 1 year ago

I've only briefly skimmed the paper, but on that glance, it looks like what they did was (effectively) drop all the attributes in LLVM that can indicate UB, e.g., the inbounds flags on getelementptr instructions, or the nsw flags on arithmetic operations.

As you note, it doesn't remove the more core UB behaviors in LLVM, in particular LLVM's reliance on pointer provenance.

nikic2• 1 year ago

They do a bit more than that. One of the options (-disable-object-based-analysis under AA2) disables the assumption that distinct identified objects do not alias, which is disabling pointer provenance in at least one key place.

So I think this option very roughly approximates a kind of "no provenance, but with address non-determinism" model, which still permits optimizations like SROA on non-escaping objects.

nikic2• 1 year ago

One peculiar thing about the benchmark results is that disabling individual UB seems to fairly consistently reduce performance without LTO, but improve it with LTO. I could see how the UB may be less useful with LTO, but it's not obvious to me why reducing UB would actually help LTO. As far as I can tell, the paper does not attempt to explain this effect.

Another interesting thing is that there is clearly synergy between different UB. For the LTO results, disabling each individual UB seems to be either neutral or an improvement, but if you disable all of them at once, then you get a significant regression.

imtringued• 1 year ago

Amazing that the pain of C is unnecessary and offers few benefits.

hyperhello• 1 year ago

C is very much one level above assembly, the way dipping a jug in the river is one level above bending down to drink. It's a whole lot easier to mechanically translate *ptr++ = 0 to the corresponding machine code than to memorize and write those actual instructions. Neither is going to automatically check the security of your memory access through any more than the jug is going to test the water.

pjmlp• 1 year ago

In the good old days of dumb CPUs.

There is a world apart between C code and auto-vectorization into AVX 512.

hnaccountme• 1 year ago

You don't program C. You program your OS using C.

If you look at it this way, does most complaints about undefined behavior go away?

Exploiting Undefined Behavior in C/C++ Programs: The Performance Impact [pdf]

Related Stories