[IndVars] Drop "exact" flag from lshr and udiv when substituting their args

[mkazantsev]

Summary

There is a transform that may replace lshr (x+1), 1 with lshr x, 1 in case
if it can prove that the result will be the same. However the initial instruction
might have an exact flag set, and it now should be dropped unless we prove
that it may hold. Incorrectly set exact attribute may then produce poison.

[sanjoy]

lgtm

lib/Transforms/Utils/SimplifyIndVar.cpp

147 ↗

(On Diff #168941)

I'd give this a less generic name, like IsTransformedUDivExact or something like that.

test/Transforms/IndVarSimplify/drop-exact.ll

8 ↗

(On Diff #168941)

Are there existing tests demonstrating that we do keep exact when legal? If not, would be nice to add one.

[mkazantsev]

test/Transforms/IndVarSimplify/drop-exact.ll

8 ↗

(On Diff #168941)

I tried playing with that, and I noticed that cases like %tmp21 = add nsw i32 %tmp17, 0 (for which that would have been legal to keep it) get optimized away earlier by other parts of IndVars, so this instruction doesn't live long enough. I will study whether or not it is possible to come here with something like this at all, and if not, I will just remove the check and drop exact unconditionally.

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

 ///
 /// Return the operand of IVOperand for this induction variable if IVOperand can
 /// be folded (in case more folding opportunities have been exposed).
 /// Otherwise return null.
 Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {
   Value *IVSrc = nullptr;
   const unsigned OperIdx = 0;
   const SCEV *FoldedExpr = nullptr;
+  bool MustDropExactFlag = false;
   switch (UseInst->getOpcode()) {
   default:
     return nullptr;
   case Instruction::UDiv:
   case Instruction::LShr:
     // We're only interested in the case where we know something about
     // the numerator and have a constant denominator.
     if (IVOperand != UseInst->getOperand(OperIdx) ||
if (UseInst->getOpcode() == Instruction::LShr) {
       uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
       if (D->getValue().uge(BitWidth))
         return nullptr;
 
       D = ConstantInt::get(UseInst->getContext(),
                            APInt::getOneBitSet(BitWidth, D->getZExtValue()));
     }
     FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D));
+    // We might have 'exact' flag set at this point which will no longer be
+    // correct after we make the replacement.
+    if (UseInst->isExact() &&
+        SE->getSCEV(IVSrc) != SE->getMulExpr(FoldedExpr, SE->getSCEV(D)))
+      MustDropExactFlag = true;
   }
   // We have something that might fold it's operand. Compare SCEVs.
   if (!SE->isSCEVable(UseInst->getType()))
     return nullptr;
 
   // Bypass the operand if SCEV can prove it has no effect.
   if (SE->getSCEV(UseInst) != FoldedExpr)
     return nullptr;
 
   LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
                     << " -> " << *UseInst << '\n');
 
   UseInst->setOperand(OperIdx, IVSrc);
   assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
 
+  if (MustDropExactFlag)
+    UseInst->dropPoisonGeneratingFlags();
+
   ++NumElimOperand;
   Changed = true;
   if (IVOperand->use_empty())
     DeadInsts.emplace_back(IVOperand);
   return IVSrc;
 }
 
 bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,

llvm/trunk/test/Transforms/IndVarSimplify/drop-exact.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -indvars -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+
+; We make a transform by getting rid of add nsw i32 %tmp17, -1; make sure that
+; we drop "exact" flag on lshr as we do it.
+define void @drop_exact(i32* %p, i64* %p1) {
+; CHECK-LABEL: @drop_exact(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB12:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    ret void
+; CHECK:       bb12:
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i32 [ -47436, [[BB:%.*]] ], [ [[TMP15:%.*]], [[BB12]] ]
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP42:%.*]], [[BB12]] ]
+; CHECK-NEXT:    [[TMP15]] = add nsw i32 [[TMP13]], -1
+; CHECK-NEXT:    [[TMP16:%.*]] = shl i32 [[TMP15]], 1
+; CHECK-NEXT:    [[TMP17:%.*]] = sub nsw i32 42831, [[TMP16]]
+; CHECK-NEXT:    [[TMP19:%.*]] = lshr i32 [[TMP17]], 1
+; CHECK-NEXT:    [[TMP20:%.*]] = urem i32 [[TMP19]], 250
+; CHECK-NEXT:    [[TMP22:%.*]] = lshr i32 [[TMP17]], 1
+; CHECK-NEXT:    store i32 [[TMP22]], i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TMP26:%.*]] = zext i32 [[TMP20]] to i64
+; CHECK-NEXT:    store i64 [[TMP26]], i64* [[P1:%.*]], align 4
+; CHECK-NEXT:    [[TMP42]] = add nuw nsw i32 [[TMP14]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[TMP42]], 719
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BB7:%.*]], label [[BB12]]
+;
+bb:
+  br label %bb12
+
+bb7:                                              ; preds = %bb12
+  ret void
+
+bb12:                                             ; preds = %bb12, %bb
+  %tmp13 = phi i32 [ -47436, %bb ], [ %tmp15, %bb12 ]
+  %tmp14 = phi i32 [ 0, %bb ], [ %tmp42, %bb12 ]
+  %tmp15 = add i32 %tmp13, -1
+  %tmp16 = shl i32 %tmp15, 1
+  %tmp17 = sub i32 42831, %tmp16
+  %tmp19 = lshr i32 %tmp17, 1
+  %tmp20 = urem i32 %tmp19, 250
+  %tmp21 = add nsw i32 %tmp17, -1
+  %tmp22 = lshr exact i32 %tmp21, 1
+  store i32 %tmp22, i32* %p, align 4
+  %tmp26 = zext i32 %tmp20 to i64
+  store i64 %tmp26, i64* %p1, align 4
+  %tmp42 = add nuw nsw i32 %tmp14, 1
+  %tmp43 = icmp ugt i32 %tmp14, 717
+  br i1 %tmp43, label %bb7, label %bb12
+}
+
+; Throw away add nsw i32 %tmp17, 0, do not drop exact flag.
+define void @dont_drop_exact(i32* %p, i64* %p1) {
+; CHECK-LABEL: @dont_drop_exact(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB12:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    ret void
+; CHECK:       bb12:
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i32 [ -47436, [[BB:%.*]] ], [ [[TMP15:%.*]], [[BB12]] ]
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP42:%.*]], [[BB12]] ]
+; CHECK-NEXT:    [[TMP15]] = add nsw i32 [[TMP13]], -1
+; CHECK-NEXT:    [[TMP16:%.*]] = shl i32 [[TMP15]], 1
+; CHECK-NEXT:    [[TMP17:%.*]] = sub nsw i32 42831, [[TMP16]]
+; CHECK-NEXT:    [[TMP19:%.*]] = lshr i32 [[TMP17]], 1
+; CHECK-NEXT:    [[TMP20:%.*]] = urem i32 [[TMP19]], 250
+; CHECK-NEXT:    [[TMP22:%.*]] = lshr exact i32 [[TMP17]], 1
+; CHECK-NEXT:    store i32 [[TMP22]], i32* [[P:%.*]], align 4
+; CHECK-NEXT:    [[TMP26:%.*]] = zext i32 [[TMP20]] to i64
+; CHECK-NEXT:    store i64 [[TMP26]], i64* [[P1:%.*]], align 4
+; CHECK-NEXT:    [[TMP42]] = add nuw nsw i32 [[TMP14]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[TMP42]], 719
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BB7:%.*]], label [[BB12]]
+;
+bb:
+  br label %bb12
+
+bb7:                                              ; preds = %bb12
+  ret void
+
+bb12:                                             ; preds = %bb12, %bb
+  %tmp13 = phi i32 [ -47436, %bb ], [ %tmp15, %bb12 ]
+  %tmp14 = phi i32 [ 0, %bb ], [ %tmp42, %bb12 ]
+  %tmp15 = add i32 %tmp13, -1
+  %tmp16 = shl i32 %tmp15, 1
+  %tmp17 = sub i32 42831, %tmp16
+  %tmp19 = lshr i32 %tmp17, 1
+  %tmp20 = urem i32 %tmp19, 250
+  %tmp21 = add nsw i32 %tmp17, 0
+  %tmp22 = lshr exact i32 %tmp21, 1
+  store i32 %tmp22, i32* %p, align 4
+  %tmp26 = zext i32 %tmp20 to i64
+  store i64 %tmp26, i64* %p1, align 4
+  %tmp42 = add nuw nsw i32 %tmp14, 1
+  %tmp43 = icmp ugt i32 %tmp14, 717
+  br i1 %tmp43, label %bb7, label %bb12
+}