[SimplifyIndVar] Simplify non-overflowing saturating add/sub

[nikic]

Summary

If we can detect that saturating math that depends on an IV cannot overflow, replace it with simple math. This is similar to the CVP optimization from D62703, just based on a different underlying analysis (SCEV vs LVI) that catches different cases.

One case this doesn't handle yet is if the IV calculation itself uses a saturating counter.

[lebedev.ri]

This looks rather similar to the eliminateOverflowIntrinsic(), but i don't have knowledge about this pass.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

475–476

Hm, this is because we didn't deal with non-ExtractValueInst uses of WO?
Since we know the overflow won't happen, those can be simply folded to a single insert, no?

[nikic]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

475–476

That should be possible, and that's what we do in other places doing this optimization. I think that this code is going out of the way to replace the ExtractValues instead because SCEV cannot reason about aggregate operations.

[nikic]

ping

[reames]

LGTM

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

public:
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
     bool replaceIVUserWithLoopInvariant(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 IsSigned);
     void replaceRemWithNumerator(BinaryOperator *Rem);
     void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
       }
       ToDelete.push_back(EVI);
     }
   }
 
   for (auto *EVI : ToDelete)
     EVI->eraseFromParent();
 
   if (WO->use_empty())
     WO->eraseFromParent();
 
   return true;
 }
 
+bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {
+  const SCEV *LHS = SE->getSCEV(SI->getLHS());
+  const SCEV *RHS = SE->getSCEV(SI->getRHS());
+  if (!willNotOverflow(SE, SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
+    return false;
+
+  BinaryOperator *BO = BinaryOperator::Create(
+      SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
+  if (SI->isSigned())
+    BO->setHasNoSignedWrap();
+  else
+    BO->setHasNoUnsignedWrap();
+
+  SI->replaceAllUsesWith(BO);
+  DeadInsts.emplace_back(SI);
+  Changed = true;
+  return true;
+}
+
 bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {
   // It is always legal to replace
   //   icmp <pred> i32 trunc(iv), n
   // with
   //   icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.
   // Or with
   //   icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.
   // Or with either of these if pred is an equality predicate.
if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
     if (Bin->getOpcode() == Instruction::SDiv)
       return eliminateSDiv(Bin);
   }
 
   if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))
     if (eliminateOverflowIntrinsic(WO))
       return true;
 
+  if (auto *SI = dyn_cast<SaturatingInst>(UseInst))
+    if (eliminateSaturatingIntrinsic(SI))
+      return true;
+
   if (auto *TI = dyn_cast<TruncInst>(UseInst))
     if (eliminateTrunc(TI))
       return true;
 
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;
 
   return false;

llvm/test/Transforms/IndVarSimplify/eliminate-sat.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -indvars | FileCheck %s
 
 declare i32 @llvm.uadd.sat.i32(i32, i32)
 declare i32 @llvm.sadd.sat.i32(i32, i32)
 declare i32 @llvm.usub.sat.i32(i32, i32)
 declare i32 @llvm.ssub.sat.i32(i32, i32)
 
 define void @uadd_sat(i32* %p) {
 ; CHECK-LABEL: @uadd_sat(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SAT:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[I]], i32 1)
-; CHECK-NEXT:    store volatile i32 [[SAT]], i32* [[P:%.*]]
+; CHECK-NEXT:    [[SAT1:%.*]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    store volatile i32 [[SAT1]], i32* [[P:%.*]]
 ; CHECK-NEXT:    [[I_INC]] = add nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[I_INC]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop

 }
 
 define void @sadd_sat(i32* %p) {
 ; CHECK-LABEL: @sadd_sat(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SAT:%.*]] = call i32 @llvm.sadd.sat.i32(i32 [[I]], i32 1)
-; CHECK-NEXT:    store volatile i32 [[SAT]], i32* [[P:%.*]]
+; CHECK-NEXT:    [[SAT1:%.*]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    store volatile i32 [[SAT1]], i32* [[P:%.*]]
 ; CHECK-NEXT:    [[I_INC]] = add nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[I_INC]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop

 }
 
 define void @usub_sat(i32* %p) {
 ; CHECK-LABEL: @usub_sat(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SAT:%.*]] = call i32 @llvm.usub.sat.i32(i32 [[I]], i32 1)
-; CHECK-NEXT:    store volatile i32 [[SAT]], i32* [[P:%.*]]
+; CHECK-NEXT:    [[SAT1:%.*]] = sub nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    store volatile i32 [[SAT1]], i32* [[P:%.*]]
 ; CHECK-NEXT:    [[I_INC]] = add nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[I_INC]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop

 }
 
 define void @ssub_sat(i32* %p) {
 ; CHECK-LABEL: @ssub_sat(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SAT:%.*]] = call i32 @llvm.ssub.sat.i32(i32 [[I]], i32 1)
-; CHECK-NEXT:    store volatile i32 [[SAT]], i32* [[P:%.*]]
+; CHECK-NEXT:    [[SAT1:%.*]] = sub nsw i32 [[I]], 1
+; CHECK-NEXT:    store volatile i32 [[SAT1]], i32* [[P:%.*]]
 ; CHECK-NEXT:    [[I_INC]] = add nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[I_INC]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop