[instcombine] Optimise for zero initialisation of product given fast flags are enabled

[zjaffal]

Summary

Currently, clang ignores the 0 initialisation in finite math
For example:

double f_prod = 0;
double arr[1000];
for (size_t i = 0; i < 1000; i++) {
  f_prod *= arr[i];
 }

Clang will ignore that f_prod is set to zero and it will generate assembly to iterate over the loop.

[fhahn]

llvm/test/Transforms/InstCombine/remove-loop-phi-fastmul.ll

10

It would be good to split off the test changes to a separate patch that just adds the tests.

20

Would be good to use 'rotated' version of the loop to keep things simpler.

37

We should also have tests where all the incoming values are instructions or arguments. We also need some tests with phis with more than 2 incoming values.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1476 ↗

(On Diff #451814)

Can we use llvm::matchSimpleRecurrence()?

Here's an example usage within instcombine:
https://github.com/llvm/llvm-project/blob/1828c75d5f4ff657cf977476091fa224c8193e1d/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L2201

[zjaffal]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1476 ↗

(On Diff #451814)

I tested using llvm::matchSimpleRecurrence. Here is what I found

1. We need to move the optimisation into InstCombineMulDivRem instead which is fine.
2. We need to add a case into llvm::matchSimpleRecurrence to handle FMul
3. The main issue of using matchSimpleRecurrence is that it doesn't handle phi with more than two operands.

I am not sure how common phi's with more than two operands are.

[zjaffal]

• Move functionality to InstCombineMulDivRem.cpp
• Use matchSimpleRecurrence

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

489

Checking for no-inf is correct, but not strictly necessary since 0.0 * Inf = NaN and we check 'nnan' (see InstSimplify for the existing constraints for the fold of X*0.0 to 0.0).

491

We don't need to walk through the phi operands again - the zero we want had to be captured as "Start"?

if (matchSimpleRecurrence(&I, Phi, Start, Step) && match(Start, m_Zero()) &&
    I.hasNoInfs() && I.hasNoNaNs() && I.hasNoSignedZeros())
  return replaceInstUsesWith(I, Start);

llvm/test/Transforms/InstCombine/remove-loop-phi-fastmul.ll

23

This test should have the minimal FMF needed to trigger the transform.

164–165

I don't think this test is adding value. It just shows the expected X*0.0 simplification to 0.0?

All of the tests should be reduced to the minimum IR needed to show the transform. Looking at existing tests in the file "recurrence.ll" might be useful.

If you want to verify that a larger example reduces with the usual opt pipeline, it would be better to add a test under "test/Transforms/PhaseOrdering".

[zjaffal]

Updating D131672: [instcombine] Optimise for zero initialisation of product given finite math in Clang

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

492

Was there a reason to not use the shorter and suggested m_Zero() matcher?
It probably doesn't make a difference for this particular pattern, but that code handles things like vector constants, so we won't miss any unusual types.

[zjaffal]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

492

I didn't know it existed. I will push a change now

[zjaffal]

Updating D131672: [instcombine] Optimise for zero initialisation of product given fast flags are enabled

[zjaffal]

Updating D131672: [instcombine] Optimise for zero initialisation of product given fast flags are enabled

[spatel]

LGTM - see inline comment for formatting nit.
The tests seem fine too, but let @fhahn have another look in case there are any other suggestions.

I'm not sure what source causes this pattern, but there could be related fast-math simplifications like X * 1.0 --> X.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

492

Remove braces around one-line 'if' clause to be consistent with surrounding code.

[zjaffal]

remove brackets around if statement

[fhahn]

Thanks for the update! Could you also update the description to describe the transformation implemented, with the legality considerations as well?

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

487

Could you add a comment explaining the transform we are applying here? Also, it would probably be good to move this more towards the end of the function, so cheaper patterns are tried first.

[zjaffal]

Updating D131672: [instcombine] Optimise for zero initialisation of product given fast flags are enabled

[RKSimon]

@zjaffal Please can you rebase against trunk again? D131838 managed to affect some of your tests

[zjaffal]

Rebase

[fhahn]

LGTM, thanks!

In D131672#3725714, @spatel wrote:

LGTM - see inline comment for formatting nit.
The tests seem fine too, but let @fhahn have another look in case there are any other suggestions.

I'm not sure what source causes this pattern, but there could be related fast-math simplifications like X * 1.0 --> X.

The source was a user report. I am not sure about FMUL recurrences that have 1.0 as start value. But I think we might want the same fold for integer multiply as follow up.

llvm/lib/Analysis/ValueTracking.cpp

for (unsigned i = 0; i != 2; ++i) {
     // TODO: Expand list -- xor, div, gep, uaddo, etc..
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::Shl:
     case Instruction::Add:
     case Instruction::Sub:
     case Instruction::And:
     case Instruction::Or:
-    case Instruction::Mul: {
+    case Instruction::Mul:
+    case Instruction::FMul: {
       Value *LL = LU->getOperand(0);
       Value *LR = LU->getOperand(1);
       // Find a recurrence.
       if (LL == P)
         L = LR;
       else if (LR == P)
         L = LL;
       else

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

 // srem, urem, frem.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
     return FoldedMul;
 
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
     return replaceInstUsesWith(I, FoldedMul);
 
   if (Instruction *R = foldFPSignBitOps(I))
     return R;
 
   // X * -1.0 --> -X
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   if (match(Op1, m_SpecificFP(-1.0)))
     return UnaryOperator::CreateFNegFMF(Op0, &I);
 
   // -X * C --> X * -C
   Value *X, *Y;
   Constant *C;
   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
     if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
       return BinaryOperator::CreateFMulFMF(X, NegC, &I);
 
   // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
   if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
if (I.isFast()) {
     }
     if (Log2) {
       Value *Log2 = Builder.CreateUnaryIntrinsic(Intrinsic::log2, X, &I);
       Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
       return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
     }
   }
 
+  // Given NoNans and NoSignedZeros are enabled
+  // and we have a phi node initalised to zero
+  // We can replace fmul operation within a loop by zero
+  PHINode *PN = nullptr;
+  Value *Start = nullptr, *Step = nullptr;
+  if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() &&
+      I.hasNoSignedZeros() && match(Start, m_Zero()))
+    return replaceInstUsesWith(I, Start);
+
   return nullptr;
 }
 
 /// Fold a divide or remainder with a select instruction divisor when one of the
 /// select operands is zero. In that case, we can use the other select operand
 /// because div/rem by zero is undefined.
 bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
   SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));

