Signed integer overflow causes program to skip the epilogue and fall into another function

[m13253]

Bugzilla Link	49599
Version	trunk
OS	All
CC	@chandlerc,@DMG862,@dwblaikie,@DougGregor,@emaste,@LebedevRI,@pogo59,@zygoloid,@oToToT

Extended Description

Comment:

Clang 13 simply does not generate any code for f1 after the undefined behavior point. So any call onto f1 will eventually ends up fell into f2.

Although the compiler can do anything with an undefined behavior, including simply crashing, infinite loop, playing some music, or nuke the earth without violating the C++ specification. I still hope this undefined behavior won't be that surprising.

This issue is not observed in C frontend, or Clang 12.

Godbolt link for your convenience: https://godbolt.org/z/r3nWrE

Source code:

#include <stdio.h>

void f1(void) {
    for(int i = 0; i >= 0; i++) {
        // Undefined behavior
    }
}

void f2(void) {
    puts("Formatting /dev/sda1...");
    // system("mkfs -t btrfs -f /dev/sda1");
}

// Prevents inlining
void (*volatile p1)(void) = f1;
void (*volatile p2)(void) = f2;

int main(void) {
    puts(__VERSION__);
    p1();
    return 0;
}

Output:

Clang 13.0.0 (https://github.com/llvm/llvm-project.git fcdf7f6224610a51dc2ff47f2f1e3377329b64a7)
Formatting /dev/sda1...

[LebedevRI]

This is indeed UB, and -fsanitize=undefined will tell you about it:
https://godbolt.org/z/79q6s8
example.cpp:4:29: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior example.cpp:4:29 in

You probably want -fwrapv.

[dwblaikie]

FWIW, I have plans to at least put a ud2/trap at the end of functions that don't otherwise return or at least call (call might be non-returning, so wouldn't want to add an extra instruction if it won't ever be called - but does mean sometimes it could fallthrough to the following function).

But yeah, UB is UB, and this is within the realm of failures you can expect from LLVM's optimizations.

[m13253]

FWIW, I have plans to at least put a ud2/trap at the end of functions that
don't otherwise return or at least call (call might be non-returning, so
wouldn't want to add an extra instruction if it won't ever be called - but
does mean sometimes it could fallthrough to the following function).

But yeah, UB is UB, and this is within the realm of failures you can expect
from LLVM's optimizations.

I would consider ud2 a reasonable solution.
It's free of performance cost, and it saves lives.

I understand the compiler can do anything with a UB.
But triggering a trap is always better than nuking the earth, isn't it?

By the way, GCC warns this UB by default (without -Wall or -Wextra) as long you don't give it -O0.
Is there any technical / performance reason to put this check into -fsanitize=undefined instead of making it default?

Anyhow, a ud2 is good enough.

[DMG862]

-mllvm -trap-unreachable will add a trap.

Some targets (MachO, Webassembly, PS4) will do this by default.

[LebedevRI]

-mllvm -trap-unreachable will add a trap.

Some targets (MachO, Webassembly, PS4) will do this by default.

Hm, that doesn't pessimize the IR at all: https://godbolt.org/z/q49rq6
Only the assembly: https://godbolt.org/z/sceK9T
Why isn't this the default then?

[pogo59]

Why isn't this the default then?

It will increase code size a bit. If you have stack-protector turned on,
there is likely to be a call to the (noreturn) check-fail function at the
end of any function with a nontrivial amount of local storage, and any call
to a noreturn function would need a trap after it. For PS4, we encountered
it because the "return" address of the check-fail call could actually be
the entry point of the next function, and the traceback/unwinder code was
not subtracting 1 from the return address before symbolizing. It was easier
to make the compiler insert the trap than to fix the unwinder.

[m13253]

According to Twitter user @​ScottWolchok, this behavior is not conforming to the standard.

(§5.10/1): "Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address"

However, both f1 and f2 have the same address, yet they are different functions.

[zygoloid]

Yes, irrespective of anything else, giving f1 and f2 the same address is a miscompile. I think that's a somewhat different issue than the one originally filed, as that only covers the case where f1 ends up being empty.

[dwblaikie]

According to Twitter user @​ScottWolchok, this behavior is not conforming
to the standard.

(§5.10/1): "Two pointers of the same type compare equal if and only if they
are both null, both point to the same function, or both represent the same
address"

However, both f1 and f2 have the same address, yet they are different
functions.

Yes, that particular aspect of this is one of the reasons I was interested in the issue when I came across it due to a debug info problem: https://lists.llvm.org/pipermail/llvm-dev/2020-July/thread.html#143722

Though technically we can fix the conformance issue while still having this kind of UB in some fairly accessible cases - LLVM has an attribute "addrsig" to denote which functions have significant addresses - so, constructors for instance (which can't have their address taken/compared) could still have the "run into another function" failure mode.

(& I expect we still have this failure mode in non-empty functions too, FWIW)

My hope was to not go as far as trap-on-unreachable, which can be pretty clearly pessimizing (eg: "void f1() { unreachable; } void f2() { if (x) { f1(); } }" will generate code, test the condition, etc, when the whole condition/block should be optimized away instead) to just the narrow case where we could add one extra byte of instructions and stop a function from falling off the end into another function where there's a good chance of that. (exactly what a "good chance" is is debatable - if it's after a call, do we do it because the call might return? what about if the call is never going to return (it might be attributed with noreturn, or it might just not return for this call site/these particular parameter values))

