[InstCombine] matchFunnelShift - support non-uniform constant vector shift amounts (PR46895)

[RKSimon]

Summary

Complete PR46895 by refactoring D87452/D88402 to allow us to match non-uniform constant values.

[nikic]

To handle the various undef cases this ended up being a lot bulkier than I hoped - I'd love to hear if anyone has any suggestions on how we could use ConstantExpr/PatternMatch to simplify this as I imagine we could use such functionality in other places as we improve non-uniform vector support.

Would something along the lines of ConstantExpr::getAdd(LC, RC) and then matching the result against a Width splat work? As C + undef already gets folded to undef.

[RKSimon]

I did wonder if a ConstantExpr::isUndef() help could be added to return a bool/vectorbool that could be then used to select the 'matching' values (e.g. undef + 1 -> 31 + 1 for i32 rotate).

[RKSimon]

I've removed the undef handling from this patch - we can revisit that later once we have a better idea of how to achieve it (see D88687).

[lebedev.ri]

LGTM

[saugustine]

It is a miscompile--or, at least a fingerprint is being miscomputed. The failure check is here:

https://boringssl.googlesource.com/boringssl/+/refs/heads/master/crypto/hrss/hrss_test.cc#165

But that is obviously somewhat removed from where things actually went wrong, which is what I'm (rather slowly, unfortunately) trying to figure out.

[lebedev.ri]

In D88420#2335173, @saugustine wrote:

It is a miscompile--or, at least a fingerprint is being miscomputed. The failure check is here:

https://boringssl.googlesource.com/boringssl/+/refs/heads/master/crypto/hrss/hrss_test.cc#165

But that is obviously somewhat removed from where things actually went wrong, which is what I'm (rather slowly, unfortunately) trying to figure out.

I think there were some related fixes afterwards. Is the issue still present in master?

[MaskRay]

In D88420#2335176, @lebedev.ri wrote:

In D88420#2335173, @saugustine wrote:

It is a miscompile--or, at least a fingerprint is being miscomputed. The failure check is here:

https://boringssl.googlesource.com/boringssl/+/refs/heads/master/crypto/hrss/hrss_test.cc#165

But that is obviously somewhat removed from where things actually went wrong, which is what I'm (rather slowly, unfortunately) trying to figure out.

I think there were some related fixes afterwards. Is the issue still present in master?

The powerpc64le issue is still present as of 51ff04567b2f8d06b2062bd3ed72eab2e93e4466.

Adding @nemanjai in case he can find anything obvious from this commit or D88834

[saugustine]

Here is a relatively simple, self-contained testcase. Of interest is that the entire loop needs to be present, and completely unwound for this bug to show. It looks to me like either next_carry or carry is mis-calculated or stale on the ninth iteration which fills the second-to-last element.

Failed
    Correct          Actual
 0: c71c71c71c71c9fc   c71c71c71c71c9fc
 1: 5b91f6e791f6e791   5b91f6e791f6e791
 2: 6000000000000005   6000000000000005
 3: 9e79e79e79e79ed8   9e79e79e79e79ed8
 4: 4bf2c78af2c7816e   4bf2c78af2c7816e
 5: a53d3d3d3d3d3d3d   a53d3d3d3d3d3d3d
 6: 7555555555555558   7555555555555558
 7: cf3cf3cf3cf3cfcd   cf3cf3cf3cf3cfcd
 8: d3cfa5effb5effcf   d3cfa5effb5effcf
 9: 0000000000000000   0000000000000001
10: 0000000000000000   0000000000000000

ppc_shift_test.c1 KBDownload

[saugustine]

Filed https://bugs.llvm.org/show_bug.cgi?id=47891 to continue discussion.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Instruction *matchFunnelShift(Instruction &Or) {
   BinaryOperator::BinaryOps ShiftOpcode1 = Or1->getOpcode();
   if (ShiftOpcode0 == ShiftOpcode1)
     return nullptr;
 
   // Match the shift amount operands for a funnel shift pattern. This always
   // matches a subtraction on the R operand.
   auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
     // Check for constant shift amounts that sum to the bitwidth.
