[RFC] Add nopoison attribute/metadata

IR & Optimizations
1

Motivation

LLVM currently has a noundef attribute, which triggers immediate undefined behavior if a value containing undef or poison bits is passed/returned. There is also !noundef load metadata with the same semantics.

This attribute is leveraged by many optimizations that would otherwise be illegal or have to introduce freeze instructions.

Unfortunately, some frontends like Rust cannot emit noundef in some fairly common cases. For example, Rust enums (tagged unions in C terms) may only be partially initialized, depending on which enum member is active.

However, Rust could use a nopoison attribute for all values, because it does not expose any poison semantics. I believe this is also true of pretty much all other frontends (including Clang), which only use immediate undefined behavior in their semantics, not poison propagation.

While nopoison is weaker than noundef and enables less optimizations, it still covers some important cases. For example, select Cond, undef, X can be folded to X if we know that X is not poison – it doesn’t matter whether it can be undef. The same holds for all other places that use either isGuaranteedNotToBePoison() or impliesPoison().

Proposal

Add a nopoison argument and return attribute, with the following wording (copied from noundef):

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

Also add a !nopoison !{} load metadata with the same semantics.

Once support for undef has been removed (or at least disallowed inside function bodies), the current noundef attribute would be removed and only nopoison would remain.

Interaction of noundef and nopoison

This proposal suggests to leave the current semantics of noundef alone: That is, noundef continues to imply that the value is both not undef and not poison. Specifying both the noundef and nopoison attributes at the same time is equivalent to specifying just noundef.

An alternative would be to separate these, and say that noundef only implies that the value is not undef, but can be poison. We do (since recently) make that separation in our internal queries, but I don’t think there is a use-case for exposing this to the attribute system. I’d rather avoid the extra churn for an attribute that will go away in the future anyway.

5 Likes
2

+1

3

+1 makes complete sense

4

Nit: that wording sounds odd to me since AIUI the whole value is poison or not; you can’t have individual bits being poison.

No objection to the new attribute/metadata.

5

I cannot imagine that what a poison value in the memory stands for.
If it is meaningless, I think the following changes will make things easier:

  • Storing a poison value is immediate UB.
  • A loaded value is never poison.
6

This is a great question :slight_smile: I have some thoughts on it.

First, in the context of metadata, one important secondary use-case for !noundef is how it acts in conjunction with other metadata like !nonnull or !range. In that case, it indicates that the value after application of other metadata is noundef. In particular, this means that violation of !nonnull etc becomes immediate undefined behavior instead of returning poison.

As such, even if we say that memory itself cannot contain poison, we would still need an attribute to promote from poison to UB semantics. Currently !noundef is fine for that. If we remove undef at some point, we’d need !nopoison then. But it would be fine to defer it until that time, as it would just be a rename at that point.

Second, there is the question of how we will go about removing the last major user of undef: Uninitialized memory. I think the plan that @nlopes originally had in mind is that we will consider uninitialized memory to be poison, and compensate for this with some variation on “freezing load” in cases where it is relevant.

If we go down that road, we obviously have to allow poison in memory. However, I think that making uninitialized memory poison causes a lot of complications that we don’t have great answers for, and I think the most recent iteration on this ([RFC] Load Instruction: Uninitialized Memory Semantics) has essentially reintroduced a concept of uninit memory that is distinct from poison.

What I am leaning towards nowadays, is to leave uninitialized memory as undef (maybe with a rename to uninit) and only forbid its use as an SSA value. That is, alloca is still implicitly initialized to undef, you can have a global variable with undef in its initializer, but function IR never contains undef, only freeze poison.

I think that this still addresses the main pain point of undef, which is the inconsistent multi-use problem. The main externality relative to poison is that you cannot, in general, duplicate loads (though I guess we could keep !noundef to allow that).

Third, not allowing poison in memory solves a lot of open miscompilation problems. E.g. we can combine byte-wise comparisons into a wide comparison, optimize away store undef, etc. The memcpy → load/store problem would not be fully fixed due to provenance, but it would fix one key facet.

Fourth, forbidding poison in memory closes the door on frontends exposing poison semantics. For example, some Rust developers were playing with the thought of exposing a type that does FP with FMF and can hold poison. I don’t think that LLVM should feel obligated to support this use-case though.

Overall, unless I’m missing something major, I think that forbidding poison in memory would be a good move. I’d like to hear @nlopes thoughts on it.

2 Likes
7

Are you suggesting that storing poison to memory would be instant UB? That means we can’t hoist stores past a non-willreturn call, even if we prove noalias. And transforms like reg2mem would need to freeze the stored values. But maybe it’s workable.

