killing undef and spreading poison

Nuno,
we still need some examples showing that the definition
“Branching on poison is immediate-UB” is the best choice,

so far we only have arguments against it (the one for loop-switching).

Excerpts from the Paper [1]

Here’s the example you give for GVN

t = x + 1;
if (t == y) {
w = x + 1;
foo(w);
}
Therefore, GVN can pick y as the representative value and transform the code into:
t = x + 1;
if (t == y) {
foo(y);
}
However, if y is a poison value and w is not

This really hinges on an incorrect choice for representative value of w.

Any value with the “poison” attribute is not a valid representative for any
seemingly equivalent value. If GVN is actually doing this it is a bug in GVN.

So this example doesn’t really show anything about branching.

Peter Lawrence.

[1. http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf ]

Hi Peter,

Nuno,
          we still need some examples showing that the definition
“Branching on poison is immediate-UB” is the best choice,
so far we only have arguments against it (the one for loop-switching).

The alternative that allows us to propagate equalities in GVN (which
you seem to be alluding at) is to use an undef "instruction" that
produces a fixed but arbitrary value (just like "freeze(poison)" would
today). However, that's bad for codegen since in some cases we will
have to keep around a live register containing consistent garbage.
Having both freeze and poison lets us use poison when we can (with
better codegen), and freeze when we must (with worse codegen) -- this
is the having-our-cake-and-eating-it-too scenario I was referring to
earlier.

-- Sanjoy

Hi Peter,

Sanjoy,
My belief is that this is a register allocation problem
that should not be addressed in the IR.

However you have changed the subject, and we still need an example
showing why the proposed definition for branch is the right one.

Peter Lawrence.

Can you explain how this is a register allocation problem? If I have “values” then I cannot elide them when performing shuffle transformation, but when I have 'undef’s I can.

I think that it is also essential to differentiate between “undefined behaviour” and “implementation defined behaviour”. These are discrete concepts in the ISO Standards lexicon because they have very different meanings and purpose.

MartinO

Hi Peter,

            My belief is that this is a register allocation problem
that should not be addressed in the IR.

This is getting weird since you've started so many threads, but it
isn't *just* a register allocator problem (edit: just noticed that
Martin something similar) -- in your "live in undef value" scheme
there also are mid-level optimizations we will not be able to do.

However you have changed the subject, and we still need an example

I'm not convinced that I changed the subject. You said

          we still need some examples showing that the definition
“Branching on poison is immediate-UB” is the best choice,
so far we only have arguments against it (the one for loop-switching).

There are two ways we can avoid branching on “Branching on poison is
immediate-UB” and still have GVN propagate equalities:

- Propagate equalities only if the thing we're propagating isn't
poison. As I've stated in this thread, that's almost impossible to
prove in interesting cases.
- Ditch poison and have an `undef` like instruction (which is
equivalent to a live-in undef register), which brings us the regalloc
and mid-level opt problem.

So both of the thing I said seem on-topic to me.

-- Sanjoy

Sanjoy,
we still need an example, some C source code, that shows
clearly why the definition of immediate-UB for branch-on-undef / poison
is the right choice. Talking, even on topic, isn’t an example.

Peter Lawrence.