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