8

Yes.

We already cannot do this without proving further preconditions due to read-only memory and data races. As far as I know, we only have three transforms which do some form of store speculation, which are:

  • Call slot optimization: This one doesn’t actually introduce any new stores, it only changes the store target. So it should not be affected.
  • LICM scalar promotion: This does introduce a store where none existed previously, but in the speculated case it will store back a just loaded value – which cannot be poison under the new semantics.
  • SimplifyCFG store speculation: In the speculated case, this will store either a loaded or a stored value, both of which exclude poison under the new semantics.

Right. As far as I can tell, the only in-tree user of reg2mem is SjLjEHPrepare, so the impact of that should be very limited. Are you aware of other places doing a reg2mem like transform on IR?

We do have more reg2mem style transforms once we leave IR behind. A few that come to mind are:

  • RA spilling. We probably don’t care about poison anymore at that point though.
  • Passing arguments via stack (at SDAG/MIR level).
  • Shift legalization via stack.

So possibly it may make sense to allow poison in memory once we leave IR behind. I’m not really familiar with what the tradeoffs would look like at that level.

9

I just caught @RalfJung here and we were discussing this.

Making storing poison UB wouldn’t work for vectors. It’s not uncommon to have poison lanes.

Besides that, I have a student (@jmciver) finishing a prototype of load !freeze, which freezes the loaded bits before converting into the value type. That should allows us to remove undef for good. We will share perf results soonish.

1 Like
10

This is a good point. But do those poison lanes actually reach store instructions? Normally lanes are poison if they are non-demanded, in which case they also don’t get stored.

I know that some compiler builtins produce partially undefined vectors, though I think we decided that those actually shouldn’t use poison lanes, and they use freeze poison instead nowadays.

Does vectorization create non-masked widened stores with poison elements? I would have guessed “no” because of the usual store speculation problems, but I’m unsure about this.

11

Maybe it’s a knee-jerk reaction on our side. Marking store poison as UB is a big change from the current semantics and thinking. It’s also not backwards compatible, so we would need to have automatic conversion from store.v1 into freeze + store.v2.

Also, we need to articulate with Rust to make sure store uninit of Rust is well supported.
Ah, there are also optimizations that introduce stores, like loop vectorization (but that’s probably ok as it introduces a round-trip and since you can’t store poison, you can’t load it either – so introduction of round trips is fine).

I’m on travel right now; let me think on this proposal more carefully next week.

12

This is the case right now, but I think we would like to expose delayed (poison-style) UB in Rust at some point. Requests for this appear fairly regularly, e.g. as a way to safely expose fast-math (have a new type that allows poison, and a safe method to convert to regular float types that calls freeze), and to deal with vectors where some lanes are poison.

So from a Rust perspective I am concerned that this proposal will lock us in a corner where we cannot have these features in the language.

Given that undef is slated for removal (in my understanding), a transformation involving undef is IMO not a great justification for such a fundamental change.

In my view, poison is the only “invalid value” LLVM needs (no need for undef, no need for a separate concept of “uninitialized memory”), so it stands for uninitialized memory and padding.

It seems to me like all these are solved by having some type that can hold arbitrary data, everything representable in memory. If you have undef/uninit in memory but not as an SSA value, then a load-store roundtrip is not a NOP so you need to carefully argue why removing a redundant store is okay. Also given that the provenance problem exists, I don’t see how “no poison in memory” actually helps. Whatever solution later materializes for provenance will likely also deal with poison in memory, and then we can avoid limiting frontends to the “nopoison” subset of LLVM.

I think the fundamental problem is: Having memory contents that cannot be represented as SSA values, or vice versa, will always introduce friction. The principled fix is to make sure that both memory and SSA values can represent the same things, to make seamless roundtrips possible.

That’s why I think a proper solution requires either a byte type, or making iN explicitly able to hold all in-memory-data in a lossless way and add some sort of attribute for “no provenance, no poison in any bit” (as in this proposal).

The Rust frontend needs to be able to store everything in allocas – if I can have a variable x: T, I can always create a reference to it and pass that out to other code, which requires x to be stored into an alloca. So if we want Rust code to be able to have a vector with some lanes being poison, we need to be able to store that to memory. More broadly speaking, a value that is UB to store in memory is a concept that makes no sense for Rust as all data only exists in memory. Local variables are merely pointers to somewhere in memory where the actual data is stored.

This is unrelated to this discussion, but note that storing back a just-loaded value is still a data race if there are concurrent accesses, so introducing such stores in a concurrent program can introduce UB.

1 Like
13

