Fix PR32157 - Hoist fp division from the loops and replace by a reciprocal

[vit9696]

Summary

This change may double the performance of certain functions relying on floating point division in the loops. Certain examples and discussion are listed in the mentioned bugreport.

[vit9696]

Ping.

[hfinkel]

A comment on the variable names; otherwise I think this looks good. Thanks!

lib/Transforms/Scalar/LICM.cpp

445

I find naming this Reciproal to be a bit confusing (because I'd expect a 1/something to be named Reciprocal). You might even name InvDivisor ReciprocalDivisor (or just RecipDivisor). The result of the multiplication could be named Product or Division or something along those lines.

[vit9696]

In D30819#710056, @hfinkel wrote:

A comment on the variable names; otherwise I think this looks good. Thanks!

Thanks. This makes good sense to me. Updated the diff.

[hfinkel]

Formatting nit, otherwise LGTM.

lib/Transforms/Scalar/LICM.cpp

445

This line is too long (max is 80 characters).

[vit9696]

Alright, fixed the line width as well.

lib/Transforms/Scalar/LICM.cpp

for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         if (isInstructionTriviallyDead(&I, TLI)) {
           CurAST->deleteValue(&I);
           I.eraseFromParent();
         }
         Changed = true;
         continue;
       }
 
+      // Attempt to remove floating point division out of the loop by converting
+      // it to a reciprocal multiplication.
+      if (I.getOpcode() == Instruction::FDiv &&
+          CurLoop->isLoopInvariant(I.getOperand(1)) &&
+          I.hasAllowReciprocal()) {
+        auto Divisor = I.getOperand(1);
+        auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
+        auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
+        ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
+        ReciprocalDivisor->insertBefore(&I);
+
+        auto Product = BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
+        Product->setFastMathFlags(I.getFastMathFlags());
+        Product->insertAfter(&I);
+        I.replaceAllUsesWith(Product);
+        I.eraseFromParent();
+
+        hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
+        Changed = true;
+        continue;
+      }
+
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
           isSafeToExecuteUnconditionally(
               I, DT, CurLoop, SafetyInfo, ORE,

test/Transforms/LICM/hoist-fast-fdiv.ll

+; RUN: opt -licm -S < %s | FileCheck %s
+
+; Function Attrs: noinline norecurse nounwind readnone ssp uwtable
+define zeroext i1 @f(double) #0 {
+; CHECK-LABEL: @f(
+; CHECK-NEXT: fdiv fast double 1.000000e+00, %0
+  br label %2
+
+; <label>:2                                       ; preds = %1, %2
+  %3 = phi i32 [ 0, %1 ], [ %11, %2 ]
+  %4 = phi i32 [ 0, %1 ], [ %12, %2 ]
+  %5 = uitofp i32 %4 to double
+prediv:
+; CHECK-LABEL: label prediv:
+; CHECK-NEXT: fmul fast double
+  %6 = fdiv fast double %5, %0
+  %7 = fptoui double %6 to i64
+  %8 = and i64 %7, 1
+  %9 = xor i64 %8, 1
+  %10 = trunc i64 %9 to i32
+  %11 = add i32 %10, %3
+  %12 = add nuw i32 %4, 1
+  %13 = icmp eq i32 %12, -1
+  br i1 %13, label %14, label %2
+
+; <label>:14                                      ; preds = %2
+  %15 = phi i32 [ %11, %2 ]
+  %16 = icmp ne i32 %15, 0
+  ret i1 %16
+}