InstCombine] fold mul with decremented "shl -1" factor (2nd try)

[spatel]

Summary

This is a hopefully corrected version of:
bc886e9b587b

I thought the patch was obvious enough to not require pre-commit review the first time, but I made a copy-paste error that created an "add" instead of the intended "sub". The regression tests showed the bug, but I overlooked that too (embarrassing).

So this time, I'm posting for review in case someone (or bots) would like to apply the patch and confirm that the previous errors (there were several independent reports) are no longer there. As I said in a comment on issue #58717, the bug reports confirm that the pattern does occur in many real-world applications, so hopefully, eliminating the multiply results in better code.

I added one more regression test in this version of the patch, and here's an Alive2 proof to show that exact example:
https://alive2.llvm.org/ce/z/dge7VC

Original commit message:

This is a sibling to:
6064e92b0a84
...but we canonicalize the shl+add to shl+xor,
so the pattern is different than I expected:
https://alive2.llvm.org/ce/z/8CX16e

I have not found any patterns that are safe
to propagate no-wrap, so that is not included
here.

[mstorsjo]

Thanks! My testscases seem to run fine with this version of the patch.

(Note, the patch doesn't seem to apply entirely cleanly on current git main; the last hunk of the testcase seems to fail to apply here.)

[spatel]

In D137157#3898971, @mstorsjo wrote:

Thanks! My testscases seem to run fine with this version of the patch.

Great! - thank you for checking.

(Note, the patch doesn't seem to apply entirely cleanly on current git main; the last hunk of the testcase seems to fail to apply here.)

Ah - I had not pushed the new test up to main. Should be clean after:
087e721dd8a7

[glandium]

FWIW, I tested replacing CreateAdd with CreateSub on the original commit yesterday, and it fixed the issues I had.

[chapuni]

I have reconfirmed this fine to build.
(who could approve this?)

[spatel]

Thanks all for the extra testing! I'll re-land the corrected patch.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(-1.0),
     IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
     Builder.setFastMathFlags(I.getFastMathFlags());
     return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
   }
 
   return nullptr;
 }
 
