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 ↗

(On Diff #91314)

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 ↗

(On Diff #93033)

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

[vit9696]

Alright, fixed the line width as well.

llvm/trunk/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,

llvm/trunk/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 %v) #0 {
+entry:
+; CHECK-LABEL: @f(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: fdiv fast double 1.000000e+00, %v
+  br label %loop
+
+loop:                                       ; preds = %entry, %loop
+  %v3 = phi i32 [ 0, %entry ], [ %v11, %loop ]
+  %v4 = phi i32 [ 0, %entry ], [ %v12, %loop ]
+  %v5 = uitofp i32 %v4 to double
+
+; CHECK-LABEL: loop:
+; CHECK: fmul fast double
+; CHECK-NOT: fdiv
+  %v6 = fdiv fast double %v5, %v
+  %v7 = fptoui double %v6 to i64
+  %v8 = and i64 %v7, 1
+  %v9 = xor i64 %v8, 1
+  %v10 = trunc i64 %v9 to i32
+  %v11 = add i32 %v10, %v3
+  %v12 = add nuw i32 %v4, 1
+  %v13 = icmp eq i32 %v12, -1
+  br i1 %v13, label %end, label %loop
+
+end:                                      ; preds = %loop
+  %v15 = phi i32 [ %v11, %loop ]
+  %v16 = icmp ne i32 %v15, 0
+  ret i1 %v16
+}
+