[llvm-dev] funnel shift, select, and poison

[Nuno Lopes via llvm-dev]

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