Sanjay Patel via llvm-dev
2019-Feb-26 19:02 UTC
[llvm-dev] funnel shift, select, and poison
If I got poison propagation right, it's probably only by luck! Hopefully, the funnel shift bug is fixed here: https://reviews.llvm.org/rL354905 Nuno, IIUC this means that you do *not* need to change the funnel shift semantics in Alive. So I think that means we're still on track to go with John's suggestion that only select and phi can block poison? (I don't know of any objections to that proposal.) Either way, I agree that we should make it clearer in the LangRef. We have this bug: https://bugs.llvm.org/show_bug.cgi?id=40768 I'm looking at select canonicalization from a different angle because I think we're still optimizing those away too soon in some cases. So it's possible that I can solve that one semi-accidentally. Are there any other reports like that 1 that you are tracking? On Mon, Feb 25, 2019 at 4:53 PM John Regehr via llvm-dev < llvm-dev at lists.llvm.org> wrote:> 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 > > > _______________________________________________ > 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/20190226/f97466d4/attachment.html>
That patch fixes things, yes, thank you! The poison semantics is now
non-blocking and all funnel shif tests in LLVM pass Alive's verification.
Regarding select, we haven't filled other bug reports other than the one you
mentioned IIRC.
I see a few failures in the test suite, e.g.:
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)
Transforms/InstCombine/select-bitext.ll
======================================define i32 @test_sext1(i1 %cca, i1 %ccb) {
%ccax = sext i1 %cca to i32
%r = select i1 %ccb, i32 %ccax, i32 0
ret i32 %r
}
=>
define i32 @test_sext1(i1 %cca, i1 %ccb) {
%narrow = and i1 %ccb, %cca
%r = sext i1 %narrow to i32
ret i32 %r
}
ERROR: Target is more poisonous than source (%cca = poison & %ccb = #x0)
Transforms/InstCombine/select-of-bittest.ll
==========================================define i32 @f_var2(i32 %arg, i32
%arg1) {
%tmp = and i32 %arg, 1
%tmp2 = icmp eq i32 %tmp, 0
%tmp3 = lshr i32 %arg, %arg1
%tmp4 = and i32 %tmp3, 1
%tmp5 = select i1 %tmp2, i32 %tmp4, i32 1
ret i32 %tmp5
}
=>
define i32 @f_var2(i32 %arg, i32 %arg1) {
%1 = shl i32 1, %arg1
%2 = or i32 %1, 1
%3 = and i32 %2, %arg
%4 = icmp ne i32 %3, 0
%tmp5 = zext i1 %4 to i32
ret i32 %tmp5
}
ERROR: Target is more poisonous than source (%arg = #x00000001 & %arg1 =
undef)
Transforms/InstCombine/unsigned_saturated_sub.ll
===============================================define i64 @max_sub_ugt(i64 %a,
i64 %b) {
%cmp = icmp ugt i64 %a, %b
%sub = sub i64 %a, %b
%sel = select i1 %cmp, i64 %sub, i64 0
ret i64 %sel
}
=>
define i64 @max_sub_ugt(i64 %a, i64 %b) {
%1 = icmp ugt i64 %a, %b
%2 = select i1 %1, i64 %a, i64 %b
%3 = sub i64 %2, %b
ret i64 %3
}
ERROR: Value mismatch (%a = 0 & %b = undef)
Thanks,
Nuno
-----Original Message-----
From: Sanjay Patel via llvm-dev
Sent: Tuesday, February 26, 2019 7:02 PM
Subject: Re: [llvm-dev] funnel shift, select, and poison
If I got poison propagation right, it's probably only by luck!
Hopefully, the funnel shift bug is fixed here:
https://reviews.llvm.org/rL354905
Nuno, IIUC this means that you do *not* need to change the funnel shift
semantics in Alive.
So I think that means we're still on track to go with John's suggestion
that
only select and phi can block poison?
(I don't know of any objections to that proposal.) Either way, I agree that
we should make it clearer in the LangRef.
We have this bug:
https://bugs.llvm.org/show_bug.cgi?id=40768
I'm looking at select canonicalization from a different angle because I
think we're still optimizing those away too soon in some cases. So it's
possible that I can solve that one semi-accidentally.
Are there any other reports like that 1 that you are tracking?
On Mon, Feb 25, 2019 at 4:53 PM John Regehr via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
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
John Regehr via llvm-dev
2019-Feb-26 21:06 UTC
[llvm-dev] funnel shift, select, and poison
> 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=40768John