What is the status of the "Killing Undef and Spreading Poison" RFC?

Hi,

Back in 2016 an RFC titled "Killing Undef and Spreading Poison" [1] was posted on this mailing list, which generated a lot of discussion between different people. Later in 2017, a paper titled "Taming Undefined Behavior in LLVM" [2] was published, detailing the various concerns introduced in the RFC. There is also a patch proposal with an initial implementation of the `freeze` instruction on the LLVM review website [3].

As far as I can see, there has been no public activity on that matter since mid-2017. What is the current status?

Thanks, Benoit

References:
[1]: https://lists.llvm.org/pipermail/llvm-dev/2016-October/106182.html
[2]: https://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
[3]: https://reviews.llvm.org/D29011

Hi,

Let me give you my view of the status:
The proposal you mentioned was, I believe, well understood and accepted. Except for one bit, which was that it requires correct typing of load/store operations. That is, if you load an i32, it means you are loading a single 32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect this property. Clang may pass several parameters as a single variable, LLVM has optimizations that combine several loads into a single integer load, etc.
So in some places of LLVM it is assumed that ix is just a bag of x bits and not an integer of x bits.

My personal opinion is that we should fix LLVM/clang such that memory operations are properly typed. We have proposed this through the use of vectors. While there were supporters for this approach, there wasn't a consensus. To be fair, we didn't implement a complete prototype for this idea nor did we conduct a thorough discussion.

Right now Sanjoy is working off-list on an alternative proposal, which is to have bit-wise semantics for poison. This removes the constraint that memory operations need to be well typed. This proposal is not ready yet AFAICT, but it will be presented and discussed once it is :slight_smile:

BTW, allowing the compiler to introduce type-punning memory operations is actually wrong when implicit integer-to-pointer casts are introduced. Nevertheless, one can argue that it is a smaller problem to fix than fixing all incorrectly-typed memory operations.

I hope this helps. Let me know if you have further questions. Unfortunately I cannot offer any timeline on when this issue will be fixed.

Nuno

Quoting Benoit Vey via llvm-dev <llvm-dev@lists.llvm.org>:

Do you have a link to this vector-based proposal? Suppose Clang
currently lowers a parameter of type struct { int32_t, int8_t, int8_t,
int8_t, int8_t } to i64, neither changing this to <8 x i8> or <2 *
i32> seems correct - but perhaps one of those options is close enough
for your requirements?. This is a disruptive change of course: there
is an often under-specified contract between the frontend and target
backend on the ABI lowering of function parameters and return values.
Changing the requirements here will require changes for every LLVM
language frontend. If a big shake-up of this part of LLVM is the way
forwards, it would probably be worth taking the time to consider all
possible options for improvement.

Best,

Alex

I just realized there isn't much information about this proposal. The best I could find is slides 23-24 of this: http://llvm.org/devmtg/2016-11/Slides/Lopes-LongLivePoison.pdf

The basic idea is that instead of accessing 2 shorts as i32, you could access them as <2 x i16>. In case of structures with different element types, you would need to use structures, which LLVM also supports. For the proposal to be correct, you can slice a value into smaller vector elements, but you cannot share a vector element across two values.
For example, representing you struct example as <8 x i8> would be correct, but not as <2 x i32>. Or we can use structures to have elements of the exact size.

You are right that the ABI lowering and the contracts for vectors are a bit underspecified. That's probably one of the reasons why vectors of i1s crash and generate bad code frequently. Is there padding between vector elements or not? Or are sub-word elements packed somehow?

Nuno

Hi Nuno,

Except for one bit, which was that it requires correct typing of load/store operations. That is, if you load an i32, it means you are loading a single 32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect this property. Clang may pass several parameters as a single variable, LLVM has optimizations that combine several loads into a single integer load, etc.

What are the places in llvm and clang that do this kind of type punning? So far I only encountered them in SROA and in memcpys generated by clang. I would be very interested in getting rid of them.

My personal opinion is that we should fix LLVM/clang such that memory operations are properly typed. We have proposed this through the use of vectors. While there were supporters for this approach, there wasn’t a consensus. To be fair, we didn’t implement a complete prototype for this idea nor did we conduct a thorough discussion.

Would you be able to post a link to these discussions? I would like to understand the potential cons of such change.

Best,
Jakub

Hi Nuno,

Except for one bit, which was that it requires correct typing of

load/store operations. That is, if you load an i32, it means you are
loading a single 32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect

this property. Clang may pass several parameters as a single variable, LLVM
has optimizations that combine several loads into a single integer load,
etc.

What are the places in llvm and clang that do this kind of type punning?

Clang does this for ABI's all the time.
Pointers to structs passed as i64, etc.

So far I only encountered them in SROA and in memcpys generated by clang.
I would be very interested in getting rid of them.

My personal opinion is that we should fix LLVM/clang such that memory
operations are properly typed. We have proposed this through the use of
vectors. While there were supporters for this approach, there wasn't a
consensus. To be fair, we didn't implement a complete prototype for this
idea nor did we conduct a thorough discussion.

Would you be able to post a link to these discussions? I would like to
understand the potential cons of such change.

While i'm a big supported of proper typing (because we are otherwise just
throwing valuable aliasing info away, and already suffer for it), people
seem to want to move in the other direction, and it would likely require a
stronger type system in LLVM anyway.

Hi,

Let me give you my view of the status:
The proposal you mentioned was, I believe, well understood and accepted.
Except for one bit, which was that it requires correct typing of
load/store
operations. That is, if you load an i32, it means you are loading a
single
32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect this
property. Clang may pass several parameters as a single variable, LLVM
has
optimizations that combine several loads into a single integer load, etc.
So in some places of LLVM it is assumed that ix is just a bag of x bits
and
not an integer of x bits.