poison is used for speculating arithmetic instructions. If we cannot benefit from speculation (e.g., div/rem/store), we should mark it as immediate UB. IMO a load from uninitialized memory should act as freeze poison. Folding it into poison cannot improve optimizations on well-defined programs.

14

Treating uninitialized memory (so, in particular, the initial contents of an allocad local variable) as not having some fixed bit pattern is quite valuable because it means the compiler does not have to worry about using a consistent value for multiple uses of this variable – it can just use whatever register each time. So there’s a clear benefit from making uninit memory different from freeze poison.

It’s not even just uninit memory; when a load races with a store, LLVM currently treats this the same as a load from uninit memory, i.e. makes it undef. Making this be freeze poison is quite problematic as it disallows re-loading the same value from memory again later: if the original program did a single load, but there’s enough register pressure to make it beneficial to re-load this value later rather than keeping it in a register all the time (and analysis concluded that this function doesn’t write to that location and doesn’t perform synchronization with other threads), then freeze poison semantics still do not permit this re-load as there might be a data race which could lead to a different bit pattern being observed the second time.

If uninit memory (and the result of a racy load) is different from a regular initialized iN, there are two options: either re-use poison as a general marker for “value you must not look at”, or introduce a second, distinct kind of “magic” value specifically for uninit memory. I think there is very little benefit to the latter approach, and the better choice it expand the scope of poison from “arithmetic gone wrong” to a more general “computation of this value has gone wrong but if you don’t look at the value then it’s fine”. That lets you speculate not just arithmetic but e.g. loads (if you know they are in-bounds).

15

Any progress? I hope this attribute can help LLVM to remove select cond, X, undef in Rust programs.

16

It seems like we didn’t reach a consensus on “memory cannot be poison in general”, but I think the original proposal for nopoison/!nopoison didn’t have any objections, so I think we can move forward with that.

Even if Rust wants to introduce types that may be poison in the future (e.g. to represent non-demanded vector lanes or floats with FMF) it should still be possible to use nopoison for most types.

1 Like
17

Most of the other points raised above also still stand, though. Without a clear idea of where uninit memory is headed, it seems a bit premature to add a flag like this. The proposal does make it harder to make uninit memory and data races be the same as posion (since that may make existing nopoison attributes invalid), so it takes a side on discussions that AFAIK are still unresolved.

select cond, X, undef should disappear entirely when undef is finally vanquished, so if that’s the only motivation for this change then wouldn’t it be better to figure out where these undef come from and eliminate them? If they come from loads of uninit memory, then the new attribute will become entirely useless if any of the suggested changes for those loads get implemented.

Given that poison is a per-value property, it’s unclear what a “poison bit” is.

18

Agree that we should reach a consensus on allowing poison values in memory before introducing a new attribute.

Here is an example extracted from coreutils-rs: Compiler Explorer
Unfortunately I cannot provide other kinds of examples since llvm-reduce always produces tests with loads of uninit memory.

Since it is impractical to find other kinds of cases introducing undef in real-world code, I am currently focusing on removing undef handling logic in the LLVM codebase (e.g., [InstSimplify] Remove most of undef handling logic by dtcxzyw · Pull Request #119884 · llvm/llvm-project · GitHub). I hope this allows us to concentrate on undefs introduced by Mem2Reg/SROA. Additionally, it will expose UBI bugs earlier as the optimizations become less aggressive (See pre-commit: PR119884 by dtcxzyw · Pull Request #1877 · dtcxzyw/llvm-opt-benchmark · GitHub).

19

Thanks for digging up an example!

Where does the undef come from in this case?

20

To be clear, LLVM currently does have poison in memory. Otherwise, load forwarding is unsound: if a store to memory somehow clears poison (I assume it becomes undef or so? not sure what you had in mind), then storing a value and lading it back out would change the value to something non-poison. Removing this roundtrip (by making the load directly use the originally stored value) would turn that non-poison value into poison again, which is an unsound transformation.

(Or maybe you meant that storing poison values is UB? That’s not documented in the LangRef, so it’d be a pretty fundamental breaking change to introduce such UB, in my opinion. Also, this would make spilling on the IR level unsound.
EDIT: re-reading your messages, you did say it should be UB. But given that there’s not even the slightest indication of this in the LangRef, I would consider that a massive breaking change. I also see no reason for doing this. poison is just yet another value that LLVM variables can carry, and it should be possible to store and load that value to/from memory just like all the other values.)

So it’s not a question whether there can be poison in memory. It’s a question of whether LLVM wants to change its semantics to no longer have poison in memory. But this will be rather non-trivial since optimizations need to be carefully adjusted.

The open question is whether uninit memory is like poison in memory, or whether it is something different.