[llvm-dev] [poison] is select-of-select to logic+select allowed?

Tue May 23 06:25:12 PDT 2017

The examples and table are great! That at least makes it clear what we need
to think about and fix (and just how complex the problem is).

Are there known limitations/objections to the freeze instruction patches
that John listed? Or are we just being cautious and/or waiting for more
people to review those?

I can answer some of the DAG questions:
(a) Yes, we have nsw/nuw/exact down there. They've been around since:
https://reviews.llvm.org/rL210467 .
(b) Yes, we use those bits to enable transforms, but it's not nearly as
common as in IR. It's also likely that we'll drop those bits during
transforms.
(c) Yes, we do all kinds of select transforms without regard for poison.
(d) AFAIK, there is no accounting for poison in the DAG for any transforms,
but it's possible that I just didn't find it in the source.

On Tue, May 23, 2017 at 4:16 AM, Nuno Lopes <nuno.lopes at ist.utl.pt> wrote:

> Hi,
>
>
>
> Let me try to give a bit more context on why select is so tricky.
>
>
>
> First thing to consider is which transformations we would like to support:
>
>
>
> *1) Control-flow -> select (SimplifyCFG)*
>
> if (c)
>
> a = x
>
> else
>
> a = y
>
>
>
>   =>
>
> %a = select %c, %x, %y
>
>
>
>
>
> *2) select -> control-flow*; reverse of 1)
>
> Not sure if this is done at IR level, or only later at SDAG.
>
>
>
>
>
> *3) select -> arithmetic*
>
> %a = select %c, true, %y
>
>   =>
>
> %a = or %c, %y
>
>
>
>
>
> *4) select removal*
>
> %c = icmp eq %x, C
>
> %r = select %c, C, %x
>
>   =>
>
> %r = %x
>
>
>
>
>
> *5) select hoisting past binops*
>
> %a = udiv %x, %y
>
> %b = udiv %x, %z
>
> %r = select %c, %a, %b
>
>   =>
>
> %t = select %c, %y, %z
>
> %r = udiv %x, %t
>
>
>
>
>
> *6) Bonus: easy to move* select instructions around. Should be possible
> to hoist selects out of loops easily.
>
>
>
>
>
> Ideally we want semantics for select that allow all transformations 1-6.
> It's hard because:
>
> 1) %a can only be poison conditionally on %c, i.e., %a is poison if
> %c=true and %x is poison, or %c=false and %y is poison
>
> 2) since we introduce a branch on %c, select on poison has to be UB like
> branch on poison
>
> 3) with arithmetic all operands are always evaluated, so conditional
> poison like in 1) doesn’t work
>
> 4) the example provided replaces C with %x in case %x=C. C is never
> poison, but %x might be.
>
> 5) We cannot introduce a division by poison if %y and %z are not poison
>
> 6) Making select trigger UB for some cases makes movement harder because
> then we need to prove that it won’t trigger UB before e.g. hoisting it out
> of loops.
>
>
>
>
>
> Summary table of what each transformation allows for %z = select %c, %x,
> %y. Each column is a different alternative of semantics for select:
>
>
>
>
>
> UB if %c poison
>
> + conditional poison
>
> UB if %c poison + poison if either
> %x/%y poison
>
> Conditional poison
>
> + non-det choice if %c poison
>
> Conditional poison + poison if %c poison**
>
> Poison if any of
> %c/%x/%y are poison
>
> SimplifyCFG
>
> ✓
>
>
>
> ✓
>
> ✓
>
>
>
> Select->control-flow
>
> ✓
>
> ✓
>
>
>
>
>
>
>
> Select->arithmetic
>
>
>
> ✓
>
>
>
>
>
> ✓
>
> Select removal
>
> ✓
>
> ✓
>
>
>
> ✓
>
> ✓
>
> Select hoist
>
> ✓
>
> ✓
>
> ✓
>
>
>
>
>
> Easy movement
>
>
>
>
>
> ✓
>
> ✓
>
> ✓
>
>
>
> Modulo bugs in the table, you can see there’s no single column with all
> rows with a ✓.  That means there’s no way (that I’m aware of) to make all
> transformations that we are interested in doing to be correct.  A solution
> is to introduce something like the freeze instruction that can land a ✓
> on any cell you want.
>
>
>
> So unless someone has a clever idea and proposes a new column that has
> ticks in all rows, we are left with picking a trade-off: either we disable
> some optimizations, or we introduce something like freeze to continue doing
> them.
>
>
>
> BTW, this table assumes that branch on poison is UB, otherwise
> optimizations like GVN are wrong (for more details see our paper:
> http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf). The column
> marked with ** is the one that Alive currently implements.
>
>
>
> Regarding SDAG: it has undef, and I believe there was some discussion
> regarding introducing poison there as well. I don’t recall if it was
> introduce already, but I believe there’s already nsw/nuw there. If that’s
> the case, the (il)legality of transformations should be exactly the same as
> in LLVM IR.  Otherwise some transformations may be easier.
>
>
>
> Sorry for the longish email; just wanted to give some background about the
> problem so that we can reach some consensus at some point.
>
>
>
> Nuno
>
>
>
>
>
> -----Original Message-----
> From: John Regehr
> Sent: 22 de maio de 2017 21:45
> Subject: Re: [poison] is select-of-select to logic+select allowed?
>
>
>
> Nuno and I have been looking through the results of experiments like the
> one reported here:
>
>
>
>    https://blog.regehr.org/archives/1510
>
>
>
> Indeed there are some select-related transformations in LLVM that are
> illegal in terms of Alive's semantics. As far as we know, they cannot be
> made legal (by adjusting the semantics of instructions) without breaking a
> bunch of other optimizations.
>
>
>
> The optimizations currently in LLVM are not only inconsistent but they can
> lead to end-to-end miscompilations. Sorting this out is going to require
> (1) figuring out what select means WRT poison/undef and (2) backing out
> some optimizations. This is going to be slightly painful but it is the only
> way forward.
>
>
>
> John
>
>
>
>
>
>
>
> On 5/22/17 2:32 PM, Sanjay Patel wrote:
>
> > Some InstCombine transforms for select-of-select were added here:
>
> > https://reviews.llvm.org/rL228409
>
> >
>
> > But Alive says this is more poisonous:
>
> >
>
> > Name: selsel
>
> > %s1 = select i1 %cond1, i8 C1, i8 C2
>
> > %s2 = select i1 %cond2, i8 %s1, i8 C2
>
> >   =>
>
> > %andcond = and i1 %cond1, %cond2
>
> > %s2 = select i1 %andcond, i8 C1, i8 C2
>
> >
>
> > http://rise4fun.com/Alive/JT6
>
> >
>
> > Are those transforms legal?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170523/fe08d60a/attachment-0001.html>