[dwblaikie]

-mllvm -trap-unreachable will add a trap.

Some targets (MachO, Webassembly, PS4) will do this by default.

Hm, that doesn't pessimize the IR at all: https://godbolt.org/z/q49rq6
Only the assembly: https://godbolt.org/z/sceK9T
Why isn't this the default then?

As you say, it pessimizes the assembly - how much pessimizing is worth the extra safety is unclear. I think there's some room for a bit more safety & I'm working on that - but my guess is we might still leave some cases where you could fall through.

[pogo59]

Two things:

First, when I try this case locally, f1() ends up being a retq instead of
optimized away entirely. Using clang trunk from last night on linux,
and the same options (-O1) as the godbolt link.
That would be recognizing the loop as empty, no uses of the iteration var,
so the entire thing can be optimized away. No UB detected, apparently.
Not sure what the difference is.

Second, IIRC, "trap on unreachable" is an X86 target thing, and not an IR
thing. For PS4 that's all we care about, but if it turns into a more
generic issue then we'll need some other mechanism.

[dwblaikie]

My hope was to not go as far as trap-on-unreachable, which can be pretty
clearly pessimizing (eg: "void f1() { unreachable; } void f2() { if (x) {
f1(); } }" will generate code, test the condition, etc, when the whole
condition/block should be optimized away instead)

Hmm, nope, that was wrong - seems trap-on-unreachable doesn't pessimize the middle end (unreachable blocks can still be removed by SimplifyCFG, etc) - but is only tested in codegen/targets.

Perhaps the MachO behavior (trap on unreachable, but don't trap after a noreturn call) might be worth generalizing. I'll see about measuring the impact of that to see what it'd be like to use it by default. (note that the MachO behavior still leaves the possibility of falling off the end if you violate the noreturn contract and return from such a function)

[dwblaikie]

Second, IIRC, "trap on unreachable" is an X86 target thing, and not an IR
thing. For PS4 that's all we care about, but if it turns into a more
generic issue then we'll need some other mechanism.

Oh, thanks for pointing that out - good to know/think about.

[dwblaikie]

Second, IIRC, "trap on unreachable" is an X86 target thing, and not an IR
thing. For PS4 that's all we care about, but if it turns into a more
generic issue then we'll need some other mechanism.

Oh, thanks for pointing that out - good to know/think about.

Since Apple uses it for MachO I was thinking "oh, what do they do on their other targets" - and it seems they maybe do enable it for ARM and AArch64 (& it's also enabled for WebAssembly). And maybe even the new old M68K backend...

$ grep -ir trap.*unreachable llvm/lib
llvm/lib/CodeGen/SelectionDAG/FastISel.cpp: if (TM.Options.TrapUnreachable)
llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp: if (!DAG.getTarget().Options.TrapUnreachable)
llvm/lib/CodeGen/SelectionDAG/StatepointLowering.cpp: if (DAG.getTarget().Options.TrapUnreachable)
llvm/lib/CodeGen/LLVMTargetMachine.cpp:static cl::opt EnableTrapUnreachable("trap-unreachable",
llvm/lib/CodeGen/LLVMTargetMachine.cpp: cl::desc("Enable generating trap for unreachable"));
llvm/lib/CodeGen/LLVMTargetMachine.cpp: if (EnableTrapUnreachable)
llvm/lib/CodeGen/LLVMTargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/AArch64/AArch64TargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/AArch64/AArch64TargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/ARM/ARMTargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/X86/X86TargetMachine.cpp: // the calling function, and TrapUnreachable is an easy way to get that.
llvm/lib/Target/X86/X86TargetMachine.cpp: // FIXME/Check here - 'trap unreachable' doesn't catch all cases of empty
llvm/lib/Target/X86/X86TargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td:defm UNREACHABLE : NRI<(outs), (ins), [(trap)], "unreachable", 0x00>;
llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td:// terminator, lowering debugtrap to UNREACHABLE can create an invalid
llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td:defm DEBUG_UNREACHABLE : NRI<(outs), (ins), [(debugtrap)], "unreachable", 0x00>;
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp: // Trap lowers to wasm unreachable
llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp: this->Options.TrapUnreachable = true;
llvm/lib/Target/M68k/M68kISelLowering.cpp: if (CLI.DoesNotReturn && !getTargetMachine().Options.TrapUnreachable) {
llvm/lib/Transforms/Utils/Local.cpp: // Don't insert a call to llvm.trap right before the unreachable.
llvm/lib/Transforms/Utils/Local.cpp: // Don't insert a call to llvm.trap right before the unreachable.

[pogo59]

Ah, I was mis-remembering. It's a TM flag and we arranged to set it for PS4.
Looks like each target (that cared) would have to be updated.