[InstCombine] try to fold 'or' into 'mul' operand

[spatel]

Summary

or (mul X, Y), X --> mul X, (add Y, 1) (when the multiply has no common bits with X)

We already have this fold if the pattern ends in 'add', but we can miss it if the 'add' becomes 'or' via another no-common-bits transform.

This is part of fixing:
http://llvm.org/PR49055
...but it won't make a difference on that example yet.

https://alive2.llvm.org/ce/z/Vrmoeb

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2642

2644

Why APInt? This should probably be ImmConstant,
though i would think that if mul is one-use, reducing use count on X may be worthwhile still.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2644

Yes, reducing uses of X does look better. And the 'add' version of this does that already, so it will be symmetric.

[spatel]

Patch updated:
Removed constant restriction on the pattern - any value can be folded into an add+mul pair (and that was already shown correct in the Alive2 link).

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2645

But if mul is not one-use yet the y is an immediate, don't we still want to fold?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2645

That's not clearly better IMO. It reduces the computation chain, but we'd be replacing an 'or' with a 'mul'. That could regress codegen (especially for targets/types where the mul is not supported), and the backend can't undo that currently.

This case is shown as the 1st negative test in the patch. These are the options:

%m = mul i32 %x, 24
call void @use(i32 %m)
%r = or i32 %m, %x

vs.

%m = mul i32 %x, 24
call void @use(i32 %m)
%r = mul i32 %x, 25

[lebedev.ri]

LG, thank you.

llvm/test/Transforms/InstCombine/or.ll

1445

Please duplicate this test with an extra use on the multiply, to complement the @mul_no_common_bits_uses.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
   if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
       !CV->isAllOnes() && MaskedValueIsZero(Y, *CV, 0, &I)) {
     // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
     // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
     Value *Or = Builder.CreateOr(X, Y);
     return BinaryOperator::CreateXor(Or, ConstantInt::get(Ty, *CV));
   }
 
+  // If the operands have no common bits set:
+  // or (mul X, Y), X --> add (mul X, Y), X --> mul X, (Y + 1)
+  if (match(&I,
+            m_c_Or(m_OneUse(m_Mul(m_Value(X), m_Value(Y))), m_Deferred(X))) &&
+      haveNoCommonBitsSet(Op0, Op1, DL)) {
+    Value *IncrementY = Builder.CreateAdd(Y, ConstantInt::get(Ty, 1));
+    return BinaryOperator::CreateMul(X, IncrementY);
+  }
+
   // (A & C) | (B & D)
   Value *A, *B, *C, *D;
   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
       match(Op1, m_And(m_Value(B), m_Value(D)))) {
 
     // (A & C0) | (B & C1)
     const APInt *C0, *C1;
     if (match(C, m_APInt(C0)) && match(D, m_APInt(C1))) {

llvm/test/Transforms/InstCombine/or.ll

 ;
   %isneg = icmp slt <2 x i5> %x, zeroinitializer
   %negx = sub <2 x i5> zeroinitializer, %x
   %isnotneg = icmp sgt <2 x i5> %negx, <i5 -1, i5 -1>
   %r = or <2 x i1> %isneg, %isnotneg
   ret <2 x i1> %r
 }
 
 define i32 @mul_no_common_bits(i32 %p1, i32 %p2) {
 ; CHECK-LABEL: @mul_no_common_bits(
 ; CHECK-NEXT:    [[X:%.*]] = and i32 [[P1:%.*]], 7
 ; CHECK-NEXT:    [[Y:%.*]] = shl i32 [[P2:%.*]], 3
-; CHECK-NEXT:    [[M:%.*]] = mul i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[M]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[Y]], 1
+; CHECK-NEXT:    [[R:%.*]] = mul i32 [[X]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %x = and i32 %p1, 7
   %y = shl i32 %p2, 3
   %m = mul i32 %x, %y
   %r = or i32 %m, %x
   ret i32 %r
 }
 
 define i32 @mul_no_common_bits_const_op(i32 %p) {
 ; CHECK-LABEL: @mul_no_common_bits_const_op(
 ; CHECK-NEXT:    [[X:%.*]] = and i32 [[P:%.*]], 7
-; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i32 [[X]], 24
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[M]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw i32 [[X]], 25
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %x = and i32 %p, 7
   %m = mul i32 %x, 24
   %r = or i32 %m, %x
   ret i32 %r
 }
 
 define <2 x i12> @mul_no_common_bits_commute(<2 x i12> %p) {
 ; CHECK-LABEL: @mul_no_common_bits_commute(
 ; CHECK-NEXT:    [[X:%.*]] = and <2 x i12> [[P:%.*]], <i12 1, i12 1>
-; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw <2 x i12> [[X]], <i12 14, i12 16>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i12> [[X]], [[M]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw <2 x i12> [[X]], <i12 15, i12 17>
 ; CHECK-NEXT:    ret <2 x i12> [[R]]
 ;
   %x = and <2 x i12> %p, <i12 1, i12 1>
   %m = mul <2 x i12> %x, <i12 14, i12 16>
   %r = or <2 x i12> %x, %m
   ret <2 x i12> %r
 }
 
-define i32 @mul_no_common_bits_uses(i32 %p) {
+; negative test - extra use requires extra instructions
+
+define i32 @mul_no_common_bits_uses(i32 %p1, i32 %p2) {
 ; CHECK-LABEL: @mul_no_common_bits_uses(
+; CHECK-NEXT:    [[X:%.*]] = and i32 [[P1:%.*]], 7
+; CHECK-NEXT:    [[Y:%.*]] = shl i32 [[P2:%.*]], 3
+; CHECK-NEXT:    [[M:%.*]] = mul i32 [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i32 [[M]])
+; CHECK-NEXT:    [[R:%.*]] = or i32 [[M]], [[X]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %x = and i32 %p1, 7
+  %y = shl i32 %p2, 3
+  %m = mul i32 %x, %y
+  call void @use(i32 %m)
+  %r = or i32 %m, %x
+  ret i32 %r
+}
+
+; negative test - probably not good to create an extra mul
+
+define i32 @mul_no_common_bits_const_op_uses(i32 %p) {
+; CHECK-LABEL: @mul_no_common_bits_const_op_uses(
 ; CHECK-NEXT:    [[X:%.*]] = and i32 [[P:%.*]], 7
 ; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i32 [[X]], 24
 ; CHECK-NEXT:    call void @use(i32 [[M]])
 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[M]], [[X]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %x = and i32 %p, 7
   %m = mul i32 %x, 24
   call void @use(i32 %m)
   %r = or i32 %m, %x
   ret i32 %r
 }
 
+; negative test - %x and %m may have set 3rd bit
+
 define i32 @mul_common_bits(i32 %p) {
 ; CHECK-LABEL: @mul_common_bits(
 ; CHECK-NEXT:    [[X:%.*]] = and i32 [[P:%.*]], 7
 ; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i32 [[X]], 12
 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[M]], [[X]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %x = and i32 %p, 7
   %m = mul i32 %x, 12
   %r = or i32 %m, %x
   ret i32 %r
 }