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

Tue Feb 26 03:48:38 PST 2019

Ok, sounds good.
I'm convinced. I'll change the semantics in Alive to block poison when  
shift_amount % bits == 0.
LangRef should probably be updated as well.

Thanks,
Nuno

Quoting Sanjay Patel <spatel at rotateright.com>:

> We have these transforms from funnel shift to a simpler shift op:
>       // fshl(X, 0, C) -> shl X, C
>       // fshl(X, undef, C) -> shl X, C
>       // fshl(0, X, C) -> lshr X, (BW-C)
>       // fshl(undef, X, C) -> lshr X, (BW-C)
>
> These were part of: https://reviews.llvm.org/D54778
>
> In all cases, one operand must be 0 or undef and the shift amount is a
> constant, so I think these are safe. If X is poison, we'll transform from a
> poisonous funnel shift to a poisonous shift (no need to introduce any
> special poison blocking behavior).
>
> On Mon, Feb 25, 2019 at 4:01 PM Nuno Lopes <nunoplopes at sapo.pt> wrote:
>
>> You are very right! Transformation to rotate is correct.
>>
>> So I guess the remaining case is if you want to be able to transform
>> funnel
>> shifts into other arithmetic operations when %x != %y. I think I saw some
>> optimizations where fshl was being transformed into shl. This wouldn't be
>> OK
>> because shl doesn't stop poison. Unless these are only being done for
>> guaranteed non-zero %sh? Then it's ok because fshl can't possibly block
>> poison in that case.
>>
>> Nuno
>>
>>
>> -----Original Message-----
>> From: Sanjay Patel
>> Sent: Monday, February 25, 2019 10:30 PM
>> Subject: Re: [llvm-dev] funnel shift, select, and poison
>>
>>
>> Don't we need to distinguish funnel shift from the more specific rotate?
>> I'm not seeing how rotate (a single input op shifted by some amount) gets
>> into trouble like funnel shift (two variables concatenated and shifted by
>> some amount).
>> Eg, if in pseudo IR we have:
>> %funnel_shift = fshl %x, %y, %sh ; this is problematic because either x or
>> y
>> can be poison, but we may not touch the poison when sh==0
>> %rotate = fshl %x, %x, %sh ; if x is poison, the op is unquestionably
>> producing poison; there's no sh==0 loophole here
>>
>>
>>
>> On Mon, Feb 25, 2019 at 1:12 PM Nuno Lopes <nunoplopes at sapo.pt> wrote:
>> Thanks Sanjay!
>>
>> I did a quick study of these funnel shifts:
>> The generic lowering to SDAG is correct for the optimization below. It
>> actually stops poison if shift amount is zero:
>>     SDValue ShAmt = DAG.getNode(ISD::UREM, sdl, VT, Z, BitWidthC);
>> (...)
>>     SDValue IsZeroShift = DAG.getSetCC(sdl, CCVT, ShAmt, Zero, ISD::SETEQ);
>>     setValue(&I, DAG.getSelect(sdl, VT, IsZeroShift, IsFSHL ? X : Y, Or));
>>
>> This is assuming select in SDAG stops poison in the same way we've proposed
>> for the IR.
>>
>> However, the lowering has 2 optimizations. It can lower funnel shifts to:
>> 1) A special funnel shift instruction if the backend supports it
>> 2) Rotate
>>
>> At least lowering to rotate would be incorrect if rotate didn't stop poison
>> as well when shift amount == 0. Most likely rotate doesn't block poison
>> though. So this doesn't seem correct.
>>
>> Blocking poison, while tempting, is usually not a good idea because it
>> blocks many optimizations. It becomes hard to remove instructions that
>> block
>> poison. Exactly as you see here: if select blocks poison (and we claim it
>> does), then it cannot be removed.
>>
>> I have 2 separate proposals:
>> 1) Keep select blocking poison, and remove the transformation below because
>> it doesn't play well with 1) lowering to rotate, and 2) because it blocks
>> optimizations like converting funnel shifts to plain shifts
>> 2) Introduce a flag in select, like we have nsw/nuw today that changes the
>> semantics regarding poison. Essentially a select that doesn't stop poison.
>> This can be safely emitted by most frontends of the languages we support
>> today, but wouldn't be used by compiler-introduced selects. The
>> optimization
>> below would only kick in when this flag is present. Of course then we can
>> have an analysis that inserts these flags like we have for nsw.
>>
>> I like 2), but 1) is simpler. I don't know if 2) is worth it, but is
>> appealing :)
>>
>> Nuno
>>
>>
>> -----Original Message-----
>> From: Sanjay Patel via llvm-dev
>> Sent: Monday, February 25, 2019 4:29 PM
>> Subject: [llvm-dev] funnel shift, select, and poison
>>
>>
>> There's a question about the behavior of funnel shift [1] + select and
>> poison here that reminds me of previous discussions about select and poison
>> [2]:
>> https://github.com/AliveToolkit/alive2/pull/32#discussion_r257528880
>>
>> Example:
>> define i8 @fshl_zero_shift_guard(i8 %x, i8 %y, i8 %sh) {
>> %c = icmp eq i8 %sh, 0
>> %f = fshl i8 %x, i8 %y, i8 %sh
>> %s = select i1 %c, i8 %x, i8 %f ; shift amount is 0 returns x (same as
>> fshl)
>> ret i8 %s
>> }
>> =>
>> define i8 @fshl_zero_shift_guard(i8 %x, i8 %y, i8 %sh) {
>> %f = fshl i8 %x, i8 %y, i8 %sh
>> ret i8 %f
>> }
>> Transformation doesn't verify!
>> ERROR: Target is more poisonous than source
>>
>>
>> ----------------------------------------------------------------------------
>>
>> The problem is that if %y is poison and we assume that funnel shift uses
>> all
>> of its operands unconditionally, the reduced code sees poison while the
>> original code is protected by the "conditional poison" (terminology?)
>> property of a select op and is safe.
>>
>> If we treat funnel shift more like a select based on its operation (when
>> the
>> shift amount is 0, we know that the output is exactly 1 of the inputs),
>> then
>> the transform should be allowed?
>>
>> This transform was implemented in instcombine [3] with the motivation of
>> reducing UB-safe rotate code in C to the LLVM intrinsic [4]. So a potential
>> sidestep of the problem would be to limit that transform to a rotate
>> pattern
>> (single value is being shifted) rather than the more general funnel pattern
>> (two values are being shifted).
>>
>> [1] https://llvm.org/docs/LangRef.html#llvm-fshl-intrinsic
>> [2] http://llvm.1065342.n5.nabble.com/poison-and-select-td72262.html
>> [3] https://reviews.llvm.org/D54552
>> [4] https://bugs.llvm.org/show_bug.cgi?id=34924
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev