[instcombine] Test for zero initialisation optimisation of a product given fast flags

[zjaffal]

Summary

Given a zero initialised variable iterating through an array and multiplying its elements, the optimiser should be able to remove the loop safely and return the initial value because fast math flags are enabled.

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

The loop here can be deleted and we can return f_prod instead

[fhahn]

I think the title/description needs updating to make clear this just adds tests.

[instcombine] Check for zero initialisation optimisation of a product given fast flags are enabled in clang.

Also it's not really Clang related, as this is a generic IR optimization, so it is best to drop the reference to Clang from the title.

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

21

Could you pass this as an argument to the tests to avoid reading memory that's not initialized?

166

I think it would be better to pass this value as argument.

241

I think it would be better to pass this condition as argument rather than having a trivial comparison.

[zjaffal]

pass constants and arrays as function parameters

[zjaffal]

Updating D131757: [instcombine] Check for zero initialisation optimisation of a product given fast flags are enabled in clang.

[fhahn]

It looks like you accidentally uploaded the wrong patch here. Originally this just added the tests. (Also the title needs updating to avoid confusion)

[zjaffal]

Updating D131757: [instcombine] Check for zero initialisation optimisation of a product given fast flags are enabled in clang.

[zjaffal]

Updating D131757: [instcombine] Check for zero initialisation optimisation of a product given fast flags are enabled in clang.

[fhahn]

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

233

might be good to also have a variant of this test that doesn't have 0.0 as incoming value.

[zjaffal]

Updating D131757: [instcombine] Test for zero initialisation optimisation of a product given fast flags

[fhahn]

LGTM, thanks!

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;
 
+  PHINode *PN = nullptr;
+  Value *Start = nullptr, *Step = nullptr;
+  if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() &&
+      I.hasNoSignedZeros()) {
+    if (Constant *StartConst = dyn_cast<Constant>(Start)) {
+      if (StartConst->isZeroValue())
+        return replaceInstUsesWith(I, StartConst);
+    }
+  }
+
   // 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;

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
   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
 ; CHECK-NEXT:    [[MUL]] = fmul fast double [[F_PROD_01]], [[TMP0]]
for.body:                                         ; preds = %entry, %for.body
   %f_prod.01 = phi double [ 0.0, %entry ], [0.0, %entry_2], [ %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
 }