Add select simplifications

[mcberg2017]

Summary

In these cases, two selects have constant selectable operands for
both the true and false components and have the same conditional expression.
We then create two arithmetic operations of the same type and feed a final
select operation using the result of the true arithmetic for the true operand
and the result of the false arithmetic for the false operand and reuse the original
conditionl expression. The arithmetic operations are naturally folded as a
consequence, leaving only the newly formed select to replace the old arithmetic operation.

[majnemer]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1408–1409 ↗

(On Diff #112210)

Shouldn't these copy the fast math flags from the original add?

[majnemer]

Please combine your two files into one and reduce the testcases a little bit. No need for allocas, loads or stores.

[craig.topper]

Is this potentially better handled by extracting the code from the bottom of SimplifyUsingDistributiveLaws that deals with selects on both arms of a binop. The fact that simplifyUsingDistributiveLaws isn't called on fadd/fsub/fmul is causing this to be handled differently that integer add/sub/mul.

[mcberg2017]

I will add the fastmath flag copy in as well, as tryFactorization does not do that.

[mcberg2017]

Updated for fast math flags

[mcberg2017]

Should i add a fsub case in the tests?

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

749 ↗

(On Diff #112210)

Ditto here regarding fastmath

[craig.topper]

I don't think that's right for the fastmath flags. In your example case the returned instruction is a select. That's not the instruction that should be getting the fastmath flags. I'm suprised that doesn't assert.

[mcberg2017]

Is SimplifyUsingDistributiveLaws safe for the non constant cases of fmul/fadd/fsub when not using fast math?

[mcberg2017]

So after looking in depth at SimplifyUsingDistributiveLaws, its pretty clear
that it is not safe when fast math is not available for the cases of
fadd/fsub/fmul. So I have reverted the code to the first form, while placing
the fast math flag copies on instructions that might not fold, which
should only happen rarely. I also added a test case for fsub as well.

[craig.topper]

I was only asking about using this portion of simplifyUsingDistributiveLaws

// (op (select (a, c, b)), (select (a, d, b))) -> (select (a, (op c, d), 0))
// (op (select (a, b, c)), (select (a, b, d))) -> (select (a, 0, (op c, d)))
if (auto *SI0 = dyn_cast<SelectInst>(LHS)) {
  if (auto *SI1 = dyn_cast<SelectInst>(RHS)) {
    if (SI0->getCondition() == SI1->getCondition()) {
      Value *SI = nullptr;
      if (Value *V =
              SimplifyBinOp(TopLevelOpcode, SI0->getFalseValue(),
                            SI1->getFalseValue(), SQ.getWithInstruction(&I)))
        SI = Builder.CreateSelect(SI0->getCondition(),
                                  Builder.CreateBinOp(TopLevelOpcode,
                                                      SI0->getTrueValue(),
                                                      SI1->getTrueValue()),
                                  V);
      if (Value *V =
              SimplifyBinOp(TopLevelOpcode, SI0->getTrueValue(),
                            SI1->getTrueValue(), SQ.getWithInstruction(&I)))
        SI = Builder.CreateSelect(
            SI0->getCondition(), V,
            Builder.CreateBinOp(TopLevelOpcode, SI0->getFalseValue(),
                                SI1->getFalseValue()));
      if (SI) {
        SI->takeName(&I);
        return SI;
      }
    }
  }
}

And since that's defering all of the intelligence to InstSimplify, I really hope its safe without fastmath. And it would never create a new instruction because InstSimplify isn't alllowed to. I believe it would also handle "select C, 0, B + select C, A, 0 -> select C, A, B"

[craig.topper]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1410 ↗

(On Diff #112272)

I don't think this can ever be an Instruction. If you started with two Constants, at worst you'd get back a ConstantExpr here and you need to set the fast math flags on that.

[mcberg2017]

These changes support the fast math flag and the contexts according to the last note
on using the code snippet in InstCombining under SimplifyUsingDistributiveLaws, which I made a
helper function with support for handling fast math if required. The changes
pass make check-llvm.

[mcberg2017]

Craig/David: Are there any issues that need to be resolved for this code review to conclude and move towards check in?

[qcolombet]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1410 ↗

(On Diff #112272)

In theory, one could decide not to use the constant folder in the builder so it could happen, couldn't it?

lib/Transforms/InstCombine/InstructionCombining.cpp

721 ↗

(On Diff #112407)

The comment seems weird to me.
Shouldn't it be:
(op (select (a, c, b)), (select (a, d, b))) -> (select (a, (op c, d), (op d, b)))?

Also I don't get why there is two of them :).

734 ↗

(On Diff #112407)

When SI != nullptr, shouldn't we use SI instead of CreateBinOp for B1, B2, here?

test/Transforms/InstCombine/select_arithmetic.ll

2 ↗

(On Diff #112407)

Could you add a comment on what this test case is checking?

6 ↗

(On Diff #112407)

Please use opt -instnamer to get rid of the implicit variables.

[qcolombet]

lib/Transforms/InstCombine/InstructionCombining.cpp

721 ↗

(On Diff #112407)

I screwed up the variable naming but you get it! (op something something instead of 0)

[qcolombet]

lib/Transforms/InstCombine/InstructionCombining.cpp

734 ↗

(On Diff #112407)

I meant the previous V (the one we got from the call of SimplifyBinOp B1 B2).
(Gosh I need more coffee!)

[mcberg2017]

Updated for latest review.

[qcolombet]

LGTM.

Thanks Michael.

[mcberg2017]

As I do not yet have check-in privalges, can someone check-in this code

lib/Transforms/InstCombine/InstructionCombining.cpp

721 ↗

(On Diff #112407)

I opted for this comment:

// (op (select (a, b, c)), (select (a, d, e))) -> (select (a, (op b, d), (op c, e)))

and augmented the code to fit the comment

[qcolombet]

@majnemer
Hi David,

Does the patch LG to you before I commit on Michael's behalf?

Cheers,
-Quentin

[majnemer]

LGTM with nits addressed.

lib/Transforms/InstCombine/InstructionCombining.cpp

714 ↗

(On Diff #114883)

I'd rename it something a little more unique/descriptive like SimplifySelectsFeedingBinaryOp

727 ↗

(On Diff #114883)

Could you assign this on the prior line? I don't think you save anything by doing the assignment in the if statement because the variable is used later.

[mcberg2017]

Post review update.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

735 ↗

(On Diff #115740)

I think you always pass true for CarryFastMathFlags. Is the goal to avoid invalid access to getFastMathFlags ? If so, I'd instead do something like if (isa<FPMathOperator>(&I)).

736 ↗

(On Diff #115740)

Forgive me if I am wrong but wouldn't this mutate the state of the builder beyond your intended use? I think you need a IRBuilder<>::FastMathFlagGuard.

740 ↗

(On Diff #115740)

I think the common custom in LLVM is to simply say if (V1).

test/Transforms/InstCombine/select_arithmetic.ll

41–47 ↗

(On Diff #115740)

I don't think these add to the test, I'd remove them.

[mcberg2017]

Ok, that is a nice way to guard FP ops, subsequently I have removed the flag argument in this patch to rely on that and on whatever the BinaryOperator has set on it. The test file is also updated and a subsequent test run is clean.

[mcberg2017]

Increased scope for fastmath guard on builder and separated scope for non fp ops

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

735–749 ↗

(On Diff #115860)

I think you can reduce the duplication by doing something like:

BuilderTy::FastMathFlagGuard Guard(Builder);
if (isa<FPMathOperator>(&I))
  Builder.setFastMathFlags(I.getFastMathFlags());

Value *V1 = SimplifyBinOp(Opcode, C, E, SQ.getWithInstruction(&I));
SI = V1 ? Builder.CreateSelect(A1, Builder.CreateBinOp(Opcode, B, D), V1) : SI;
if (Value *V2 = SimplifyBinOp(Opcode, B, D, SQ.getWithInstruction(&I)))
  SI = V1 ? Builder.CreateSelect(A1, V2, V1) : Builder.CreateSelect(A1, V2, Builder.CreateBinOp(Opcode, C, E));

if (SI) {
  SI->takeName(&I);
  return SI;
}

The guard will harmlessly no-op when we don't have an FP operator.

[mcberg2017]

Ok, and the guard is of no effect when the fastmath flags are not set. Testing is still clean.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

731–733 ↗

(On Diff #115864)

You can simplify this a little using m_Specific:

if (match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C))) &&
    match(RHS, m_Select(m_Specific(A), m_Value(D), m_Value(E)))) {

This also lets us remove a level of indentation.

739 ↗

(On Diff #115864)

Are there situations where we'd unnecessarily CreateSelect?

My reading of the code is that we will throw away this SelectInst if both V1 and V2 end up being true.

Maybe something like the following would work:

Value *SI = nullptr;
Value *V1 = SimplifyBinOp(Opcode, C, E, SQ.getWithInstruction(&I));
Value *V2 = SimplifyBinOp(Opcode, B, D, SQ.getWithInstruction(&I));
if (V1 && V2) {
  SI = Builder.CreateSelect(A1, V2, V1);
} else if (V2) {
  SI = Builder.CreateSelect(A1, V2, Builder.CreateBinOp(Opcode, C, E));
} else if (V1) {
  SI = Builder.CreateSelect(A1, Builder.CreateBinOp(Opcode, B, D), V1);
}

if (SI) {
  SI->takeName(&I);
  return SI;
}

739–741 ↗

(On Diff #115864)

It is uncommon in LLVM to parenthesize the condition of a ternary expression.

[mcberg2017]

Simplified to reduce lexical depth, removed a return and removed ternaries.

[majnemer]

LGTM

[mcrosier]

Unfortunately, we're seeing a 4.7% regression in SPEC2006/lbm due to this change. The number of dynamic instructions is increased by ~5.5%.

We're running on AArch64/Falkor with the following flags: -O3 -fno-math-errno -ffp-contract=fast -fomit-frame-pointer

All of the code changes are in LBM_performStreamCollide(), which accounts for ~98% of execution.

I'll keep digging so I can provide more details, but I wanted to report the regression.

[mcrosier]

In D37019#881221, @mcrosier wrote:

Unfortunately, we're seeing a 4.7% regression in SPEC2006/lbm due to this change. The number of dynamic instructions is increased by ~5.5%.

We're running on AArch64/Falkor with the following flags: -O3 -fno-math-errno -ffp-contract=fast -fomit-frame-pointer

All of the code changes are in LBM_performStreamCollide(), which accounts for ~98% of execution.

I'll keep digging so I can provide more details, but I wanted to report the regression.

Balaram posted a candidate fix here: https://reviews.llvm.org/D38288

llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
           // Insert the new integer add.
           Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv");
           return new SIToFPInst(NewAdd, I.getType());
         }
       }
     }
   }
 
-  // select C, 0, B + select C, A, 0 -> select C, A, B
-  {
-    Value *A1, *B1, *C1, *A2, *B2, *C2;
-    if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
-        match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) {
-      if (C1 == C2) {
-        Constant *Z1=nullptr, *Z2=nullptr;
-        Value *A, *B, *C=C1;
-        if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
-            Z1 = dyn_cast<Constant>(A1); A = A2;
-            Z2 = dyn_cast<Constant>(B2); B = B1;
-        } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
-            Z1 = dyn_cast<Constant>(B1); B = B2;
-            Z2 = dyn_cast<Constant>(A2); A = A1;
-        }
-
-        if (Z1 && Z2 &&
-            (I.hasNoSignedZeros() ||
-             (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
-          return SelectInst::Create(C, A, B);
-        }
-      }
-    }
-  }
+  // Handle specials cases for FAdd with selects feeding the operation
+  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))
+    return replaceInstUsesWith(I, V);
 
   if (I.hasUnsafeAlgebra()) {
     if (Value *V = FAddCombine(Builder).simplify(&I))
       return replaceInstUsesWith(I, V);
   }
 
   return Changed ? &I : nullptr;
 }
if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) {
     if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) {
       Value *NewExt = Builder.CreateFPExt(V, I.getType());
       Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt);
       NewI->copyFastMathFlags(&I);
       return NewI;
     }
   }
 
+  // Handle specials cases for FSub with selects feeding the operation
+  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
+    return replaceInstUsesWith(I, V);
+
   if (I.hasUnsafeAlgebra()) {
     if (Value *V = FAddCombine(Builder).simplify(&I))
       return replaceInstUsesWith(I, V);
   }
 
   return nullptr;
 }

llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// operation distributes over.
   ///
   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
   /// -> "A*(B+C)") or expanding out if this results in 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 *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 
+  // Binary Op helper for select operations where the expression can be
+  // efficiently reorganized.
+  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
+                                        Value *RHS);
+
   /// This tries to simplify binary operations by factorizing out common terms
   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
   Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
                           Value *, Value *, Value *);
 
   /// Match a select chain which produces one of three values based on whether
   /// the LHS is less than, equal to, or greater than RHS respectively.
   /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,

llvm/trunk/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) {
         // -X * Y => -(X*Y) (Promote negation as high as possible)
         Value *T = Builder.CreateFMul(N0, Opnd1);
         Value *Neg = Builder.CreateFNeg(T);
         Neg->takeName(&I);
         return replaceInstUsesWith(I, Neg);
       }
     }
 
+    // Handle specials cases for FMul with selects feeding the operation
+    if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
+      return replaceInstUsesWith(I, V);
+
     // (X*Y) * X => (X*X) * Y where Y != X
     //  The purpose is two-fold:
     //   1) to form a power expression (of X).
     //   2) potentially shorten the critical path: After transformation, the
     //  latency of the instruction Y is amortized by the expression of X*X,
     //  and therefore Y is in a "less critical" position compared to what it
     //  was before the transformation.
     //

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
       // They do! Return "A op B".
       ++NumExpand;
       A = Builder.CreateBinOp(TopLevelOpcode, A, B);
       A->takeName(&I);
       return A;
     }
   }
 
-  // (op (select (a, c, b)), (select (a, d, b))) -> (select (a, (op c, d), 0))
-  // (op (select (a, b, c)), (select (a, b, d))) -> (select (a, 0, (op c, d)))
-  if (auto *SI0 = dyn_cast<SelectInst>(LHS)) {
-    if (auto *SI1 = dyn_cast<SelectInst>(RHS)) {
-      if (SI0->getCondition() == SI1->getCondition()) {
-        Value *SI = nullptr;
-        if (Value *V =
-                SimplifyBinOp(TopLevelOpcode, SI0->getFalseValue(),
-                              SI1->getFalseValue(), SQ.getWithInstruction(&I)))
-          SI = Builder.CreateSelect(SI0->getCondition(),
-                                    Builder.CreateBinOp(TopLevelOpcode,
-                                                        SI0->getTrueValue(),
-                                                        SI1->getTrueValue()),
-                                    V);
-        if (Value *V =
-                SimplifyBinOp(TopLevelOpcode, SI0->getTrueValue(),
-                              SI1->getTrueValue(), SQ.getWithInstruction(&I)))
-          SI = Builder.CreateSelect(
-              SI0->getCondition(), V,
-              Builder.CreateBinOp(TopLevelOpcode, SI0->getFalseValue(),
-                                  SI1->getFalseValue()));
-        if (SI) {
-          SI->takeName(&I);
-          return SI;
-        }
-      }
-    }
+  return SimplifySelectsFeedingBinaryOp(I, LHS, RHS);
+}
+
+Value *InstCombiner::SimplifySelectsFeedingBinaryOp(BinaryOperator &I,
+                                                    Value *LHS, Value *RHS) {
+  Instruction::BinaryOps Opcode = I.getOpcode();
+  // (op (select (a, b, c)), (select (a, d, e))) -> (select (a, (op b, d), (op
+  // c, e)))
+  Value *A, *B, *C, *D, *E;
+  if (match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C))) &&
+      match(RHS, m_Select(m_Specific(A), m_Value(D), m_Value(E)))) {
+    BuilderTy::FastMathFlagGuard Guard(Builder);
+    if (isa<FPMathOperator>(&I))
+      Builder.setFastMathFlags(I.getFastMathFlags());
+
+    Value *V1 = SimplifyBinOp(Opcode, C, E, SQ.getWithInstruction(&I));
+    Value *V2 = SimplifyBinOp(Opcode, B, D, SQ.getWithInstruction(&I));
+    if (V1 && V2)
+      SI = Builder.CreateSelect(A, V2, V1);
+    else if (V2)
+      SI = Builder.CreateSelect(A, V2, Builder.CreateBinOp(Opcode, C, E));
+    else if (V1)
+      SI = Builder.CreateSelect(A, Builder.CreateBinOp(Opcode, B, D), V1);
+
+    if (SI)
   }
 
