# NoUndef attribute breaks hoisting? We have a speculation problem it seems

The more I fathom into interactions of poison and poison-related stuff, the more weird and scary their implications seem to me. Maybe I don’t understand something, if so, someone please help me to get through it.

Here is what LangRef says about `noundef` property of loads:

``````The optional !noundef metadata must reference a single metadata name <empty_node>
corresponding to a node with no entries. The existence of !noundef metadata on the instruction tells
the optimizer that the value loaded is known to be well defined. If the value isn’t well defined, the
behavior is undefined.
``````

``````int a[10];
for (int i = 0; i < N; i++) {
a[i] = 1;
}
for (int i = 1; i < N; i++) {
x = a[0];
a[i] += x;
}
``````

We know that we will only enter 2nd loop if N > 1. Under this condition we are also certain that `a` is initialized, and it doesn’t contain `undef`. It means that `x = a[0]` provably never reads `undef` (actually it always reads `1`). So I can legally mark it as `noundef`:

``````int a[10];
for (int i = 0; i < N; i++) {
a[i] = 1;
}
for (int i = 1; i < N; i++) {
a[i] += x;
}
``````

Now, what’s the point of reading the same value all over in loop? `a` is known dereferenceable. We should be able to safely hoist the load out of the loop:

``````int a[10];
for (int i = 0; i < N; i++) {
a[i] = 1;
}
for (int i = 1; i < N; i++) {
a[i] += x;
}
``````

(Yeah I know that real LICM would hoist to preheader and not into a block before `i < N` check, but let’s give imagination a chance and say that we have found a reason to hoist it right after init. We are discussing legality, not profitability).

Now, if N = 0, everything breaks. The original program entered neither loop, so it didn’t have any UB. The new program, according to specification, has immediate UB on load, because it will provably read an undef value from unitialized array.

Note that if there was no !noundef on load, such hoisting would be absolutely legit. The read value was undef but was never used.

You can say “OK, we should drop metadata !noundef” whenever we hoist a load. Fine, but what if `x` was computed as `x = call foo(arr, 0)` that reads arr[i] and `foo` has `noundef` attribute on return value? We cannot simply go to the module and drop the attribute of another function while performing LICM.

I thought that the intention of `!noundef` was to give optimizer more freedom (e.g. drop freeze instuctions), not to break the optimizations. But in fact, presence of noundef means that speculating such instructions will introduce immediate UB to places where it used to be deferred UB, that could never lead to real UB.

Thoughts?

I vote for cleansing these attributes from loads and functions.

Your understanding of `!noundef` is correct.
It’s true that to hoist a load from a loop you need to drop `!noundef` (in general).

Your concern is regarding hoisting function calls. It’s true that you need to drop the `!noundef` tag from the return value and parameters (or freeze them) on hoisting. Changing the declaration might not be an options and thus you may not be able to hoist a function call.
But it’s very rare that one can hoist a function call anyway. So I disagree that it’s better to drop `!noundef` altogether. If that becomes a concern, we can change the frontend you care about to emit `!noundef` only at the callee (which can be dropped) instead of being at the declarations (for the return value; for arguments it can continue as-is).

Thanks for quick response! Few points here:

It’s true that you need to drop the `!noundef` tag from the return value and parameters (or freeze them) on hoisting

Freeze is not an option. Immediate UB will happen on call return, before the result is frozen.

But it’s very rare that one can hoist a function call anyway.

“Very rare” is a very subjective category. Here are some examples:

``````int abs(int x) { if (x < 0) return -x; else return x; }
int x_plus_1(int x) { return x + 1; }
int noop(int x) { return x; }
``````

All of them can legally be marked as `speculatable`. But if they take undef, they return undef. Adding `noudef` to either of their arguments or return value will immediately make them non-speculatable.

The dumbest example I can come up with is

``````int example(int x) {
int ret = 0;
for (int i = 0; i < N; i++) {
ret += noop(x);
}
return ret;
}

int noop (int x) noundef, speculatable {
return x
}

``````

External precondition:

• N == 0 whenever x is undef
• N > 0 whenever x is not undef

The call of `noop` cannot be hoisted out of loop because if `x` is `undef` and `N = 0`, hoisting is UB.

In our downstream code, we use a lot of functions marked as speculatable, because they are pure math functions with no possible way to get any UB. However, marking them as `noundef` gives them a way to produce UB on call.

Is there any realistic example of function with `noundef` legally set?

I meant the arguments. The result can’t be frozen, agreed.

