[llvm-dev] [EXT] Re: funnel shift, select, and poison

[Nuno Lopes via llvm-dev]

I agree we should have some sort of poison/undef in SDAG. It's not  
clear to me which one we should keep, though.

The set of optimizations that happens at SDAG level is different than  
that that happens at IR level.
For example, there's no GVN in SDAG.  GVN, LVI, LICM, and other  
optimizations that propagate equalities from branches, are the reason  
why undef is not a good thing to have at IR level. But since SDAG  
doesn't have such optimizations AFAIK, undef might actually be fine.
(the only case I'm unsure is whether SDAG has a known bits analysis  
that takes branches into account)

Poison, on the other hand, blocks optimizations like select  
simplification, which seems useful to do in SDAG. These optimizations  
can always be deferred to SDAG->MI lowering time, since MI will  
probably never have poison. But then you lose the compound effect of  
the simplifications.

Poison can always be translated to undef. So we can live in a world  
where IR has poison and no undef, and SDAG has undef but no posion.

I don't know enough of the backend to recommend anything beyond saying  
that assuming everything I wrote above is correct, it would be nice to  
test if we could live without poison in SDAG and what the change in  
perf would be.

If we are to keep poison in SDAG, then we need to assume it and start  
fixing the few optimizations that are currently incorrect, and  
potentially move some of them to the SDAG/MI lowering phase.

Thanks,
Nuno


Quoting Eli Friedman <efriedma at quicinc.com>:

> Flags isn’t the only way you can get poison in SelectionDAG; a bunch  
> of operations produce poison.  Among other things, we have shifts  
> with an overflowing shift amount, overflowing fptosi, and  
> AssertZext.  IIRC we take advantage of the fptosi UB to avoid  
> redundant masking in some cases.
>
> I guess we could go through and limit those operations to something  
> else instead… but I’m not quite sure what that would look like.   
> Getting rid of poison isn’t that helpful if we still have undef  
> (particularly if we’re going to try to get rid of undef at the IR  
> level at some point). I guess we could get rid of undef too, but at  
> that point I think you start seriously hurting target-independent  
> SelectionDAG optimizations: every operation has to have a defined  
> output for every possible input (except operations with a chain can  
> be UB, or produce an output that’s “defined” based on the chain).  I  
> guess that would involve adding target-defined behavior for a bunch  
> of operations, along the lines of getBooleanContents().
>
> It makes sense say poison/undef don’t exist after isel.  That might  
> block some optimizations in theory, I guess, but I think that  
> matches the way it currently works.  (We currently have “undef”  
> operands in MachineInstrs, but that isn’t the same thing.)  Well,  
> actually, I think the use of alias analysis in scheduling breaks  
> this (since the result of a load which violates TBAA can be changed  
> by the scheduler), but I don’t think that’s ever led to a practical  
> issue.
> -Eli
>
> From: Sanjay Patel
> Sent: Wednesday, February 27, 2019 9:38 AM
> To: Nuno Lopes <nunoplopes at sapo.pt>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; John Regehr <regehr at cs.utah.edu>
> Subject: [EXT] Re: [llvm-dev] funnel shift, select, and poison
>
> I don't think anyone at that time realized that we were poisoning  
> SDAG by extending the flags. :)
>
> So yes - and this is probably setting myself up for a suicide  
> mission - I think we should undo that decision.
>
> A transform that I remember adding to SDAG that depends on wrapping was here:
> https://reviews.llvm.org/D13757
> ...and that shows that the cleanup would have to extend to  
> target-specific files. It also suggests the solution: deal with all  
> poison-related transforms in IR in CGP (or a dedicated codegen IR  
> pass) before we form the DAG, and then drop those bits.
>
> On Wed, Feb 27, 2019 at 9:12 AM Nuno Lopes  
> <nunoplopes at sapo.pt<mailto:nunoplopes at sapo.pt>> wrote:
> You are right: select in SDAG has to be poison-blocking as well,
> otherwise the current lowering from IR's select to SDAG's select would
> be wrong. Which makes the select->or transformation incorrect at SDAG
> level as well.
> I guess until recently people believed that poison in SDAG wasn't much
> of a problem (myself included). I was convinced otherwise with the
> test cases that Juneyoung found a few weeks ago:
> https://bugs.llvm.org/show_bug.cgi?id=40657
>
> MI doesn't have poison AFAIK, so at least we are safe there, I hope
> (not sure about undef, though).
>
> I don't know if there was a thorough discussion on the performance
> benefits of having poison in SDAG, though. Is it that important? are
> there loop-related optimizations that require nsw information?
> If so, then we should pay the price and fix SDAG. (and extend Alive to
> verify SDAG as well -- ok, I'm hanging myself here, but..). If not,
> maybe getting rid of poison in SDAG could be a good thing.
> There's also undef, which I don't know exactly what's the semantics,
> but AFAIR is as bad as the IR's.
>
> Nuno
>
>
> Quoting Sanjay Patel via llvm-dev  
> <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>:
>
>> I don't object to deferring the optimization, but let me check my poison
>> understanding...
>>   select i1 %cond, i1 true, i1 %x --> or i1 %cond, %x
>>
>> 1. 'select' is a poison-blocking operation, but 'or' is
>> non-poison-blocking, so we are propagating a potentially poisonous %x with
>> this transform.
>> 2. We will fix the problem in IR by removing this transform in IR
>> 3. The backend (SDAG) has that same transform.
>> 4. SDAG has poison because we propagate the wrapping/exact flags to DAG
>> nodes.
>> 5. Are we just sweeping the bug under the rug? Nobody cares because SDAG is
>> undocumented, so anything goes down there?
>>
>>
>> On Tue, Feb 26, 2019 at 2:06 PM John Regehr via llvm-dev <
>> llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>>> > Transforms/InstCombine/select.ll
>>> > ================================
>>> > define i1 @trueval_is_true(i1 %C, i1 %X) {
>>> >   %R = select i1 %C, i1 1, i1 %X
>>> >   ret i1 %R
>>> > }
>>> > =>
>>> > define i1 @trueval_is_true(i1 %C, i1 %X) {
>>> >   %R = or i1 %C, %X
>>> >   ret i1 %R
>>> > }
>>> > ERROR: Target is more poisonous than source (when %C = #x1 & %X = poison)
>>> >
>>> > (there are many variations of these select->arithmetic transformations)
>>>
>>> This particular little family of transformations can be reliably done by
>>> all of the backends I looked at, so disabling them at the IR level
>>> should be OK. See a bit more discussion here:
>>>
>>> > https://bugs.llvm.org/show_bug.cgi?id=40768
>>>
>>> John