[IndVars] Eliminate redundant type cast between integer and float

[Allen]

Summary

Recompute the range: match for fptosi of sitofp, and then query the range of the input to the sitofp
according the comment on D129140.

Fixes https://github.com/llvm/llvm-project/issues/55505.

[nikic]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

681

This is probably not needed, as SIToFP operand must be an integer, which is always SCEVable.

683

Why do we care about hasOneUse here? This seems at odds with your users() loop below.

687

getSignedRange?

698

How can IVOperand not dominate U? IVOperands dominates UseInst, which dominates all its uses.

699

There may be a type mismatch here: Either we need to limit to the same type, or insert sext/trunc as necessary.

[Allen]

Add type checking

[Allen]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

681

done, thanks!

683

yes, it can be deleted, thanks @nikic

687

good catch, thanks!

698

thanks, I updated it with replaceAllUsesWith.

699

thanks, I add limit to the same type now.

[nikic]

This looks reasonable to me, but I think we could use at least two more tests: 1. Type mismatch between the integer IV and the fptosi result. 2. Case where the transform is *not* valid because there are too many significant bits.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

679

We don't really need the IVOperand argument, given how casts only have a single operand.

694

We should also add CI to DeadInsts, so it gets DCEd.

699

Can just be Changed = true, no need for |=.

llvm/test/Transforms/IndVarSimplify/floating-point-small-iv.ll

3

Drop the -adce here.

37

For this test, it would be better to use an integer IV from the start, rather than going through the float -> int transform. This makes it clear that your code works even if IndVars is not the producer of the integer IV (which is the key difference to D129140).

[Allen]

Address commant and add two more tests

[Allen]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

679

Done

694

Thanks @nikic very much, apply your comment.

699

Done

llvm/test/Transforms/IndVarSimplify/floating-point-small-iv.ll

3

Done, it can be dropped after add CI to DeadInsts according your comment, thanks.

37

Done

[nikic]

LGTM

A natural followup here would be to do the same for the unsigned case.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

687

nit: Unnecessary empty line

929

Directly -> directly

[nikic]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

931

You might want to call pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers); here, to queue the potentially new direct uses of IVOperand (which no longer go through the cast pair and might be simplified now).

[Allen]

In D129191#3637968, @nikic wrote:

LGTM

A natural followup here would be to do the same for the unsigned case.

Ok, I'll try to address this , thanks for reminding

[Allen]

Address the remain comment, and new call pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers)

[Allen]

rebase to top

[Allen]

In D129191#3638113, @Allen wrote:

In D129191#3637968, @nikic wrote:

LGTM

A natural followup here would be to do the same for the unsigned case.

Ok, I'll try to address this , thanks for reminding. Address the unsigned case here https://reviews.llvm.org/D129358

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

687

Done

929

Done

931

Done , thanks very much

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

public:
     /// specified induction variable. This is the top-level driver that applies
     /// all simplifications to users of an IV.
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
     bool replaceIVUserWithLoopInvariant(Instruction *UseInst);
+    bool replaceFloatIVWithIntegerIV(Instruction *UseInst);
 
     bool eliminateOverflowIntrinsic(WithOverflowInst *WO);
     bool eliminateSaturatingIntrinsic(SaturatingInst *SI);
     bool eliminateTrunc(TruncInst *TI);
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     bool makeIVComparisonInvariant(ICmpInst *ICmp, Value *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
   LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
                     << " with loop invariant: " << *S << '\n');
   ++NumFoldedUser;
   Changed = true;
   DeadInsts.emplace_back(I);
   return true;
 }
 
