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

[John Regehr via llvm-dev]

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




On 2/25/19 9:29 AM, Sanjay Patel via llvm-dev wrote:
> 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
>