From: "Nuno Lopes" <nuno.lopes@ist.utl.pt>
To: llvm-dev@lists.llvm.org
Cc: "Sanjoy Das" <sanjoy@playingwithpointers.com>, "David Majnemer" <david.majnemer@gmail.com>, "John Regehr"
<regehr@cs.utah.edu>, "Chung-Kil Hur" <gil.hur@sf.snu.ac.kr>, "Juneyoung Lee" <juneyoung.lee@sf.snu.ac.kr>,
"Yoonseung Kim" <yoonseung.kim@sf.snu.ac.kr>, "Youngju Song" <youngju.song@sf.snu.ac.kr>, hfinkel@anl.gov, "Dan
Gohman" <dan433584@gmail.com>, nlewycky@google.com, mbraun@apple.com, qcolombet@apple.com, "t p northover"
<t.p.northover@gmail.com>
Sent: Tuesday, October 18, 2016 7:06:31 AM
Subject: RFC: Killing undef and spreading poison
Hi,
Over the past few years we've been trying to kill poison somehow.
There have
been a few proposals, but they've all failed to pass the bar and/or
to
gather significant support (my own proposals included).
We (David, Gil, John, Juneyoung, Sanjoy, Youngju, Yoonseung, and
myself)
have a new proposal to kill undef instead and replace it with poison
+ a new
'freeze' instruction. We believe this proposal simplifies things at
the IR
level, allows us to fix long-standing bugs in LLVM, and is roughly
performance-neutral for now (and can enable further optimizations in
the
future).
Sorry for the longish email. We will give a talk about this proposal
at the
LLVM dev meeting in November, so hopefully we'll be able to discuss
this
further in person.
We would appreciate any comments, feedback, suggestions, etc. If you
have
questions let me know as well (not everything below is super
detailed, so
please ask where things are not explicit enough).
(I've CC'ed a few people that have been involved in discussions re
semantics
of LLVM IR in the past year or so. Apologies in advance if I forgot
someone
-- which probably I did. I've also CC'ed some CodeGen folks, from
which we
would appreciate input on how this proposal fits within the current
and the
future pipeline)
Thanks for working on this! A couple of questions/comments below:
...
Purpose of Freeze
Poison is propagated aggressively throughout. However, there are
cases where
this breaks certain optimizations, and therefore freeze is used to
selectively stop poison from being propagated.
A use of freeze is to enable speculative execution. For example,
loop
switching does the following transformation:
while (C) {
if (C2) {
A
} else {
B
}
}
=>
if (C2) {
while (C)
A
} else {
while (C)
B
}
Here we are evaluating C2 before C. If the original loop never
executed
then we had never evaluated C2, while now we do. So we need to make
sure
there's no UB for branching on C2. Freeze ensures that so we would
actually
have 'if (freeze(C2))' instead.
Note that having branch on poison not trigger UB has its own
problems.
Can you please elaborate on these problems?
We
believe this is a good tradeoff.
...
Discussion on select
Select is a tricky instruction to define semantics for. There are
multiple
views of select's purpose that are contradictory:
1) Select should be equivalent to arithmetic (e.g., allow 'select
%c,
true, %x' -> 'or %c, %x' and arithmetic -> select)
2) br + phi -> select should be allowed (simplifyCFG)
3) Select -> br + phi should be allowed
To have 1), we need to make select poison if either of its arguments
is
poison. This disallows 2), since there we need to have select being
poison
only if the dynamically-chosen value is poison.
2) and 3) are orthogonal and do not conflict, though.
3) is hard because it requires select to be stronger than branching
(UB-wise), meaning that we would need select to be UB if the
condition was
poison. This blocks a bunch of instcombine patterns, like:
Pre: C < 0
%r = udiv %a, C
=>
%c = icmp ult %a, C
%r = select %c, 0, 1
If %a is poison, then we would be introducing UB. Adding freeze(%c)
would
fix the problem, though.
Since we really want to have 2) since that's simplifyCFG, we propose
to make
'select %c, %a, %b' poison if any of the following holds:
- %c is poison
- %c = true and %a is poison
- %c = false and %b is poison
This disallows 3) and some transformations of 1). Since 3) is only
performed
in CodeGenPrepare, we can safely ignore it (no aggressive
optimizations are
run afterwards).
This strikes me as a dangerous game to play. CGP's transformations need to be semantically sound (even if they are anti-canonical). In part, this is because our IR-level analyses are used by CGP. Moreover, targets after CGP run IR-level transformations, and having different semantic rules there is going to make code reuse hard in subtle ways. Which brings up another issue: We currently have undef at the MI level; do you propose changing that, and if so, how?
-Hal
For 1), we will have to restrict InstCombine
patterns for
the cases when we are sure a given variable is non-poisonous (which
is only
when it came from a 'freeze' instruction or it's the result of a
non-poison-producing instruction).
This semantics also allows arithmetic -> select, but not select ->
arithmetic (without use of freeze).
...
