Sanjay Patel via llvm-dev
2019-Feb-25 16:29 UTC
[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190225/14c9adab/attachment.html>
John Regehr via llvm-dev
2019-Feb-25 17:15 UTC
[llvm-dev] funnel shift, select, and poison
Thanks for bringing this up Sanjay! I'd just like to add that the general question here is "where does poison stop propagating" and this question needs to be definitively answered by this community. The longer we put this off, the more incorrect transformations will accumulate. One answer might be "only select and phi stop poison" in which case this transformation is clearly invalid. Another answer might be "other instructions also stop poison, such as and 0, %in or the example below -- fsh by zero stops poison from its second argument" Maybe Nuno can chime in on this, but our general advice is that while this second answer is very appealing, because it lets us keep this nice transformation, it generally leads to trouble later by forbidding other transformations. John On 2/25/19 9:29 AM, Sanjay Patel via llvm-dev wrote:> 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 >
Krzysztof Parzyszek via llvm-dev
2019-Feb-25 17:29 UTC
[llvm-dev] funnel shift, select, and poison
On 2/25/2019 11:15 AM, John Regehr via llvm-dev wrote:> I'd just like to add that the general question here is "where does > poison stop propagating" and this question needs to be definitively > answered by this community.Does a call stop poison? Whatever the decision is may be contradicted after inlining, so what should such a call return? A superposition of poison and non-poison, until the function is inlined? It's a serious question. -Krzysztof
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
Sanjay Patel via llvm-dev
2019-Feb-25 22:30 UTC
[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/89674dc5/attachment.html>