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

[Sanjay Patel via llvm-dev]

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190225/b47429a6/attachment.html>