<div dir="ltr"><div dir="ltr">Don't we need to distinguish funnel shift from the more specific rotate?</div><div>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).</div><div>Eg, if in pseudo IR we have:</div><div>%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</div><div>%rotate = fshl %x, %x, %sh ; if x is poison, the op is unquestionably producing poison; there's no sh==0 loophole here<br></div><div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Feb 25, 2019 at 1:12 PM Nuno Lopes <<a href="mailto:nunoplopes@sapo.pt">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">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></div>