[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

1477

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

1477

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

498 ↗

(On Diff #452620)

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).

500 ↗

(On Diff #452620)

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

24

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

142

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 ↗

(On Diff #452718)

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 ↗

(On Diff #452718)

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 ↗

(On Diff #452934)

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 ↗

(On Diff #452993)

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/Transforms/InstCombine/InstCombinePHI.cpp

static Value *simplifyUsingControlFlow(InstCombiner &Self, PHINode &PN,
   if (InsertPt != BB->end()) {
     Self.Builder.SetInsertPoint(&*InsertPt);
     return Self.Builder.CreateNot(Cond);
   }
 
   return nullptr;
 }
 
+bool phiAllConstantOperandsAreZero(PHINode &PN) {
+  size_t ZeroConstCount = 0;
+  for (Value *V : PN.operands())
+    if (Constant *ConstVA = dyn_cast<Constant>(V))
+      if (ConstVA->isZeroValue())
+        ZeroConstCount += 1;
+  return ZeroConstCount == PN.getNumOperands() - 1;
+}
 // PHINode simplification
 //
 Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
   if (Value *V = simplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
     return replaceInstUsesWith(PN, V);
 
   if (Instruction *Result = foldPHIArgZextsIntoPHI(PN))
     return Result;
if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
             MadeChange = true;
           }
         }
       }
       if (MadeChange)
         return &PN;
     }
   }
+  if (phiAllConstantOperandsAreZero(PN)) {
+    for (Value *Operands : PN.operands()) {
+      if (Instruction *Fmul = dyn_cast<Instruction>(Operands)) {
+        if (Fmul->getOpcode() != Instruction::FMul || !Fmul->hasNoInfs() ||
+            !Fmul->hasNoNaNs() || !Fmul->hasNoSignedZeros())
+          break;
+        for (Value *InstOperand : Fmul->operands()) {
+          if (PHINode *PhiOperand = dyn_cast<PHINode>(InstOperand)) {
+            if (PhiOperand != &PN)
+              continue;
+            auto *ZeroVal = Constant::getNullValue(PN.getType());
+            replaceInstUsesWith(PN, ZeroVal);
+          }
+        }
+      }
+    }
+  }
 
   // We sometimes end up with phi cycles that non-obviously end up being the
   // same value, for example:
   //   z = some value; x = phi (y, z); y = phi (x, z)
   // where the phi nodes don't necessarily need to be in the same block.  Do a
   // quick check to see if the PHI node only contains a single non-phi value, if
   // so, scan to see if the phi cycle is actually equal to that value.
   {

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() {
 ; CHECK-LABEL: @test_mul_fast_flags(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ARR_D:%.*]] = alloca [1000 x double], align 8
 ; 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:
   %arr_d = alloca [1000 x double], align 8
   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_nnan_flag_enabled() {
 ; CHECK-LABEL: @test_nnan_flag_enabled(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ARR_D:%.*]] = alloca [1000 x double], align 8
 ; 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 double [[F_PROD_01]], [[TMP0]]
 ; CHECK-NEXT:    [[INC]] = add i64 [[I_02]], 1
for.body:                                         ; preds = %entry, %for.body
   %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_non_constant_operand() {
 ; CHECK-LABEL: @test_phi_non_constant_operand(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ARR_D:%.*]] = alloca [1000 x double], align 8
 ; 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:
   %arr_d = alloca [1000 x double], align 8
   %entry_val = fmul fast double 1.0, 0.0
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]

 end:                                              ; preds = %for.body
   %f_prod.0.lcssa = phi double [ %mul, %for.body ]
   ret double %f_prod.0.lcssa
 }
 
 define double @test_multiple_phi_operands() {
 ; CHECK-LABEL: @test_multiple_phi_operands(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ARR_D:%.*]] = alloca [1000 x double], align 8
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY:%.*]], label [[ENTRY_2:%.*]]
 ; CHECK:       entry_2:
 ; CHECK-NEXT:    br label [[FOR_BODY]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ 0, [[ENTRY_2]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[F_PROD_01:%.*]] = phi double [ 0.000000e+00, [[ENTRY]] ], [ 0.000000e+00, [[ENTRY_2]] ], [ [[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:
   %arr_d = alloca [1000 x double], align 8
   %entry_cond = icmp ult i32 0, 0
   br i1 %entry_cond, label %for.body, label %entry_2
 
 entry_2:
   br label %for.body