+/// Eliminate redundant type cast between integer and float.
+bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {
+  if (UseInst->getOpcode() != CastInst::SIToFP)
+    return false;
+
+  Value *IVOperand = UseInst->getOperand(0);
+  // Get the symbolic expression for this instruction.
+  ConstantRange IVRange = SE->getSignedRange(SE->getSCEV(IVOperand));
+  unsigned DestNumSigBits = UseInst->getType()->getFPMantissaWidth();
+  if (IVRange.getActiveBits() <= DestNumSigBits) {
+    for (User *U : UseInst->users()) {
+      // Match for fptosi of sitofp and with same type.
+      auto *CI = dyn_cast<FPToSIInst>(U);
+      if (!CI || IVOperand->getType() != CI->getType())
+        continue;
+
+      CI->replaceAllUsesWith(IVOperand);
+      DeadInsts.push_back(CI);
+      LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI
+                        << " with: " << *IVOperand << '\n');
+
+      ++NumFoldedUser;
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
 /// Eliminate any operation that SCEV can prove is an identity function.
 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
                                            Instruction *IVOperand) {
   if (!SE->isSCEVable(UseInst->getType()) ||
       (UseInst->getType() != IVOperand->getType()) ||
       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
     return false;
 
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
            strengthenOverflowingOperation(BO, IVOperand)) ||
           (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
         // re-queue uses of the now modified binary operator and fall
         // through to the checks that remain.
         pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
       }
     }
 
+    // Try to use integer induction for FPToSI of float induction directly.
+    if (replaceFloatIVWithIntegerIV(UseInst)) {
+      // Re-queue the potentially new direct uses of IVOperand.
+      pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
+      continue;
+    }
+
     CastInst *Cast = dyn_cast<CastInst>(UseInst);
     if (V && Cast) {
       V->visitCast(Cast);
       continue;
     }
     if (isSimpleIVUser(UseInst, L, SE)) {
       pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
     }

llvm/test/Transforms/IndVarSimplify/floating-point-iv.ll

 define void @pr55505_remove_redundant_fptosi_for_float_iv(i32 %index, ptr %dst) {
 ; CHECK-LABEL: @pr55505_remove_redundant_fptosi_for_float_iv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[FLOAT_IV_INT:%.*]] = phi i32 [ 1000, [[ENTRY:%.*]] ], [ [[FLOAT_IV_NEXT_INT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[INDVAR_CONV:%.*]] = sitofp i32 [[FLOAT_IV_INT]] to float
 ; CHECK-NEXT:    call void @use.float(float [[INDVAR_CONV]])
-; CHECK-NEXT:    [[CONV_I32:%.*]] = fptosi float [[INDVAR_CONV]] to i32
-; CHECK-NEXT:    call void @use.i32(i32 [[CONV_I32]])
+; CHECK-NEXT:    call void @use.i32(i32 [[FLOAT_IV_INT]])
 ; CHECK-NEXT:    [[CONV_I16:%.*]] = fptosi float [[INDVAR_CONV]] to i16
 ; CHECK-NEXT:    [[CONV_I64:%.*]] = fptosi float [[INDVAR_CONV]] to i64
 ; CHECK-NEXT:    call void @use.i16(i16 [[CONV_I16]])
 ; CHECK-NEXT:    call void @use.i64(i64 [[CONV_I64]])
 ; CHECK-NEXT:    [[UCONV_I16:%.*]] = fptoui float [[INDVAR_CONV]] to i16
 ; CHECK-NEXT:    [[UCONV_I64:%.*]] = fptoui float [[INDVAR_CONV]] to i64
 ; CHECK-NEXT:    call void @use.i16(i16 [[UCONV_I16]])
 ; CHECK-NEXT:    call void @use.i64(i64 [[UCONV_I64]])

llvm/test/Transforms/IndVarSimplify/floating-point-small-iv.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -indvars -S | FileCheck %s
+
+@array = dso_local global [16777219 x i32] zeroinitializer, align 4
+
+define void @small_const_bound(i32 %index) {
+; CHECK-LABEL: @small_const_bound(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV_INT:%.*]] = phi i32 [ 100, [[ENTRY:%.*]] ], [ [[DEC_INT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[IV_INT]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 [[IDXPROM]]
+; CHECK-NEXT:    store i32 [[IV_INT]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DEC_INT]] = add nsw i32 [[IV_INT]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[DEC_INT]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[CLEANUP:%.*]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %iv.int = phi i32 [ 100, %entry ], [ %dec.int, %for.body ]
+  %indvar.conv = sitofp i32 %iv.int to float
+  %conv = fptosi float %indvar.conv to i32
+  %idxprom = sext i32 %conv to i64
+  %arrayidx = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 %idxprom
+  store i32 %conv, i32* %arrayidx, align 4
+  %dec.int = add nsw i32 %iv.int, -1
+  %cmp = icmp ugt i32 %dec.int, 0
+  br i1 %cmp, label %for.body, label %cleanup
+
+cleanup:                                          ; preds = %for.body
+  ret void
+}
+
+; Negative test: The transform is *not* valid because there are too many significant bits
+define void @overflow_masked_const_bound(i32 %index) {
+; CHECK-LABEL: @overflow_masked_const_bound(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV_INT:%.*]] = phi i32 [ 16777218, [[ENTRY:%.*]] ], [ [[DEC_INT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[INDVAR_CONV:%.*]] = sitofp i32 [[IV_INT]] to float
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float [[INDVAR_CONV]] to i32
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[CONV]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 [[IDXPROM]]
+; CHECK-NEXT:    store i32 [[CONV]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DEC_INT]] = add nsw i32 [[IV_INT]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[DEC_INT]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[CLEANUP:%.*]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %iv.int = phi i32 [ 16777218, %entry ], [ %dec.int, %for.body ] ; intermediate 16777218 (= 1 << 24 + 2)
+  %indvar.conv = sitofp i32 %iv.int to float
+  %conv = fptosi float %indvar.conv to i32
+  %idxprom = sext i32 %conv to i64
+  %arrayidx = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 %idxprom
+  store i32 %conv, i32* %arrayidx, align 4
+  %dec.int = add nsw i32 %iv.int, -1
+  %cmp = icmp ugt i32 %dec.int, 0
+  br i1 %cmp, label %for.body, label %cleanup
+
+cleanup:                                          ; preds = %for.body
+  ret void
+}
+
+; Negative test: Type mismatch between the integer IV and the fptosi result
+define void @mismatch_type_const(i32 %index) {
+;
+; CHECK-LABEL: @mismatch_type_const(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IV_INT:%.*]] = phi i32 [ 100, [[ENTRY:%.*]] ], [ [[DEC_INT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[INDVAR_CONV:%.*]] = sitofp i32 [[IV_INT]] to float
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float [[INDVAR_CONV]] to i16
+; CHECK-NEXT:    [[IDXPROM32:%.*]] = sext i16 [[CONV]] to i32
+; CHECK-NEXT:    [[IDXPROM64:%.*]] = sext i16 [[CONV]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 [[IDXPROM64]]
+; CHECK-NEXT:    store i32 [[IDXPROM32]], i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DEC_INT]] = add nsw i32 [[IV_INT]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[DEC_INT]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[CLEANUP:%.*]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %iv.int = phi i32 [ 100, %entry ], [ %dec.int, %for.body ]
+  %indvar.conv = sitofp i32 %iv.int to float
+  %conv = fptosi float %indvar.conv to i16
+  %idxprom32 = sext i16 %conv to i32
+  %idxprom64 = sext i16 %conv to i64
+  %arrayidx = getelementptr inbounds [16777219 x i32], [16777219 x i32]* @array, i64 0, i64 %idxprom64
+  store i32 %idxprom32, i32* %arrayidx, align 4
+  %dec.int = add nsw i32 %iv.int, -1
+  %cmp = icmp ugt i32 %dec.int, 0
+  br i1 %cmp, label %for.body, label %cleanup
+
+cleanup:                                          ; preds = %for.body
+  ret void
+}