[LLVM-backend] Zig should set noundef attributes on arguments

[Validark]

Zig Version

0.12.0-dev.2076+8fd15c6ca

Steps to Reproduce and Observed Behavior

Godbolt Link

export fn foo(a: u32, b: u32) bool {
    return a < 2 and b < 2;
}

The above is not getting optimized. The obvious optimization here is to transform this into return (a | b) < 2, but that will not happen because, according to the fine folks at llvm/llvm-project#77432, Zig is not properly setting the noundef attribute on the function arguments, therefore and can not be turned into a bitwise AND, i.e. &.

Expected Behavior

It should be as optimized as this code is: (Godbolt link)

export fn foo(a: u32, b: u32) bool {
    return 1 == (@intFromBool(a < 2) & @intFromBool(b < 2));
}

[nektro]

with that attribute does passing undefined as a function argument become UB?

[xdBronch]

shouldnt passing undefined already be considered UB? it really shouldnt be used like that unless you know the argument is unused

[nektro]

yeah I suppose it would. guess I'm wary of what other kind of optimizations it would cause llvm to enable and if we have enough safety checking to warn against it

[N00byEdge]

Passing undefined as a function argument should not be UB, consider for example

syscall6(SYS_EXIT, 0, undefined, undefined, undefined, undefined, undefined)

here the values will even be used and passed to inline assembly, they will just have undefined values

noundef from LLVM docs:

This attribute applies to parameters and return values. If the value representation contains any
undefined or poison bits, the behavior is undefined. Note that this does not refer to padding introduced
by the type’s storage representation.

I don't see how that would be relevant for this, why can't you do this optimization without that?

[xdBronch]

but those parameters are effectively unused right? they're passed to inline asm but only as pseudo values to fullfil the interface of the syscall function. there's no branching on the values for example? I don't mean UB in the sense that the compiler will emit broken code, more that you're willingly using values that may lead to unpredictable behavior. I'm assuming that's more in line with what nektro meant as well

and I'm a little confused on that llvm definition, I'm not familiar with what it means by poison bits or if undefined in that context is the same as zigs undefined but like I was saying before, should that not always be assumed to be the case?

[N00byEdge]

Yes those values are used but ignored, but the LLVM docs don't mention usage, only the values. If the value representation contains any undefined or poison bits, the behavior is undefined, that sounds to me like it would cause UB.

[N00byEdge]