My personal opinion is that we should fix LLVM/clang such that memory
operations are properly typed. We have proposed this through the use of
vectors. While there were supporters for this approach, there wasn't a
consensus. To be fair, we didn't implement a complete prototype for this
idea nor did we conduct a thorough discussion.

Do you have a link to this vector-based proposal? Suppose Clang
currently lowers a parameter of type struct { int32_t, int8_t, int8_t,
int8_t, int8_t } to i64, neither changing this to <8 x i8> or <2 *
i32> seems correct - but perhaps one of those options is close enough
for your requirements?. This is a disruptive change of course: there
is an often under-specified contract between the frontend and target
backend on the ABI lowering of function parameters and return values.
Changing the requirements here will require changes for every LLVM
language frontend. If a big shake-up of this part of LLVM is the way
forwards, it would probably be worth taking the time to consider all
possible options for improvement.

I just realized there isn't much information about this proposal. The best I
could find is slides 23-24 of this:
http://llvm.org/devmtg/2016-11/Slides/Lopes-LongLivePoison.pdf

The basic idea is that instead of accessing 2 shorts as i32, you could
access them as <2 x i16>. In case of structures with different element
types, you would need to use structures, which LLVM also supports. For the
proposal to be correct, you can slice a value into smaller vector elements,
but you cannot share a vector element across two values.
For example, representing you struct example as <8 x i8> would be correct,
but not as <2 x i32>. Or we can use structures to have elements of the exact
size.

But structures tend not to be handled as you would like for call
lowering, which is why the Clang frontend will often 'lie' about their
type to ensure that they are passed according to the ABI rules. I
think someone once described ABI/calling convention handling as
happening both too early and too late. You're forced to do some of the
work much earlier than you might expect - in your language frontend.
You then do the other half of the work in call lowering,
post-legalisation when structs have been split into their constituent
elements and illegal types have been split. It's surely not
insurmountable, but I expect a change here will require substantial
design and implementation effort, not to mention testing for
regressions.

I would like to see this improved in some way, but it's worth
recognising that going this route puts "fixing LLVM/Clang ABI
lowering" on the critical path. There hasn't been complete consensus
that there is a problem to fix, but even amongst those frustrated with
the status quo nobody has had the time to prototype an alternative
solution. Perhaps this extra potential benefit will help in that
respect.

You are right that the ABI lowering and the contracts for vectors are a bit
underspecified. That's probably one of the reasons why vectors of i1s crash
and generate bad code frequently. Is there padding between vector elements
or not? Or are sub-word elements packed somehow?

Honestly it's been a while since I looked at the handling of vectors
in call lowering.

Best,

Alex

Except for one bit, which was that it requires correct typing of load/store

operations. That is, if you load an i32, it means you are loading a single
32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect this

property. Clang may pass several parameters as a single variable, LLVM has
optimizations that combine several loads into a single integer load, etc.

What are the places in llvm and clang that do this kind of type punning? So
far I only encountered them in SROA and in memcpys generated by clang. I
would be very interested in getting rid of them.

Besides the ones you and Daniel mentioned there's also GVN. If GVN concludes that a load of a pointer and a load of an integer are equal, e.g. (load i64**) = (load i64*), then it will get rid of one of the loads and insert an inttoptr/ptrtoint.
This is incorrect (in our memory model, at least), since GVN is essentially introducing implicit casts with the memory operations. One of the consequences of memory models that support implicit casts is that they make dead store eliminiation illegal in general, which is not really desirable (more details in the paper draft I sent you).

My personal opinion is that we should fix LLVM/clang such that memory
operations are properly typed. We have proposed this through the use of
vectors. While there were supporters for this approach, there wasn't a
consensus. To be fair, we didn't implement a complete prototype for this
idea nor did we conduct a thorough discussion.

Would you be able to post a link to these discussions? I would like to
understand the potential cons of such change.

Sorry, most of the discussions were off-line.

Advantages include of disable type punning include:
  - Make LLVM IR (more) sound and thus enable automatic verification of optimizations
  - Enable additional optimizations. Daniel mentioned better AA. There are other things, like better tracking of padding. In general, merging multiple variables in a single variable confuses most dataflow analyses.

Disadvtanges:
  - Potential for more insert/select element instructions (although fewer bitwise operations to pull out elements)
  - Need a few fixes to Clang for the ABI lowering stuff

I'm surely forgetting something, but that's what on the top of my head.

Nuno

Except for one bit, which was that it requires correct typing of load/store

operations. That is, if you load an i32, it means you are loading a
single
32-bit integer, not two 16-bit integers or something else.

This is a valid concern because currently nor LLVM nor clang respect this

property. Clang may pass several parameters as a single variable, LLVM
has
optimizations that combine several loads into a single integer load, etc.

What are the places in llvm and clang that do this kind of type punning?
So
far I only encountered them in SROA and in memcpys generated by clang. I
would be very interested in getting rid of them.

Besides the ones you and Daniel mentioned there's also GVN. If GVN
concludes that a load of a pointer and a load of an integer are equal, e.g.
(load i64**) = (load i64*), then it will get rid of one of the loads and
insert an inttoptr/ptrtoint.
This is incorrect (in our memory model, at least), since GVN is
essentially introducing implicit casts with the memory operations. One of
the consequences of memory models that support implicit casts is that they
make dead store eliminiation illegal in general, which is not really
desirable (more details in the paper draft I sent you).

Note:This is also illegal in non-integral pointer types, IIRC, and so as
that becomes less experimental, this has to be changed at least for that.