Fix invariant fdiv hoisting in LICM

[rampitec]

Summary

FDiv is replaced with multiplication by reciprocal and invariant
reciprocal is hoisted out of the loop, while multiplication remains
even if invariant.

Switch checks for all invariant operands and only invariant
denominator to fix the issue.

[vit9696]

Hello,

The proposed change seems right to me in both senses:

• moving the invariant out of the loop (obvious);
• not making a reciprocal here, as it may add an extra overhead for non-constant divisors.

The only case I could see this behaving worse is when the loop is not supposed to be executed, but the operations will still get speculatively hoisted. To my view this is uncommon and kind of contradicts the assumption of the LICM pass that loops do get executed more than once. It could have been nice to see some benchmarks on real projects, but I expect the inner arithmetics to be normally collapsed by other passes and defeat any change effects except in some special code, which this change supposedly optimises for, so it is not worth it.

Accepted.

Best regards,
Vit

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;
       }
 
+      // 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) &&
+          (IsMustExecute ||
+           isSafeToExecuteUnconditionally(
+               I, DT, CurLoop, SafetyInfo, ORE,
+               CurLoop->getLoopPreheader()->getTerminator()))) {
+        Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+        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) &&
-          (IsMustExecute ||
-           isSafeToExecuteUnconditionally(
-               I, DT, CurLoop, SafetyInfo, ORE,
-               CurLoop->getLoopPreheader()->getTerminator()))) {
-        Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
-        continue;
-      }
-
       if (IsMustExecute)
         IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
     }
   }
 
   return Changed;
 }
 

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 {
+define zeroext i1 @invariant_denom(double %v) #0 {
 entry:
-; CHECK-LABEL: @f(
+; CHECK-LABEL: @invariant_denom(
 ; 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-NOT: fdiv
   br i1 %v13, label %end, label %loop
 
 end:                                      ; preds = %loop
   %v15 = phi i32 [ %v11, %loop ]
   %v16 = icmp ne i32 %v15, 0
   ret i1 %v16
 }
 
+define void @invariant_fdiv(float* %out, float %arg) {
+; CHECK-LABEL: @invariant_fdiv(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: %div = fdiv fast float 4.000000e+00, %arg
+; CHECK-NEXT: fmul fast float %div, 0x41F0000000000000
+entry:
+  br label %loop
+
+loop:                                              ; preds = %loop, %entry
+  %ind = phi i32 [ 0, %entry ], [ %inc, %loop ]
+
+; CHECK-LABEL: loop:
+; CHECK: getelementptr
+; CHECK-NOT: fdiv
+; CHECK-NOT: fmul
+  %div = fdiv fast float 4.000000e+00, %arg
+  %mul = fmul fast float %div, 0x41F0000000000000
+  %gep = getelementptr inbounds float, float* %out, i32 %ind
+  store float %mul, float* %gep, align 4
+  %inc = add nuw nsw i32 %ind, 1
+  %cond = icmp eq i32 %inc, 1024
+  br i1 %cond, label %exit, label %loop
+
+exit:                                              ; preds = %loop
+  ret void
+}