[InstSimplify] remove shift that is redundant with part of funnel shift

[spatel]

Summary

In D111530, I suggested that we add some relatively basic pattern-matching folds for shifts and funnel shifts and avoid a more specialized solution if possible.

We can start by implementing at least one of these in IR because it's easier to write the code and verify with Alive2:
https://alive2.llvm.org/ce/z/qHpmNn

This will need to be adapted/extended for SDAG to handle the motivating bug because the patterns only appear later with that example (added some tests: bb850d422b64)

This can be extended within InstSimplify to handle cases where we 'and' with a shift too (in that case, kill the funnel shift).
We could also handle patterns where the shift and funnel shift directions are inverted, but I think it's better to canonicalize that instead to avoid pattern-match case explosion.

[RKSimon]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

if ((match(Op0, m_Shl(m_AllOnes(), m_Value(X))) &&
     const APInt *C;
     if ((match(X, m_Sub(m_APInt(C), m_Specific(Y))) ||
          match(Y, m_Sub(m_APInt(C), m_Specific(X)))) &&
         C->ule(X->getType()->getScalarSizeInBits())) {
       return ConstantInt::getAllOnesValue(X->getType());
     }
   }
 
+  // A funnel shift (rotate) can be decomposed into simpler shifts. See if we
+  // are mixing in another shift that is redundant with the funnel shift.
+
+  // (fshl X, ?, Y) | (shl X, Y) --> fshl X, ?, Y
+  // (shl X, Y) | (fshl X, ?, Y) --> fshl X, ?, Y
+  if (match(Op0,
+            m_Intrinsic<Intrinsic::fshl>(m_Value(X), m_Value(), m_Value(Y))) &&
+      match(Op1, m_Shl(m_Specific(X), m_Specific(Y))))
+    return Op0;
+  if (match(Op1,
+            m_Intrinsic<Intrinsic::fshl>(m_Value(X), m_Value(), m_Value(Y))) &&
+      match(Op0, m_Shl(m_Specific(X), m_Specific(Y))))
+    return Op1;
+
+  // (fshr ?, X, Y) | (lshr X, Y) --> fshr ?, X, Y
+  // (lshr X, Y) | (fshr ?, X, Y) --> fshr ?, X, Y
+  if (match(Op0,
+            m_Intrinsic<Intrinsic::fshr>(m_Value(), m_Value(X), m_Value(Y))) &&
+      match(Op1, m_LShr(m_Specific(X), m_Specific(Y))))
+    return Op0;
+  if (match(Op1,
+            m_Intrinsic<Intrinsic::fshr>(m_Value(), m_Value(X), m_Value(Y))) &&
+      match(Op0, m_LShr(m_Specific(X), m_Specific(Y))))
+    return Op1;
+
   if (Value *V = simplifyAndOrOfCmps(Q, Op0, Op1, false))
     return V;
 
   // If we have a multiplication overflow check that is being 'and'ed with a
   // check that one of the multipliers is not zero, we can omit the 'and', and
   // only keep the overflow check.
   if (isCheckForZeroAndMulWithOverflow(Op0, Op1, false))
     return Op1;

llvm/test/Transforms/InstSimplify/or.ll

;
   ret <2 x i4> %or
 }
 
 declare i32 @llvm.fshl.i32 (i32, i32, i32)
 declare i32 @llvm.fshr.i32 (i32, i32, i32)
 
 define i32 @or_shl_fshl(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_shl_fshl(
-; CHECK-NEXT:    [[SHY:%.*]] = shl i32 [[Y:%.*]], [[S:%.*]]
-; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshl.i32(i32 [[Y]], i32 [[X:%.*]], i32 [[S]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[FUN]], [[SHY]]
-; CHECK-NEXT:    ret i32 [[OR]]
+; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshl.i32(i32 [[Y:%.*]], i32 [[X:%.*]], i32 [[S:%.*]])
+; CHECK-NEXT:    ret i32 [[FUN]]
 ;
   %shy = shl i32 %y, %s
   %fun = call i32 @llvm.fshl.i32(i32 %y, i32 %x, i32 %s)
   %or = or i32 %fun, %shy
   ret i32 %or
 }
 
 define i32 @or_shl_fshl_commute(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_shl_fshl_commute(
-; CHECK-NEXT:    [[SHY:%.*]] = shl i32 [[Y:%.*]], [[S:%.*]]
-; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshl.i32(i32 [[Y]], i32 [[X:%.*]], i32 [[S]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHY]], [[FUN]]
-; CHECK-NEXT:    ret i32 [[OR]]
+; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshl.i32(i32 [[Y:%.*]], i32 [[X:%.*]], i32 [[S:%.*]])
+; CHECK-NEXT:    ret i32 [[FUN]]
 ;
   %shy = shl i32 %y, %s
   %fun = call i32 @llvm.fshl.i32(i32 %y, i32 %x, i32 %s)
   %or = or i32 %shy, %fun
   ret i32 %or
 }
 
+; negative test - fshl operands are not commutative
+
 define i32 @or_shl_fshl_wrong_order(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_shl_fshl_wrong_order(
 ; CHECK-NEXT:    [[SHY:%.*]] = shl i32 [[Y:%.*]], [[S:%.*]]
 ; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y]], i32 [[S]])
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[FUN]], [[SHY]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %shy = shl i32 %y, %s
   %fun = call i32 @llvm.fshl.i32(i32 %x, i32 %y, i32 %s)
   %or = or i32 %fun, %shy
   ret i32 %or
 }
 
 define i32 @or_lshr_fshr(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_lshr_fshr(
-; CHECK-NEXT:    [[SHY:%.*]] = lshr i32 [[Y:%.*]], [[S:%.*]]
-; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshr.i32(i32 [[X:%.*]], i32 [[Y]], i32 [[S]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[FUN]], [[SHY]]
-; CHECK-NEXT:    ret i32 [[OR]]
+; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshr.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[S:%.*]])
+; CHECK-NEXT:    ret i32 [[FUN]]
 ;
   %shy = lshr i32 %y, %s
   %fun = call i32 @llvm.fshr.i32(i32 %x, i32 %y, i32 %s)
   %or = or i32 %fun, %shy
   ret i32 %or
 }
 
 define i32 @or_lshr_fshr_commute(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_lshr_fshr_commute(
-; CHECK-NEXT:    [[SHY:%.*]] = lshr i32 [[Y:%.*]], [[S:%.*]]
-; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshr.i32(i32 [[X:%.*]], i32 [[Y]], i32 [[S]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHY]], [[FUN]]
-; CHECK-NEXT:    ret i32 [[OR]]
+; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshr.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 [[S:%.*]])
+; CHECK-NEXT:    ret i32 [[FUN]]
 ;
   %shy = lshr i32 %y, %s
   %fun = call i32 @llvm.fshr.i32(i32 %x, i32 %y, i32 %s)
   %or = or i32 %shy, %fun
   ret i32 %or
 }
 
+; negative test - fshr operands are not commutative
+
 define i32 @or_lshr_fshr_wrong_order(i32 %x, i32 %y, i32 %s) {
 ; CHECK-LABEL: @or_lshr_fshr_wrong_order(
 ; CHECK-NEXT:    [[SHY:%.*]] = lshr i32 [[Y:%.*]], [[S:%.*]]
 ; CHECK-NEXT:    [[FUN:%.*]] = call i32 @llvm.fshr.i32(i32 [[Y]], i32 [[X:%.*]], i32 [[S]])
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[FUN]], [[SHY]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %shy = lshr i32 %y, %s
   %fun = call i32 @llvm.fshr.i32(i32 %y, i32 %x, i32 %s)
   %or = or i32 %fun, %shy
   ret i32 %or
 }