[llvm-dev] funnel shift, select, and poison
John Regehr via llvm-dev
llvm-dev at lists.llvm.org
Mon Feb 25 15:53:43 PST 2019
Great to see you've avoided the less-than-obvious pitfall of
transforming funnel shift by not-constant into a shift!
(Background for people not following this as closely: Unlike LLVM's
regular shifts, the funnel shifts mask the shift exponent. This removes
potential UBs but also introduces an impedance mismatch WRT shift.)
John
On 2/25/19 4:17 PM, Sanjay Patel wrote:
> 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
> <mailto: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
> <mailto: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 <mailto:llvm-dev at lists.llvm.org>
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
More information about the llvm-dev
mailing list