[llvm-dev] funnel shift, select, and poison

Wed Feb 27 13:25:54 PST 2019

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: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Sanjay Patel via llvm-dev
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190227/2223f3a1/attachment.html>