Ugh, there's something more fucky going on here, and I don't get it.
v < 2 can be translated to (v & 0xfffffffe) == 0.
(a & 0xfffffffe) == 0 and (b & 0xfffffffe) == 0 should always be equivalent to ((a|b) & 0xfffffffe) == 0.
This also shows the same issue with zig vs clang (https://gcc.godbolt.org/z/8hbhq3vKT), and I'm not sure why. I don't see how undefined bits affect this at all. Is this related to how zig emits IR for the short circuiting on and?

[N00byEdge]

would you look at that, it does make the optimziation happen though:

# opt -O3 | llc
define dso_local zeroext i1 @foo(i32 %0, i32 %1) local_unnamed_addr {
Entry:
  %2 = icmp ult i32 %0, 2
  %3 = icmp ult i32 %1, 2
  %4 = select i1 %2, i1 %3, i1 false
  ret i1 %4
}

define dso_local zeroext i1 @bar(i32 noundef %0, i32 noundef %1) local_unnamed_addr {
Entry:
  %2 = icmp ult i32 %0, 2
  %3 = icmp ult i32 %1, 2
  %4 = select i1 %2, i1 %3, i1 false
  ret i1 %4
}
        .text
        .file   "<stdin>"
        .globl  foo                             # -- Begin function foo
        .p2align        4, 0x90
        .type   foo,@function
foo:                                    # @foo
# %bb.0:                                # %Entry
        cmpl    $2, %edi
        setb    %cl
        cmpl    $2, %esi
        setb    %al
        andb    %cl, %al
        retq
.Lfunc_end0:
        .size   foo, .Lfunc_end0-foo
                                        # -- End function
        .globl  bar                             # -- Begin function bar
        .p2align        4, 0x90
        .type   bar,@function
bar:                                    # @bar
# %bb.0:                                # %Entry
        orl     %esi, %edi
        cmpl    $2, %edi
        setb    %al
        retq
.Lfunc_end1:
        .size   bar, .Lfunc_end1-bar
                                        # -- End function
        .section        ".note.GNU-stack","",@progbits

[Plecra]

Ah here's why: https://llvm.org/docs/LangRef.html#i-select

select is a special case: the current version of the function would return true with foo(1, undefined) because select is well-defined even when the unchosen value is undefined. However the optimized one would ofc return undef after the or combined them.

With that cause, I expect another solution would be to implement and with bitwise ops instead of select. I don't know if that's preferable :D (edit: I would've expected true and undefined to be undefined before today so this might be acceptable) Absolutely terrible idea :D We still need and to be short circuiting. That said, freeze might work if the rewrites are implemented in llvm. afaict, select (freeze a), (freeze a), (freeze b): u1 = (freeze a) | (freeze b)

[N00byEdge]

That makes no sense. Why would select be defined for undefined values? Also, does this make it UB or just undefined result to pass undefined in?

[Plecra]

(By my understanding,) It's currently well-defined to call foo(1, undefined) and expect 1 to be returned, which is preventing LLVM from making the optimization called for by the original question. foo(undefined, *) is also defined to return an undefined value.

Edit: I got the truth values the wrong way around: foo(3, undefined) is well defined to return false. foo(1, undefined) will naturally select undefined < 2 = undefined

Edit2: Here's more details on the optimization from llvm's end https://aqjune.github.io/posts/2021-10-4.the-select-story.html

[N00byEdge]

Select talks about semantics based on poison bits, not undefined bits. noundef forbids both. Does zig emit anything that can have poison bits?

[Plecra]

https://github.com/llvm/llvm-project/blob/21830c913505b1fd2cf10e454253483180c7e10b/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp#L4448-L4451

Here's select's behaviour: "[a = select b, c, d ==>] Sa = select Sb, [ (c^d) | Sc | Sd ], [ b ? Sc : Sd ]" undef and poison are treated equally, PoisonValues subclass UndefValues.

As a quick explanation of that syntax, Sx is the "shadow" of x and contains a bitmask representing which bits of x are undefined. a = b + c generates Sa = Sb | Sc as seen here.

This was the best source I could find for this info: docs are sparse on undef, and most email threads are debating the semantics XD MemorySanitizer at least represents the current intentions of the llvm sources

[Plecra]

It seems the optimization might be valid anyway in this specific case (pointed out by @mlugg on discord). Clang doesn't need it because of their noundef annotations which would explain the absence from LLVM right now.

We might add it as an optimization for zig's sake if it does turn out to be correct. Here's an informal analysis for someone smarter than me to refine😆

Proposition:
  select x, y, x = o < 2^n
  where
    o = a | b
    x = a < 2^n
    y = b < 2^n

There're 9 cases for each permutation of x and y, and the result value of the instruction is written r here. After the rewrite it is r'

value	#1	#2	#3	#4	#5	#6	#7	#8	#9
a	<2^n	<2^n	<2^n	>=2^n	>=2^n	>=2^n	undef	undef	undef
b	<2^n	>=2^n	undef	<2^n	>=2^n	undef	<2^n	>=2^n	undef
x	1	1	1	0	0	0	undef	undef	undef
y	1	0	undef	1	0	undef	1	0	undef
r	1	0	undef	0	0	0	undef	undef	undef
o	<2^n	>=2^n	_	>=2^n	>=2^n	>=2^n	_	>=2^n	_
r'	1	0	undef	0	0	0	undef	0	undef

It would seem that there're no cases where the rewrite would introduce UB. (I am however entirely out of my element ;))

[N00byEdge]

Exactly what I've been saying about the bitwise rewrite. They are exactly equivalent. The undefined bits shouldn't affect this optimization at all. The only thing that could are poison bits.