[InstCombine] enable more factorization in SimplifyUsingDistributiveLaws

[Allen]

Summary

This is one of the IR transforms suggested in issue #57255.
https://godbolt.org/z/P9rMGhTcE.
Now we already support to transform t*5 + t into t * (5+1), but not for t - 1 + 5 * t
so the patch try logic: (t-1)+(5*t) -> (t*5)+(t-1) -> (t*5+t)-1 = t*(5+1)-1

Depend D132412

[xbolva00]

Please add more tests

[Allen]

Add 4 more tests according comment

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

759

Make formatting changes independently of this patch or just leave it unchanged.

775

It seems odd for this function to specify the exact opcode. Everything else is generalized based on association and distribution laws. Is mul really the only opcode where this transform works?

780

Use plain `cast' if we don't use the return value. Alternatively, give it a name and use it:

if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I)) {
  cast<Instruction>(New)->setHasNoSignedWrap(OBO.hasNoSignedWrap())

How did we guarantee that "New" is an OBO instruction?

If it is safe to propagate no-wrap like this, then we need tests and Alive2 proofs to show it.

787–788

Is this change independent of the one above? If so, we should have separate patches and tests, so it is clear what this does.

llvm/test/Transforms/InstCombine/add4.ll

131

(x + (-1)) + (x * 5) --> (x * 6) + (-1)

144

(x * 4) + (x - 1) --> (x * 5) + (-1)

Is this converted to shl first?

157

(x + y) + (x * 4) --> (x * 5) + y

Is this converted to shl first?

170

(x + 2) + (x * t) --> (t + 1) * x + 2

[Allen]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

775

Thanks, I restrict to mul as some performance regression of logic combination tests

787–788

Yes, for case (t-1)+(5*t) -> (t*5)+(t-1) -> (t*5+t)-1

• here is the 1st step: (t-1)+(5*t) -> (t*5)+(t-1)
• above transform is the 2ns step: (t*5)+(t-1) -> (t*5+t)-1

[Allen]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

759

Thansk for your suggestion, addressed https://reviews.llvm.org/D136912

llvm/test/Transforms/InstCombine/add4.ll

157

Instcombine is executed many times, and we have a chance to match the mul version.

[Allen]

Address comment, I think it is better to separate the precommit test after accept the total changes.

[Allen]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

780

As we have condition TopLevelOpcode == RHSOpcode, so the operand of I and New must be same, this can guard the "New" is an OBO instruction

780

I don't try to update the no-wrap to start begin, and will check that if the basic changes is accepted.

787–788

Ok, I'll separate the function after this patch reviewed to make sure this is the direction.

[Allen]

Rebase top to fix the failed case in file Transforms/PGOProfile/chr.ll

[Allen]

ping?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 /// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).
 /// Returns the simplified value, or null if it didn't simplify.
 Value *InstCombinerImpl::SimplifyUsingDistributiveLaws(BinaryOperator &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
   Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
 
-  {
-    // Factorization.
-    Value *A, *B, *C, *D;
-    Instruction::BinaryOps LHSOpcode, RHSOpcode;
-    if (Op0)
-      LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B);
-    if (Op1)
-      RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D);
 
-    // The instruction has the form "(A op' B) op (C op' D)".  Try to factorize
-    // a common term.
-    if (Op0 && Op1 && LHSOpcode == RHSOpcode)
-      if (Value *V = tryFactorization(I, LHSOpcode, A, B, C, D))
-        return V;
 
-    // The instruction has the form "(A op' B) op (C)".  Try to factorize common
-    // term.
-    if (Op0)
-      if (Value *Ident = getIdentityValue(LHSOpcode, RHS))
-        if (Value *V = tryFactorization(I, LHSOpcode, A, B, RHS, Ident))
-          return V;
+  if (Op0) {
+  }
 
-    // The instruction has the form "(B) op (C op' D)".  Try to factorize common
-    // term.
-    if (Op1)
-      if (Value *Ident = getIdentityValue(RHSOpcode, LHS))
-        if (Value *V = tryFactorization(I, RHSOpcode, LHS, Ident, C, D))
-          return V;
+  if (Op1) {
   }
 
+  // The instruction has the form "(A * B) op (C op D)".  Try to factorize
+  // common term for "(A * B) op (C)".
+  if (Op0 && Op1 && LHSOpcode == Instruction::Mul &&
+      TopLevelOpcode == RHSOpcode && Instruction::isCommutative(RHSOpcode))
+    if (Value *Ident = getIdentityValue(LHSOpcode, C))
+      if (Value *V = tryFactorization(I, LHSOpcode, A, B, C, Ident)) {
+        Value *New = Builder.CreateBinOp(RHSOpcode, V, D);
+        if (dyn_cast<OverflowingBinaryOperator>(&I)) {
+          cast<Instruction>(New)->setHasNoSignedWrap(I.hasNoSignedWrap());
+          cast<Instruction>(New)->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
+        }
+        return New;
+      }
+
+  // The instruction has the form "(A op' B) op' (C * D)". See if expanding it
+  // out to "(C * D) op' (A op' B)" results in simplifications.
+  if (Op0 && Op1 && RHSOpcode == Instruction::Mul && A == C &&
+      LHSOpcode == TopLevelOpcode &&
+      rightDistributesOverLeft(TopLevelOpcode, RHSOpcode)) {
+    bool InnerCommutative = Instruction::isCommutative(TopLevelOpcode);
+    if (dyn_cast<ConstantInt>(B) && InnerCommutative) {
+      // They do! Return "RHS op' LHS".
+      ++NumExpand;
+      Value *New = Builder.CreateBinOp(TopLevelOpcode, RHS, LHS);
+      New->takeName(&I);
+      if (dyn_cast<OverflowingBinaryOperator>(&I)) {
+        cast<Instruction>(New)->setHasNoSignedWrap(I.hasNoSignedWrap());
+        cast<Instruction>(New)->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
+      }
+      return New;
+    }
+  }
+
   // Expansion.
   if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
     // The instruction has the form "(A op' B) op C".  See if expanding it out
     // to "(A op C) op' (B op C)" results in simplifications.
     Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
     Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
 
     // Disable the use of undef because it's not safe to distribute undef.

llvm/test/Transforms/InstCombine/add4.ll

 ;
   %t = urem i32 %x, 299
   %t1 = udiv i32 %x, 299
   %t2 = urem i32 %t1, 147483647
   %t3 = mul i32 %t2, 299
   %t4 = add i32 %t, %t3
   ret i32 %t4
 }
+
+; (x - 1) - (x * C) --> (1 + C) * x - 1
+define i32 @mul_add_common_factor_commute0(i32 %x) {
+; CHECK-LABEL: @mul_add_common_factor_commute0(
+; CHECK-NEXT:    [[X3:%.*]] = mul i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X3]], -1
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+  %x1 = add i32 %x, -1
+  %x2 = mul i32 %x, 5
+  %x3 = add i32 %x1, %x2
+  ret i32 %x3
+}
+
+; (x - 1) - (x * C) --> (1 + C) * x - 1
+define i32 @mul_add_common_factor_commute1(i32 %x) {
+; CHECK-LABEL: @mul_add_common_factor_commute1(
+; CHECK-NEXT:    [[X3:%.*]] = mul i32 [[X:%.*]], 5
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X3]], -1
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+  %x1 = add i32 %x, -1
+  %x2 = mul i32 %x, 4
+  %x3 = add i32 %x2, %x1
+  ret i32 %x3
+}
+
+; (x + y) - (x * C) --> (1 + C) * x + y
+define i32 @mul_add_common_factor_commute2(i32 %x, i32 %y) {
+; CHECK-LABEL: @mul_add_common_factor_commute2(
+; CHECK-NEXT:    [[X3:%.*]] = mul i32 [[X:%.*]], 5
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X3]], [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+  %x1 = add i32 %x, %y
+  %x2 = mul i32 %x, 4
+  %x3 = add i32 %x2, %x1
+  ret i32 %x3
+}
+
+; (x + 2) - (x * t) --> (1 + t) * x + 2
+define i32 @mul_add_common_factor_commute3(i32 %x, i32 %t) {
+; CHECK-LABEL: @mul_add_common_factor_commute3(
+; CHECK-NEXT:    [[X11:%.*]] = add i32 [[T:%.*]], 1
+; CHECK-NEXT:    [[X3:%.*]] = mul i32 [[X11]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X3]], 2
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+  %x1 = add i32 %x, 2
+  %x2 = mul i32 %x, %t
+  %x3 = add i32 %x2, %x1
+  ret i32 %x3
+}
+

llvm/test/Transforms/PGOProfile/chr.ll

 ; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP0]], 2
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[TMP6]], 0
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[BB3]], label [[BB2_NONCHR:%.*]], !prof [[PROF16]]
 ; CHECK:       bb2.nonchr:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[BB0]] ], [ [[TMP5]], [[BB2_NONCHR]] ], [ [[TMP5]], [[BB1_NONCHR]] ]
-; CHECK-NEXT:    [[TMP9:%.*]] = mul i32 [[TMP8]], 42
-; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], -99
-; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP9]], [[TMP10]]
-; CHECK-NEXT:    ret i32 [[TMP11]]
+; CHECK-NEXT:    [[TMP9:%.*]] = mul i32 [[TMP8]], 43
+; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP9]], -99
+; CHECK-NEXT:    ret i32 [[TMP10]]
 ;
 entry:
   %0 = load i32, ptr %i
   %1 = and i32 %0, 1
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %bb1, label %bb0, !prof !15
 
 bb0: