[InstCombine] X *fast (C ? 1.0 : 0.0) -> C ? X : 0.0

[foad]

Summary

This is implemented with more general rules:

X op (C ? P : Q) -> C ? (X op P) : (X op Q)

// if X op P and X op Q both simplify

(C ? P : Q) op Y -> C ? (P op Y) : (Q op Y)

// if P op Y and Q op Y both simplify

The tests include some other cases where these more general rules apply.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

776

Question to reviewers: would it be better to enhance SimplifyQuery / InstrInfoQuery to know about fast math flags, so that I don't have to pass FMF around explicitly?

[xbolva00]

I think we need a few more tests here

a) vector tests
b) 'extra use' tests
c) negative tests

[xbolva00]

Not sure how other reviewers, but I consider the use of 'C' as confusing here, since 'C' is usually a constant. I would recommend to avoid 'C', if it is not a constant.

Edit: As I see, original code also used 'C', so feel free to ignore me :)

[foad]

In D64713#1585080, @xbolva00 wrote:

Not sure how other reviewers, but I consider the use of 'C' as confusing here, since 'C' is usually a constant. I would recommend to avoid 'C', if it is not a constant.

Edit: As I see, original code also used 'C', so feel free to ignore me :)

Right, and since the code uses all of A B C D E F, I think it's reasonably clear that none of them are meant to stand for anything in particular.

[foad]

Add a vector test.

[foad]

In D64713#1585078, @xbolva00 wrote:

I think we need a few more tests here

a) vector tests
b) 'extra use' tests
c) negative tests

a) I've added one.
b) The patch doesn't introduce any new hasOneUse() tests. Do you think it should?
c) There are infinitely many expressions not optimized by this pattern :) Can you give an example of the kind of thing you're thinking of?

[xbolva00]

b) yes, one more test never hurts
c) one test per.. e.g.; broken precondition, missing 'fast' ?

[foad]

In D64713#1585110, @xbolva00 wrote:

b) yes, one more test never hurts

I meant:
b) The patch doesn't introduce any more uses of hasOneUse() in the source code. Do you think it should?

[xbolva00]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

777

Can you simplify lines 782-808? Almost same code in both branches..

[foad]

Add a negative test for fmul without fast math flags.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

777

I'd prefer to keep the SimplifyFPBinOp/CreateSelect calls in separate branches, otherwise I think the code will get much more confusing to read.

As for the boilerplate code to do with fast math flags: I could either pull it all out to the top level of the function (so it would run unconditionally, even if we're not able to optimize anything); or I could try teaching SimplifyQuery about fast math flags (as mentioned above), which would simplify it a little. Do you have any preference?

[foad]

Rewrite to remove duplicated code.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

777

As for the boilerplate code to do with fast math flags:

Maybe use lambda?

[xbolva00]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

799

Nice :)

[mcberg2017]

Looks ok to me, but I would like some of the others to chime in first.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

793

Question to reviewers: should I make this condition LHSIsSelect && LHS->hasOneUse() (and the same for RHS on line 792)? I am tempted to do so just to be conservative, to make sure that this instcombine actually removes all uses of the original select.

[lebedev.ri]

(i'm not touching fp folds)

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

793

Presumably you'd want to add all the necessary variation of tests with extra uses, and see which ones need
restrictions to one-use cases.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

784–785

I know this is an existing function name, but it doesn't match my expectation based on the name. Change it to simplifyAnyBinOp() or simplifyIntOrFPBinOp() as a preliminary step?

llvm/test/Transforms/InstCombine/fmul.ll

1002

'fast' is over-specifying the constraints here (and probably all of these tests).
fmul by 1.0 doesn't need any flags; fmul by 0.0 only needs nsz and nnan.

1013

Vary the opcodes (fadd, fsub, fdiv) in these tests for better coverage?

llvm/test/Transforms/InstCombine/mul.ll

522–530

Is this test changed by this patch? If not, it shouldn't be here.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

784–785

I don't think your suggestions are any better than the status quo; how is anyone supposed to know or remember the difference between simplifyBinOp and simplifyAnyBinOp? Instead, how about I overload simplifyBinOp to take FMF as an optional (last) argument?

llvm/test/Transforms/InstCombine/fmul.ll

1002

True. I could change it to nsz nnan if you think that's better. (Incidentally I think nsz ninf should also be sufficient in theory, but I won't pursue that in this patch.)

1013

fmul is fairly unique in having useful simplifications for two different constant operands, 0.0 and 1.0, but I'll see what I can do.

llvm/test/Transforms/InstCombine/mul.ll

522–530

Yes. Without this patch, this test does not get simplified at all.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

784–785

Ok, that's less misleading than what we have now. You can make that change without review, then rebase this patch.

llvm/test/Transforms/InstCombine/mul.ll

522–530

Ok, then please commit this test with baseline CHECK lines as another preliminary NFC step ahead of this patch.

[foad]

llvm/test/Transforms/InstCombine/mul.ll

522–530

I don't really understand why you're suggesting to do that with this test case, but not with the other tests I added. There really is not much difference between them.

Perhaps it would be clearer if I split my original patch into two:

1. Pass fast math flags in to the calls to simplifyBinOp.
2. Add the X op (C ? P : Q) -> C ? (X op P) : (X op Q) combines that are really the main point of the patch.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

784–785

See D64902. I know you said I could do it without review, but I prefer to give others a chance to comment before committing.

[spatel]

llvm/test/Transforms/InstCombine/mul.ll

522–530

Yes, please add all of the baseline tests for each part of this patch and fork this into the minimal code change patches, so we can see each piece independently.

[xbolva00]

Do we miss int version of this? @spatel @lebedev.ri

int foo(int x, int y, bool b) {

return x / (b  ? 1 : y);

}

We have sdiv x, (select b 1 y), x86-64:
cmov...
idiv...

[lebedev.ri]

In D64713#1604369, @xbolva00 wrote:

Do we miss int version of this? @spatel @lebedev.ri

int foo(int x, int y, bool b) {
    return x / (b  ? 1 : y);
}

We have sdiv x, (select b 1 y), x86-64:
cmov...
idiv...

I'd agree that having select %b (div %x, %y), %x would be better but that does not look like a valid transform:
https://godbolt.org/z/4Fs_dB
https://rise4fun.com/Alive/xplW

Optimization: D64713-int

ERROR: Domain of definedness of Target is smaller than Source's for i32 %r

Example:
%b i1 = 0x1 (1, -1)
%y i32 = poison
%x i32 = poison
%cond i32 = 0x00000001 (1)
%t0 i32 = UB
Source value: poison
Target value: UB

$ /repositories/alive2/build-Clang-unknown/alive -root-only /tmp/test.ll 
Processing /tmp/test.ll..

----------------------------------------
Name: D64713-int
  %cond = select i1 %b, i8 1, i8 %y
  %r = sdiv i8 %x, %cond
  ret i8 %r
=>
  %cond = select i1 %b, i8 1, i8 %y
  %t0 = sdiv i8 %x, %y
  %r = select i1 %b, i8 %x, i8 %t0
  ret i8 %r

ERROR: Source is more defined than target

Example:
i1 %b = #x1 (1)
i8 %y = poison
i8 %x = poison

Source:
i8 %cond = #x01 (1)
i8 %r = poison

Target:
i8 %cond = #x01 (1)
i8 %t0 = poison
i8 %r = poison

[xbolva00]

ah, poison :/

I checked gcc codegen and gcc can fold it..

[foad]

llvm/test/Transforms/InstCombine/mul.ll

522–530

OK, part of this is now split out into D65658.

[foad]

Rebase on top of pre-committed test cases.

[foad]

Ping! I think I've addressed all the earlier comments.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

794–804

Is it correct that everything outside of lines 791-801 is functionally identical to before? If so, please pre-commit that part as NFC.

[foad]

Rebase after committing NFC parts.

[foad]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

794–804

Yes, done: d162e02cee74

[spatel]

LGTM - the title of the patch is too specific at this point; more like:
[InstCombine] hoist binop that simplifies into arms of select
?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

794–804

Thanks - that makes it clear how the new transforms fit in.

[xbolva00]

In D64713#1604491, @lebedev.ri wrote:

In D64713#1604369, @xbolva00 wrote:

Do we miss int version of this? @spatel @lebedev.ri

int foo(int x, int y, bool b) {
    return x / (b  ? 1 : y);
}

We have sdiv x, (select b 1 y), x86-64:
cmov...
idiv...

I'd agree that having select %b (div %x, %y), %x would be better but that does not look like a valid transform:
https://godbolt.org/z/4Fs_dB
https://rise4fun.com/Alive/xplW

Optimization: D64713-int

ERROR: Domain of definedness of Target is smaller than Source's for i32 %r

Example:
%b i1 = 0x1 (1, -1)
%y i32 = poison
%x i32 = poison
%cond i32 = 0x00000001 (1)
%t0 i32 = UB
Source value: poison
Target value: UB

$ /repositories/alive2/build-Clang-unknown/alive -root-only /tmp/test.ll 
Processing /tmp/test.ll..

----------------------------------------
Name: D64713-int
  %cond = select i1 %b, i8 1, i8 %y
  %r = sdiv i8 %x, %cond
  ret i8 %r
=>
  %cond = select i1 %b, i8 1, i8 %y
  %t0 = sdiv i8 %x, %y
  %r = select i1 %b, i8 %x, i8 %t0
  ret i8 %r

ERROR: Source is more defined than target

Example:
i1 %b = #x1 (1)
i8 %y = poison
i8 %x = poison

Source:
i8 %cond = #x01 (1)
i8 %r = poison

Target:
i8 %cond = #x01 (1)
i8 %t0 = poison
i8 %r = poison

Can this be solved using freeze?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Value *InstCombiner::SimplifySelectsFeedingBinaryOp(BinaryOperator &I,
   FastMathFlags FMF;
   BuilderTy::FastMathFlagGuard Guard(Builder);
   if (isa<FPMathOperator>(&I)) {
     FMF = I.getFastMathFlags();
     Builder.setFastMathFlags(FMF);
   }
 
   Instruction::BinaryOps Opcode = I.getOpcode();
   SimplifyQuery Q = SQ.getWithInstruction(&I);
 
   Value *Cond, *True = nullptr, *False = nullptr;
   if (LHSIsSelect && RHSIsSelect && A == D) {
     // (A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F)
     Cond = A;
     True = SimplifyBinOp(Opcode, B, E, FMF, Q);
     False = SimplifyBinOp(Opcode, C, F, FMF, Q);
 
     if (LHS->hasOneUse() && RHS->hasOneUse()) {
       if (False && !True)
         True = Builder.CreateBinOp(Opcode, B, E);
       else if (True && !False)
         False = Builder.CreateBinOp(Opcode, C, F);
     }
+  } else if (LHSIsSelect && LHS->hasOneUse()) {
+    // (A ? B : C) op Y -> A ? (B op Y) : (C op Y)
+    Cond = A;
+    True = SimplifyBinOp(Opcode, B, RHS, FMF, Q);
+    False = SimplifyBinOp(Opcode, C, RHS, FMF, Q);
+  } else if (RHSIsSelect && RHS->hasOneUse()) {
+    // X op (D ? E : F) -> D ? (X op E) : (X op F)
+    Cond = D;
+    True = SimplifyBinOp(Opcode, LHS, E, FMF, Q);
+    False = SimplifyBinOp(Opcode, LHS, F, FMF, Q);
   }
 
   if (!True || !False)
     return nullptr;
 
   Value *SI = Builder.CreateSelect(Cond, True, False);
   SI->takeName(&I);
   return SI;
 }
 
 /// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a
 /// constant zero (which is the 'negate' form).

llvm/test/Transforms/InstCombine/fmul.ll

 
 define float @negate_if_true(float %x, i1 %cond) {
 ; CHECK-LABEL: @negate_if_true(
 ; CHECK-NEXT:    [[TMP1:%.*]] = fneg float [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[COND:%.*]], float [[TMP1]], float [[X]]
 ; CHECK-NEXT:    ret float [[TMP2]]
 ;
   %sel = select i1 %cond, float -1.0, float 1.0
   %r = fmul float %sel, %x
   ret float %r
 }
 
 define float @negate_if_false(float %x, i1 %cond) {
 ; CHECK-LABEL: @negate_if_false(
 ; CHECK-NEXT:    [[TMP1:%.*]] = fneg arcp float [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select arcp i1 [[COND:%.*]], float [[X]], float [[TMP1]]
 ; CHECK-NEXT:    ret float [[TMP2]]
 ;
   %sel = select i1 %cond, float 1.0, float -1.0
   %r = fmul arcp float %sel, %x
   ret float %r
 }
 
 define <2 x double> @negate_if_true_commute(<2 x double> %px, i1 %cond) {
 ; CHECK-LABEL: @negate_if_true_commute(
 ; CHECK-NEXT:    [[X:%.*]] = fdiv <2 x double> <double 4.200000e+01, double 4.200000e+01>, [[PX:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = fneg ninf <2 x double> [[X]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select ninf i1 [[COND:%.*]], <2 x double> [[TMP1]], <2 x double> [[X]]
;
   %sel = select i1 %cond, <2 x double> <double -1.0, double 0.0>, <2 x double> <double 1.0, double 1.0>
   %r = fmul <2 x double> %x, %sel
   ret <2 x double> %r
 }
 
 ; X *fast (C ? 1.0 : 0.0) -> C ? X : 0.0
 define float @fmul_select(float %x, i1 %c) {
 ; CHECK-LABEL: @fmul_select(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], float 1.000000e+00, float 0.000000e+00
-; CHECK-NEXT:    [[MUL:%.*]] = fmul fast float [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[MUL:%.*]] = select fast i1 [[C:%.*]], float [[X:%.*]], float 0.000000e+00
 ; CHECK-NEXT:    ret float [[MUL]]
 ;
   %sel = select i1 %c, float 1.0, float 0.0
   %mul = fmul fast float %sel, %x
   ret float %mul
 }
 
 ; X *fast (C ? 1.0 : 0.0) -> C ? X : 0.0
 define <2 x float> @fmul_select_vec(<2 x float> %x, i1 %c) {
 ; CHECK-LABEL: @fmul_select_vec(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], <2 x float> <float 1.000000e+00, float 1.000000e+00>, <2 x float> zeroinitializer
-; CHECK-NEXT:    [[MUL:%.*]] = fmul fast <2 x float> [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[MUL:%.*]] = select fast i1 [[C:%.*]], <2 x float> [[X:%.*]], <2 x float> zeroinitializer
 ; CHECK-NEXT:    ret <2 x float> [[MUL]]
 ;
   %sel = select i1 %c, <2 x float> <float 1.0, float 1.0>, <2 x float> zeroinitializer
   %mul = fmul fast <2 x float> %sel, %x
   ret <2 x float> %mul
 }
 
 ; Without fast math flags we can't optimize X * (C ? 1.0 : 0.0) -> C ? X : 0.0
 define float @fmul_select_strict(float %x, i1 %c) {
 ; CHECK-LABEL: @fmul_select_strict(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], float 1.000000e+00, float 0.000000e+00
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul float [[SEL]], [[X:%.*]]
 ; CHECK-NEXT:    ret float [[MUL]]
 ;
   %sel = select i1 %c, float 1.0, float 0.0
   %mul = fmul float %sel, %x
   ret float %mul
 }
 
 ; sqrt(X) *fast (C ? sqrt(X) : 1.0) -> C ? X : sqrt(X)
 define double @fmul_sqrt_select(double %x, i1 %c) {
 ; CHECK-LABEL: @fmul_sqrt_select(
 ; CHECK-NEXT:    [[SQR:%.*]] = call double @llvm.sqrt.f64(double [[X:%.*]])
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], double [[SQR]], double 1.000000e+00
-; CHECK-NEXT:    [[MUL:%.*]] = fmul fast double [[SQR]], [[SEL]]
+; CHECK-NEXT:    [[MUL:%.*]] = select fast i1 [[C:%.*]], double [[X]], double [[SQR]]
 ; CHECK-NEXT:    ret double [[MUL]]
 ;
   %sqr = call double @llvm.sqrt.f64(double %x)
   %sel = select i1 %c, double %sqr, double 1.0
   %mul = fmul fast double %sqr, %sel
   ret double %mul
 }

llvm/test/Transforms/InstCombine/mul.ll

 ;
   %v1 = ptrtoint i32* @X to i64
   %B8 = sub i64 0, %v1
   %B4 = mul i64 %B8, %L1
   ret i64 %B4
 }
 
 define i32 @negate_if_true(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @negate_if_true(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[X]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 -1, i32 1
   %r = mul i32 %sel, %x
   ret i32 %r
 }
 
 define i32 @negate_if_false(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @negate_if_false(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[X]], i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 1, i32 -1
;
   %sel = select i1 %cond, <2 x i8> <i8 -1, i8 0>, <2 x i8> <i8 1, i8 1>
   %r = mul <2 x i8> %x, %sel
   ret <2 x i8> %r
 }
 
 ; (C ? (X /exact Y) : 1) * Y -> C ? X : Y
 define i32 @mul_div_select(i32 %x, i32 %y, i1 %c) {
 ; CHECK-LABEL: @mul_div_select(
-; CHECK-NEXT:    [[DIV:%.*]] = udiv exact i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i32 [[DIV]], i32 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[SEL]], [[Y]]
+; CHECK-NEXT:    [[MUL:%.*]] = select i1 [[C:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[MUL]]
 ;
   %div = udiv exact i32 %x, %y
   %sel = select i1 %c, i32 %div, i32 1
   %mul = mul i32 %sel, %y
   ret i32 %mul
 }