<div dir="ltr"><div dir="ltr"><div>If I got poison propagation right, it's probably only by luck! <br></div><div><br></div><div>Hopefully, the funnel shift bug is fixed here:</div><div><a href="https://reviews.llvm.org/rL354905" rel="noreferrer" target="_blank">https://reviews.llvm.org/rL354905</a></div><div><br></div><div>Nuno, IIUC this means that you do *not* need to change the funnel shift semantics in Alive. <br></div><div><br></div><div><div>So I think that means we're still on track to go with John's suggestion that only select and phi can block poison?</div><div>(I don't know of any objections to that proposal.) Either way, I agree that we should make it clearer in the LangRef. </div><div><br></div><div>We have this bug:<br></div></div><div><a href="https://bugs.llvm.org/show_bug.cgi?id=40768" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=40768</a></div><div>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. <br></div><div>Are there any other reports like that 1 that you are tracking?<br></div><div><br> </div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Feb 25, 2019 at 4:53 PM John Regehr via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</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">Great to see you've avoided the less-than-obvious pitfall of <br>
transforming funnel shift by not-constant into a shift!<br>
<br>
(Background for people not following this as closely: Unlike LLVM's <br>
regular shifts, the funnel shifts mask the shift exponent. This removes <br>
potential UBs but also introduces an impedance mismatch WRT shift.)<br>
<br>
John<br>
<br>
<br>
On 2/25/19 4:17 PM, Sanjay Patel wrote:<br>
> We have these transforms from funnel shift to a simpler shift op:<br>
> // 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>
> <br>
> These were part of: <a href="https://reviews.llvm.org/D54778" rel="noreferrer" target="_blank">https://reviews.llvm.org/D54778</a><br>
> <br>
> In all cases, one operand must be 0 or undef and the shift amount is a <br>
> constant, so I think these are safe. If X is poison, we'll transform <br>
> from a poisonous funnel shift to a poisonous shift (no need to introduce <br>
> any special poison blocking behavior).<br>
> <br>
> On Mon, Feb 25, 2019 at 4:01 PM Nuno Lopes <<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</a> <br>
> <mailto:<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</a>>> wrote:<br>
> <br>
> 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<br>
> funnel<br>
> shifts into other arithmetic operations when %x != %y. I think I saw<br>
> some<br>
> optimizations where fshl was being transformed into shl. This<br>
> 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)<br>
> gets<br>
> into trouble like funnel shift (two variables concatenated and<br>
> shifted by<br>
> some amount).<br>
> Eg, if in pseudo IR we have:<br>
> %funnel_shift = fshl %x, %y, %sh ; this is problematic because<br>
> 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><br>
> <mailto:<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,<br>
> ISD::SETEQ);<br>
> setValue(&I, DAG.getSelect(sdl, VT, IsZeroShift, IsFSHL ? X :<br>
> Y, Or));<br>
> <br>
> This is assuming select in SDAG stops poison in the same way we've<br>
> proposed<br>
> for the IR.<br>
> <br>
> However, the lowering has 2 optimizations. It can lower funnel<br>
> 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<br>
> 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<br>
> that block<br>
> poison. Exactly as you see here: if select blocks poison (and we<br>
> 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<br>
> because<br>
> it doesn't play well with 1) lowering to rotate, and 2) because it<br>
> blocks<br>
> optimizations like converting funnel shifts to plain shifts<br>
> 2) Introduce a flag in select, like we have nsw/nuw today that<br>
> changes the<br>
> semantics regarding poison. Essentially a select that doesn't stop<br>
> 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<br>
> optimization<br>
> below would only kick in when this flag is present. Of course then<br>
> 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<br>
> 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<br>
> 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<br>
> 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<br>
> (when the<br>
> shift amount is 0, we know that the output is exactly 1 of the<br>
> 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<br>
> potential<br>
> sidestep of the problem would be to limit that transform to a rotate<br>
> pattern<br>
> (single value is being shifted) rather than the more general funnel<br>
> 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> <mailto:<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>
> <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>
_______________________________________________<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>
</blockquote></div>