-  return nullptr;
+  return SI;
 }
 
 /// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a
 /// constant zero (which is the 'negate' form).
 Value *InstCombiner::dyn_castNegVal(Value *V) const {
   if (BinaryOperator::isNeg(V))
     return BinaryOperator::getNegArgument(V);
 

llvm/trunk/test/Transforms/InstCombine/select_arithmetic.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; Tests folding constants from two similar selects that feed a add
+define float @test1(i1 zeroext %arg) #0 {
+  %tmp = select i1 %arg, float 5.000000e+00, float 6.000000e+00
+  %tmp1 = select i1 %arg, float 1.000000e+00, float 9.000000e+00
+  %tmp2 = fadd float %tmp, %tmp1
+  ret float %tmp2
+; CHECK-LABEL: @test1(
+; CHECK: %tmp2 = select i1 %arg, float 6.000000e+00, float 1.500000e+01
+; CHECK-NOT: fadd
+; CHECK: ret float %tmp2
+}
+
+; Tests folding constants from two similar selects that feed a sub
+define float @test2(i1 zeroext %arg) #0 {
+  %tmp = select i1 %arg, float 5.000000e+00, float 6.000000e+00
+  %tmp1 = select i1 %arg, float 1.000000e+00, float 9.000000e+00
+  %tmp2 = fsub float %tmp, %tmp1
+  ret float %tmp2
+; CHECK-LABEL: @test2(
+; CHECK: %tmp2 = select i1 %arg, float 4.000000e+00, float -3.000000e+00
+; CHECK-NOT: fsub
+; CHECK: ret float %tmp2
+}
+
+; Tests folding constants from two similar selects that feed a mul
+define float @test3(i1 zeroext %arg) #0 {
+  %tmp = select i1 %arg, float 5.000000e+00, float 6.000000e+00
+  %tmp1 = select i1 %arg, float 1.000000e+00, float 9.000000e+00
+  %tmp2 = fmul float %tmp, %tmp1
+  ret float %tmp2
+; CHECK-LABEL: @test3(
+; CHECK: %tmp2 = select i1 %arg, float 5.000000e+00, float 5.400000e+01
+; CHECK-NOT: fmul
+; CHECK: ret float %tmp2
+}
+