llvm/test/Transforms/InstCombine/remove-loop-phi-fastmul.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 define double @test_mul_fast_flags(ptr %arr_d) {
 ; CHECK-LABEL: @test_mul_fast_flags(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[F_PROD_01:%.*]] = phi double [ 0.000000e+00, [[ENTRY]] ], [ [[MUL:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [1000 x double], ptr [[ARR_D:%.*]], i64 0, i64 [[I_02]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load double, ptr [[ARRAYIDX]], align 8
-; CHECK-NEXT:    [[MUL]] = fmul fast double [[F_PROD_01]], [[TMP0]]
 ; CHECK-NEXT:    [[INC]] = add i64 [[I_02]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INC]], 1000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[END:%.*]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    ret double 0.000000e+00
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %f_prod.01 = phi double [ 0.000000e+00, %entry ], [ %mul, %for.body ]
   %arrayidx = getelementptr inbounds [1000 x double], ptr %arr_d, i64 0, i64 %i.02
   %0 = load double, ptr %arrayidx, align 8
   %mul = fmul fast double %f_prod.01, %0
   %inc = add i64 %i.02, 1
   %cmp = icmp ult i64 %inc, 1000
   br i1 %cmp, label %for.body, label %end
 
 end:                                              ; preds = %for.body
   %f_prod.0.lcssa = phi double [ %mul, %for.body ]
   ret double %f_prod.0.lcssa
 }
 
 define double @test_nsz_nnan_flags_enabled(ptr %arr_d) {
 ; CHECK-LABEL: @test_nsz_nnan_flags_enabled(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[F_PROD_01:%.*]] = phi double [ 0.000000e+00, [[ENTRY]] ], [ [[MUL:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [1000 x double], ptr [[ARR_D:%.*]], i64 0, i64 [[I_02]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load double, ptr [[ARRAYIDX]], align 8
-; CHECK-NEXT:    [[MUL]] = fmul nnan nsz double [[F_PROD_01]], [[TMP0]]
 ; CHECK-NEXT:    [[INC]] = add i64 [[I_02]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INC]], 1000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[END:%.*]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret double [[MUL]]
+; CHECK-NEXT:    ret double 0.000000e+00
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
   %f_prod.01 = phi double [ 0.000000e+00, %entry ], [ %mul, %for.body ]
   %arrayidx = getelementptr inbounds [1000 x double], ptr %arr_d, i64 0, i64 %i.02
for.body:                                         ; preds = %entry, %for.body
   %inc = add i64 %i.02, 1
   %cmp = icmp ult i64 %inc, 1000
   br i1 %cmp, label %for.body, label %end
 
 end:                                              ; preds = %for.body
   %f_prod.0.lcssa = phi double [ %mul, %for.body ]
   ret double %f_prod.0.lcssa
 }
 
 define double @test_phi_initalise_to_non_zero(ptr %arr_d) {
 ; CHECK-LABEL: @test_phi_initalise_to_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[F_PROD_01:%.*]] = phi double [ 1.000000e+00, [[ENTRY]] ], [ [[MUL:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [1000 x double], ptr [[ARR_D:%.*]], i64 0, i64 [[I_02]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load double, ptr [[ARRAYIDX]], align 8