[llvm-dev] [poison] is select-of-select to logic+select allowed?
John Regehr via llvm-dev
llvm-dev at lists.llvm.org
Tue May 23 09:27:18 PDT 2017
Would it make sense to first commit to a semantics for select, document
this, and attempt to comment out all now-invalid optimizations? We
don't want to remove them entirely since, as Nuno points out, we can
bring some of them back later using appropriate freezes.
What I don't know is who would be affected by the performance
regressions in the meantime, but I suspect that they wouldn't be too big
of a deal for most of us.
John
On 05/23/2017 10:16 AM, Nuno Lopes wrote:
> Regarding the patches, there are two concerns AFAICT:
>
> 1. It’s a new instruction and as usual when introducing a new
> instruction it will require work for some time until most
> optimizations know about it, and to get rid of any potential perf
> regression. No big deal; we just need to do the work (and we have
> already done some of it).
> 2. The patch was written by a student, which may not have time to
> support it properly going forward. That means that someone needs to
> step in and take ownership. Of course we will be here to help, but
> none of us at the moment can commit to own this. The blog post that
> John mentioned below describes our machinery to find bugs in
> optimizations and in new semantics, and we will put it to use to
> test LLVM periodically.
>
> On the plus side, freeze can helps us get rid of a bunch of
> miscompilations, which no one enjoys.
>
> The usage of freeze can be incremental; we can try out with a few things
> to see how it goes. We have more radical ideas down the road, like
> replace undef with poison, but one thing at a time :)
>
> Regarding SDAG, and given that poison is already there, we would need to
> adopt a similar solution to the IR. Maybe right now we can get away
> with it because nsw is not exploited significantly (as you say). Just
> because there’s no explicit poison in SDAG, just having nsw is
> sufficient to cause miscompilations when combined with other
> transformations.
>
> See, for example, this bug report for InstCombine regarding select+nsw:
> https://bugs.llvm.org/show_bug.cgi?id=31633
>
> Nuno
>
> *From:*Sanjay Patel [mailto:spatel at rotateright.com]
> *Sent:* 23 de maio de 2017 14:25
> *To:* Nuno Lopes <nuno.lopes at ist.utl.pt>
> *Cc:* John Regehr <regehr at cs.utah.edu>; llvm-dev
> <llvm-dev at lists.llvm.org>; Matthias Braun <mbraun at apple.com>; Sanjoy Das
> <sanjoy at playingwithpointers.com>; David Majnemer
> <david.majnemer at gmail.com>; Hal Finkel <hfinkel at anl.gov>; Friedman, Eli
> <efriedma at codeaurora.org>
> *Subject:* Re: [poison] is select-of-select to logic+select allowed?
>
> 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
> <mailto: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?
>
More information about the llvm-dev
mailing list