All C/C++ functions.
When an undef/poison value is created on a C program, it usually means that the program executed UB (in C/C++ semantics). The fact that LLVM gets a undef/poison value is because we decided to delay triggering UB (for example, because we don’t want the `add` instruction to trigger UB on overflow, as then we couldn’t hoist arithmetic instructions). But we can trigger UB later on.
We use function boundaries to trigger UB as it’s already hard to move calls around, thus adding the `!noundef` doesn’t make it much harder.

Note that trivial functions are inlined. If a function is non-trivial maybe we can’t infer `speculatable` either. Right now, `speculatable` is not even inferred in the default optimization pipeline.
I’m happy to look into concrete examples to help assessing the options.

All C/C++ functions.

``````
int main() {
int x;
std::abs(x);
return 0;
}
``````

If `abs` is marked as `noundef`, this is UB in C++, isn’t it? I thought it wasn’t.

That’s also the point I’m trying to make. `noundef` makes things that would normally produce poison (that will never be used later on) produce UB here and now. How is that useful and for what purpose?

LLVM doesn’t only exist for default (clang?) pipeline. We have some Java-related abstraction functions that we marked speculatable because we know they are. And now I’m trying to figure out how does this interact with noundef.

The motivation behind this all is that we have swarming `freeze` instructions in our IR that we want to get rid of. And the natural way of doing so looked marking everything as `noundef`. But with such side effects of this metadata and complexity it brings, I’m not sure if it’s a good idea.

There is an `Instruction::dropUndefImplyingAttrsAndUnknownMetadata()` helper for this purpose. There is nothing really “new” about `noundef` metadata and attributes. We always had metadata and attributes that implied immediate UB. One example is `dereferenceable`.

The only interesting problem I see here is your point about attributes on the function declaration rather than call-site, as this helper will only drop call-site attributes. I believe our stance on this is that it is illegal to mark a function declaration with UB-implying attributes as speculatable. If you want to make it speculatable, then you also need to place attributes like noundef or dereferenceable on the call-sites only.

See ⚙ D104641 Strip undef implying attributes when moving calls, which also discusses this issue.

Wasn’t the purpose of `!noundef` to fight freezes? If it’s as easy to lose it as to move the instruction, we can safely assume they will all be lost very early (especially speculable calls and loads), and freezes will stick with us forever.

Wow, clang does indeed generate UB here: Compiler Explorer

Trying to understand is it legal.

Based on experience with other metadata, I would assume that the answer is “no”. I’ve never encountered dropping load metadata during speculation to be a significant optimization problem myself (and we have plenty of other important load metadata like tbaa, noalias and range, which are subject to the same constraints). I think the only case where I have seen common and significant optimization regressions due to dropped metadata are when loads are eliminated entirely and not just speculated – classical example is range metadata getting completely lost during SROA, and we get bounds check elimination issues due to that. This might be a lesser problem for noundef, because freezes can be fairly reliably propagated to value sources once SROA is done.

Do you happen to have some specific piece of code in mind here? In some cases it’s possible to preserve more metadata than we currently do, e.g. ⚙ D119965 [LICM][PhaseOrder] Don't speculate in LICM until after running loop rotate tweaked LICM runs to preserve metadata in more cases (the motivation there was tbaa metadata).

See [basic.indet] for why it is legal.

Mostly things that cause pain are like:

• getSCEV(freeze(a+b)) is freeze SCEVUnknown, and nothing useful can be proved for it (i.e. it’s not even a SCEVAdd or smth we can reason about); Things are even worse of `+` is `nuw nsw`(we acnnot sink freeze to its arguments without dropping flags).
• LoopPredication & IndVars & IRCE & Guard Widening stumble over Freezes when trying to recognize comparison patterns;
• Sometimes random pattern matchers break in other places

Mostly these things are caused by frozen loads, but I can see this happening to calls as well (until some point, our loads are represented as abstraction calls).

Thanks! I didn’t realize C++ allows UB where we’d normally have poison… Live long, learn long.

Speculatable function can’t exibit undefined behavior:

This function attribute indicates that the function does not have any effects besides calculating its result and does not have undefined behavior.

Also, a function can be marked speculatable only at the declaration.

This attribute is only valid on functions and declarations, not on individual call sites. If a function is incorrectly marked as speculatable and really does exhibit undefined behavior, the undefined behavior may be observed even if the call site is dead code.

This is intentional. This attribute can only be used for functions that are unconditionally speculatable.

Looks like using noundef arguments on a speculatable functions is a perfect recipe for UB. You can still mark the returned value as noundef if this fact is unconditional.

FWIW it’s a bit less obvious for C, see