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

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/20170522/bbc53c66/attachment.html>

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?
>

Are we even at a point in the poison semantics discussion where we can reason
about it? Is there a canonical description of poison at the moment which is in
sync with LLVM (and alive)? The LLVM language reference doesn't even seem to
mention the "poison filtering" effect of select; i.e. when the
non-poison input of a select is taken no poison comes out of it. While such a
semantic surely makes sense IMO, it only states that about Phi instructions at
the moment...

Sorry for not being too helpful here and just answering with more questions.
- I assume matching for `select (i1, i8 freeze, i8 freeze)` like patterns would
make this correct and as usefull again. But freeze is not part of official LLVM
AFAIK.
- If this rule is considered a problem today, then we could probably move it to
the SelectionDAG level.

- Matthias
> On May 22, 2017, at 1:32 PM, Sanjay Patel <spatel at rotateright.com>
wrote:
> 
> Some InstCombine transforms for select-of-select were added here:
> https://reviews.llvm.org/rL228409 <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 <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/20170522/5950267f/attachment.html>

I should remind that what we really want to do (at the same time as 
items 1 and 2 below) is to merge poison and undef into a single concept, 
along with adding a new freeze instruction that gives the benefits of 
both without (we hope) the current level of confusion.

We have patches to this effect and we need help moving towards a 
consensus that this approach (or some different approach) is the way 
forward.

https://reviews.llvm.org/D29011
https://reviews.llvm.org/D29121
https://reviews.llvm.org/D29013

John



On 5/22/17 2:45 PM, John Regehr via llvm-dev wrote:
> 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?
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

For background, the reason I was looking at this is because we miss the
transform when the select operands are swapped:

Name: selsel
%s1 = select i1 %cond1, i8 %a, i8 %b
%s2 = select i1 %cond2, i8 %s1, i8 %b
  =>
%notcond1 = xor i1 %cond1, -1
%s1 = select i1 %notcond1, i8 %b, i8 %a
%s2 = select i1 %cond2, i8 %s1, i8 %b

If the transform to and/or is allowed, I'd enhance the matching to account
for this case (if we can invert a condition for free).

I was also wondering about the DAG rules. We don't (need to) consider
poison at that level?



On Mon, May 22, 2017 at 2:50 PM, Matthias Braun <mbraun at apple.com>
wrote:
> Are we even at a point in the poison semantics discussion where we can
> reason about it? Is there a canonical description of poison at the moment
> which is in sync with LLVM (and alive)? The LLVM language reference
doesn't
> even seem to mention the "poison filtering" effect of select;
i.e. when the
> non-poison input of a select is taken no poison comes out of it. While such
> a semantic surely makes sense IMO, it only states that about Phi
> instructions at the moment...
>
> Sorry for not being too helpful here and just answering with more
> questions.
> - I assume matching for `select (i1, i8 freeze, i8 freeze)` like patterns
> would make this correct and as usefull again. But freeze is not part of
> official LLVM AFAIK.
> - If this rule is considered a problem today, then we could probably move
> it to the SelectionDAG level.
>
> - Matthias
>
> On May 22, 2017, at 1:32 PM, Sanjay Patel <spatel at rotateright.com>
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/20170522/590047b7/attachment-0001.html>

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>
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>
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> 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/f98ceab6/attachment.html>