[llvm-dev] funnel shift, select, and poison (original) (raw)

Nuno Lopes via llvm-dev llvm-dev at lists.llvm.org
Tue Feb 26 03:48:38 PST 2019

Ok, sounds good. I'm convinced. I'll change the semantics in Alive to block poison when
shift_amount % bits == 0. LangRef should probably be updated as well.

Thanks, Nuno

Quoting Sanjay Patel <spatel at rotateright.com>:

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> 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: %funnelshift = 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#discussionr257528880 Example: define i8 @fshlzeroshiftguard(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 @fshlzeroshiftguard(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/showbug.cgi?id=34924

LLVM Developers mailing list llvm-dev at lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

More information about the llvm-dev mailing list