funnel shift, select, and poison

Project Infrastructure LLVM Dev List Archives
#1

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

#2

Thanks for bringing this up Sanjay!

I'd just like to add that the general question here is "where does poison stop propagating" and this question needs to be definitively answered by this community. The longer we put this off, the more incorrect transformations will accumulate.

One answer might be "only select and phi stop poison" in which case this transformation is clearly invalid.

Another answer might be "other instructions also stop poison, such as

   and 0, %in

or the example below -- fsh by zero stops poison from its second argument"

Maybe Nuno can chime in on this, but our general advice is that while this second answer is very appealing, because it lets us keep this nice transformation, it generally leads to trouble later by forbidding other transformations.

John

#3

Does a call stop poison?

Whatever the decision is may be contradicted after inlining, so what should such a call return? A superposition of poison and non-poison, until the function is inlined? It's a serious question.

-Krzysztof

#4

Poison has to propagate through calls and loads/stores, or else basically nothing works.

John

#5

Consider this:

   %v0 = call i32 @foo(poison) nounwind/readnone
   store i32 %v0, i32* %valid_address

If we assume that poison propagates through calls, we could then optimize this to

   %v0 = poison
   store poison, i32* %valid_address

If we somehow realized that foo is

   define i32 @foo(i32) { ret i32 0 }

then the resulting code would be different.

-Krzysztof

#6

Consider this:

%v0 = call i32 @foo(poison) nounwind/readnone
store i32 %v0, i32* %valid_address

If we assume that poison propagates through calls, we could then optimize this to

%v0 = poison
store poison, i32* %valid_address

This is a sound transformation only if foo() returns poison when it is called with poison as an argument.

If this is what foo() looks like:

define i32 @foo(i32) { ret i32 0 }

then of course the transformation above is wrong.

John

#7

Then how do you interpret "poison has to propagate through calls"?

A typical analysis of a function will either see a call or the inlined body. If "call(poison)" cannot be assumed to be a poison, then a call effectively stops the propagation of a poison.

-Krzysztof

#8

A typical analysis of a function will either see a call or the inlined body. If "call(poison)" cannot be assumed to be a poison, then a call effectively stops the propagation of a poison.

Sorry that I was unclear.

What I am trying to say is that calls and returns (like loads and stores) are transparent with respect to poison.

It is definitely unsound to assume call(poison) == poison, because not every function returns a value that is poison-dependent on the function's arguments.

John

#9

It is definitely unsound to assume call(poison) == poison, because not every function returns a value that is poison-dependent on the function's arguments.

That's exactly the same as for a "select".

I'm in favor of a set of simple rules regarding the propagation of poison, so I lean towards the "one answer" you proposed in the first email, i.e.

> One answer might be "only select and phi stop poison"

except augmented to include calls and invokes.

-Krzysztof

#10

It is definitely unsound to assume call(poison) == poison, because not every function returns a value that is poison-dependent on the function's arguments.

That's exactly the same as for a "select".

But that is not what the LangRef says. It says that for purposes of poison: "Values other than phi nodes depend on their operands."

Most people, I think, would agree that select should not poison-depend on its not-selected operand. This is one of the things that needs to be clarified.

John

#11

I'm in favor of a set of simple rules regarding the propagation of poison, so I lean towards the "one answer" you proposed in the first email, i.e.

> One answer might be "only select and phi stop poison"

except augmented to include calls and invokes.

This is already explicit and clear in the LangRef:

- Function arguments depend on the corresponding actual argument values in the dynamic callers of their functions.

- Call instructions depend on the ret instructions that dynamically transfer control back to them.

- Invoke instructions depend on the ret, resume, or exception-throwing call instructions that dynamically transfer control back to them.

See https://llvm.org/docs/LangRef.html#poison-values

John

#12

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 :slight_smile:

Nuno

#13

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:
%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
%rotate = fshl %x, %x, %sh ; if x is poison, the op is unquestionably producing poison; there’s no sh==0 loophole here

#14

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

#15

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).

#16

Great to see you've avoided the less-than-obvious pitfall of transforming funnel shift by not-constant into a shift!

(Background for people not following this as closely: Unlike LLVM's regular shifts, the funnel shifts mask the shift exponent. This removes potential UBs but also introduces an impedance mismatch WRT shift.)

John

#17

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@rotateright.com>:

#18

If I got poison propagation right, it’s probably only by luck!

Hopefully, the funnel shift bug is fixed here:
https://reviews.llvm.org/rL354905

Nuno, IIUC this means that you do not need to change the funnel shift semantics in Alive.

So I think that means we’re still on track to go with John’s suggestion that only select and phi can block poison?
(I don’t know of any objections to that proposal.) Either way, I agree that we should make it clearer in the LangRef.

We have this bug:

https://bugs.llvm.org/show_bug.cgi?id=40768
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.

Are there any other reports like that 1 that you are tracking?

#19

That patch fixes things, yes, thank you! The poison semantics is now non-blocking and all funnel shif tests in LLVM pass Alive's verification.

Regarding select, we haven't filled other bug reports other than the one you mentioned IIRC.
I see a few failures in the test suite, e.g.:

Transforms/InstCombine/select.ll

#20

Transforms/InstCombine/select.ll

define i1 @trueval_is_true(i1 %C, i1 %X) {
%R = select i1 %C, i1 1, i1 %X
ret i1 %R
}
=>
define i1 @trueval_is_true(i1 %C, i1 %X) {
%R = or i1 %C, %X
ret i1 %R
}
ERROR: Target is more poisonous than source (when %C = #x1 & %X = poison)

(there are many variations of these select->arithmetic transformations)

This particular little family of transformations can be reliably done by all of the backends I looked at, so disabling them at the IR level should be OK. See a bit more discussion here:

https://bugs.llvm.org/show_bug.cgi?id=40768

John