-    // TODO: Support non-uniform shift amounts.
-    const APInt *LC, *RC;
-    if (match(L, m_APIntAllowUndef(LC)) && match(R, m_APIntAllowUndef(RC)))
-      if (LC->ult(Width) && RC->ult(Width) && (*LC + *RC) == Width)
-        return ConstantInt::get(L->getType(), *LC);
+    const APInt *LI, *RI;
+    if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
+      if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
+        return ConstantInt::get(L->getType(), *LI);
+
+    // TODO: Support undefs in non-uniform shift amounts.
+    Constant *LC, *RC;
+    if (match(L, m_Constant(LC)) && !LC->containsUndefElement() &&
+        match(R, m_Constant(RC)) && !RC->containsUndefElement() &&
+        match(L, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, APInt(Width, Width))) &&
+        match(R, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, APInt(Width, Width)))) {
+      if (match(ConstantExpr::getAdd(LC, RC), m_SpecificInt(Width)))
+        return L;
+    }
 
     // For non-constant cases, the following patterns currently only work for
     // rotation patterns.
     // TODO: Add general funnel-shift compatible patterns.
     if (ShVal0 != ShVal1)
       return nullptr;
 
     // For non-constant cases we don't support non-pow2 shift masks.

llvm/test/Transforms/InstCombine/funnel.ll

 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shr = lshr <2 x i17> %x, <i17 12, i17 undef>
   %shl = shl <2 x i17> %y, <i17 5, i17 undef>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }
 
-; TODO: Allow arbitrary shift constants.
+; Allow arbitrary shift constants.
+; TODO: Support undef elements.
 
 define <2 x i32> @fshr_v2i32_constant_nonsplat(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @fshr_v2i32_constant_nonsplat(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 17, i32 19>
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> [[Y:%.*]], <i32 15, i32 13>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i32> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> [[Y:%.*]], <2 x i32> [[X:%.*]], <2 x i32> <i32 15, i32 13>)
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;
   %shr = lshr <2 x i32> %x, <i32 17, i32 19>
   %shl = shl <2 x i32> %y, <i32 15, i32 13>
   %r = or <2 x i32> %shl, %shr
   ret <2 x i32> %r
 }
 
;
   %shr = lshr <2 x i32> %x, <i32 17, i32 19>
   %shl = shl <2 x i32> %y, <i32 15, i32 undef>
   %r = or <2 x i32> %shl, %shr
   ret <2 x i32> %r
 }
 
 define <2 x i36> @fshl_v2i36_constant_nonsplat(<2 x i36> %x, <2 x i36> %y) {
 ; CHECK-LABEL: @fshl_v2i36_constant_nonsplat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i36> [[X:%.*]], <i36 21, i36 11>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i36> [[Y:%.*]], <i36 15, i36 25>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i36> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i36> @llvm.fshl.v2i36(<2 x i36> [[X:%.*]], <2 x i36> [[Y:%.*]], <2 x i36> <i36 21, i36 11>)
 ; CHECK-NEXT:    ret <2 x i36> [[R]]
 ;
   %shl = shl <2 x i36> %x, <i36 21, i36 11>
   %shr = lshr <2 x i36> %y, <i36 15, i36 25>
   %r = or <2 x i36> %shl, %shr
   ret <2 x i36> %r
 }
 

llvm/test/Transforms/InstCombine/rotate.ll

 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shl = shl <2 x i17> %x, <i17 12, i17 undef>
   %shr = lshr <2 x i17> %x, <i17 5, i17 undef>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }
 
-; TODO: Allow arbitrary shift constants.
+; Allow arbitrary shift constants.
+; TODO: Support undef elements.
 
 define <2 x i32> @rotr_v2i32_constant_nonsplat(<2 x i32> %x) {
 ; CHECK-LABEL: @rotr_v2i32_constant_nonsplat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> [[X:%.*]], <i32 17, i32 19>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i32> [[X]], <i32 15, i32 13>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i32> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> [[X:%.*]], <2 x i32> [[X]], <2 x i32> <i32 17, i32 19>)
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;
   %shl = shl <2 x i32> %x, <i32 17, i32 19>
   %shr = lshr <2 x i32> %x, <i32 15, i32 13>
   %r = or <2 x i32> %shl, %shr
   ret <2 x i32> %r
 }
 
;
   %shl = shl <2 x i32> %x, <i32 17, i32 19>
   %shr = lshr <2 x i32> %x, <i32 15, i32 undef>
   %r = or <2 x i32> %shl, %shr
   ret <2 x i32> %r
 }
 
 define <2 x i36> @rotl_v2i36_constant_nonsplat(<2 x i36> %x) {
 ; CHECK-LABEL: @rotl_v2i36_constant_nonsplat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i36> [[X:%.*]], <i36 21, i36 11>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i36> [[X]], <i36 15, i36 25>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i36> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i36> @llvm.fshl.v2i36(<2 x i36> [[X:%.*]], <2 x i36> [[X]], <2 x i36> <i36 21, i36 11>)
 ; CHECK-NEXT:    ret <2 x i36> [[R]]
 ;
   %shl = shl <2 x i36> %x, <i36 21, i36 11>
   %shr = lshr <2 x i36> %x, <i36 15, i36 25>
   %r = or <2 x i36> %shl, %shr
   ret <2 x i36> %r
 }