-/// Reduce integer multiplication patterns that contain a (1 << Z) factor.
+/// Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
 /// Callers are expected to call this twice to handle commuted patterns.
 static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
                           InstCombiner::BuilderTy &Builder) {
   Value *X = Mul.getOperand(0), *Y = Mul.getOperand(1);
   if (CommuteOperands)
     std::swap(X, Y);
 
   const bool HasNSW = Mul.hasNoSignedWrap();
static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
   if (match(Y, m_OneUse(m_Add(m_BinOp(Shift), m_One()))) &&
       match(Shift, m_OneUse(m_Shl(m_One(), m_Value(Z))))) {
     bool PropagateNSW = HasNSW && Shift->hasNoSignedWrap();
     Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr");
     Value *Shl = Builder.CreateShl(FrX, Z, "mulshl", HasNUW, PropagateNSW);
     return Builder.CreateAdd(Shl, FrX, Mul.getName(), HasNUW, PropagateNSW);
   }
 
+  // Similar to above, but a decrement of the shifted value is disguised as
+  // 'not' and becomes a sub:
+  // X * (~(-1 << Z)) --> X * ((1 << Z) - 1) --> (X << Z) - X
+  // This increases uses of X, so it may require a freeze, but that is still
+  // expected to be an improvement because it removes the multiply.
+  if (match(Y, m_OneUse(m_Not(m_OneUse(m_Shl(m_AllOnes(), m_Value(Z))))))) {
+    Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr");
+    Value *Shl = Builder.CreateShl(FrX, Z, "mulshl");
+    return Builder.CreateSub(Shl, FrX, Mul.getName());
+  }
+
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   if (Value *V = simplifyMulInst(Op0, Op1, SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 

llvm/test/Transforms/InstCombine/mul.ll

 ;
   %pow2x = shl i32 1, %x
   call void @use32(i32 %pow2x)
   %x1 = add i32 %pow2x, 1
   %m = mul i32 %x1, %y
   ret i32 %m
 }
 
+; ((-1 << x) ^ -1) * y --> (y << x) - y
+
 define i8 @shl1_decrement(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl1_decrement(
-; CHECK-NEXT:    [[POW2X:%.*]] = shl i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[X1:%.*]] = xor i8 [[POW2X]], -1
-; CHECK-NEXT:    [[M:%.*]] = mul i8 [[X1]], [[Y:%.*]]
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i8 [[Y:%.*]]
+; CHECK-NEXT:    [[MULSHL:%.*]] = shl i8 [[Y_FR]], [[X:%.*]]
+; CHECK-NEXT:    [[M1:%.*]] = sub i8 [[MULSHL]], [[Y_FR]]
+; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %pow2x = shl i8 -1, %x
   %x1 = xor i8 %pow2x, -1
   %m = mul i8 %x1, %y
   ret i8 %m
 }
 
 define i8 @shl1_decrement_commute(i8 %x, i8 noundef %p) {
 ; CHECK-LABEL: @shl1_decrement_commute(
 ; CHECK-NEXT:    [[Y:%.*]] = ashr i8 [[P:%.*]], 1
-; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[X1:%.*]] = xor i8 [[NOTMASK]], -1
-; CHECK-NEXT:    [[M:%.*]] = mul i8 [[Y]], [[X1]]
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    [[MULSHL:%.*]] = shl i8 [[Y]], [[X:%.*]]
+; CHECK-NEXT:    [[M1:%.*]] = sub i8 [[MULSHL]], [[Y]]
+; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %y = ashr i8 %p, 1 ; thwart complexity-based canonicalization
   %pow2x = shl i8 1, %x
   %x1 = add i8 %pow2x, -1
   %m = mul i8 %y, %x1
   ret i8 %m
 }
 
 define i8 @shl1_nuw_decrement(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl1_nuw_decrement(
-; CHECK-NEXT:    [[POW2X:%.*]] = shl i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[X1:%.*]] = xor i8 [[POW2X]], -1
-; CHECK-NEXT:    [[M:%.*]] = mul nuw i8 [[X1]], [[Y:%.*]]
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i8 [[Y:%.*]]
+; CHECK-NEXT:    [[MULSHL:%.*]] = shl i8 [[Y_FR]], [[X:%.*]]
+; CHECK-NEXT:    [[M1:%.*]] = sub i8 [[MULSHL]], [[Y_FR]]
+; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %pow2x = shl i8 -1, %x
   %x1 = xor i8 %pow2x, -1
   %m = mul nuw i8 %x1, %y
   ret i8 %m
 }
 
 define i8 @shl1_nsw_decrement(i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl1_nsw_decrement(
-; CHECK-NEXT:    [[POW2X:%.*]] = shl nsw i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[X1:%.*]] = xor i8 [[POW2X]], -1
-; CHECK-NEXT:    [[M:%.*]] = mul nsw i8 [[X1]], [[Y:%.*]]
-; CHECK-NEXT:    ret i8 [[M]]
+; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i8 [[Y:%.*]]
+; CHECK-NEXT:    [[MULSHL:%.*]] = shl i8 [[Y_FR]], [[X:%.*]]
+; CHECK-NEXT:    [[M1:%.*]] = sub i8 [[MULSHL]], [[Y_FR]]
+; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %pow2x = shl nsw i8 -1, %x
   %x1 = xor i8 %pow2x, -1
   %m = mul nsw i8 %x1, %y
   ret i8 %m
 }
 
+; negative test - extra use would require more instructions
+
 define i32 @shl1_decrement_use(i32 %x, i32 %y) {
 ; CHECK-LABEL: @shl1_decrement_use(
 ; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[X:%.*]]
 ; CHECK-NEXT:    [[X1:%.*]] = xor i32 [[NOTMASK]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[X1]])
 ; CHECK-NEXT:    [[M:%.*]] = mul i32 [[X1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[M]]
 ;
   %pow2x = shl i32 1, %x
   %x1 = add i32 %pow2x, -1
   call void @use32(i32 %x1)
   %m = mul i32 %x1, %y
   ret i32 %m
 }
 
+; the fold works for vectors too and if 'y' is a constant, sub becomes add
+
 define <2 x i8> @shl1_decrement_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @shl1_decrement_vec(
-; CHECK-NEXT:    [[POW2X:%.*]] = shl <2 x i8> <i8 -1, i8 -1>, [[X:%.*]]
-; CHECK-NEXT:    [[X1:%.*]] = xor <2 x i8> [[POW2X]], <i8 -1, i8 -1>
-; CHECK-NEXT:    [[M:%.*]] = mul <2 x i8> [[X1]], <i8 42, i8 -3>
-; CHECK-NEXT:    ret <2 x i8> [[M]]
+; CHECK-NEXT:    [[MULSHL:%.*]] = shl <2 x i8> <i8 42, i8 -3>, [[X:%.*]]
+; CHECK-NEXT:    [[M1:%.*]] = add <2 x i8> [[MULSHL]], <i8 -42, i8 3>
+; CHECK-NEXT:    ret <2 x i8> [[M1]]
 ;
   %pow2x = shl <2 x i8> <i8 -1, i8 -1>, %x
   %x1 = xor <2 x i8> %pow2x, <i8 -1, i8 -1>
   %m = mul <2 x i8> %x1, <i8 42, i8 -3>
   ret <2 x i8> %m
 }
 
 ; X * Y (when Y is a boolean) --> Y ? X : 0