SCEV incorrectly marks certain expressions as nsw

[sanjoy]

Summary

Unfortunately, I could not come up with a test case for this one; but I don't think getPreStartForSignExtend can assume AR is nsw -- there is one place in scalar evolution that calls getSignExtendAddRecStart(AR, ...) without proving that AR is nsw

(line 1564)

  OperandExtendedAdd =
    getAddExpr(WideStart,
               getMulExpr(WideMaxBECount,
                          getZeroExtendExpr(Step, WideTy)));
  if (SAdd == OperandExtendedAdd) {
    // If AR wraps around then
    //
    //    abs(Step) * MaxBECount > unsigned-max(AR->getType())
    // => SAdd != OperandExtendedAdd
    //
    // Thus (AR is not NW => SAdd != OperandExtendedAdd) <=>
    // (SAdd == OperandExtendedAdd => AR is NW)

    const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);

    // Return the expression with the addrec on the outside.
    return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
                         getZeroExtendExpr(Step, Ty),
                         L, AR->getNoWrapFlags());
  }
}

[hfinkel]

Indeed, that call site seems inconsistent with the stated precondition of getPreStartForSignExtend. Not only do we not prove NSW there before calling getSignExtendAddRecStart (which calls getPreStartForSignExtend), but in all cases where we could prove NSW on AR, we return prior to reaching that callsite.

However, is this the right fix? The condition you're checking is a stated pre-condition of the function. Is this the only dependence on that pre-condition? Maybe we should add an assert, and a check in the caller?

lib/Analysis/ScalarEvolution.cpp

1397 ↗

(On Diff #19964)

Can you run the test suite or self hosting with an assert here and see if you can find a test case?

Otherwise, we're just ++(technical dept);

[sanjoy]

The condition you're checking is a stated pre-condition of the function. Is this the only dependence on that pre-condition?

Yes, as far as I can tell. The three checks explicitly test that PreStart + Step does not overflow without depending on the no-wrap-ness of AR. The other SCEV functions this calls out to may potentially do a better job if AR is in fact nsw but that is not required for correctness except in the case this patch fixes. This is why I think the right fix is to simply relax the precondition (I've changed the comment to reflect that).

Clang bootstrap (Release+Asserts) fails to find a failure. I don't find that surprising -- we'd essentially have to have a non-nsw AR such that sext(AR->getStart()) + BECount * zext(AR->getStep()) does not overflow, while sext(AR->getStart()) + BECount * sext(AR->getStep()) does (this part is easy) and PreStart is an scev add expression that does not overflow (this part is hard if we want the first property). The only obvious way to get the second property is to make PreAR of the form C1 + C2 * Var (with some constraints on C1 and C2), but having PreStart in that form makes it difficult for scev to prove that sext(AR->getStart()) + BECount * zext(AR->getStep()) does not overflow. Frankly, it is possible that the bug this patch fixes is completely dormant at this time in SCEV.

[atrick]

The function's precondition no longer holds after one of your other fixes. It's good that you noticed that.

In another one of your fixes it looks like you added this check:

if (PreAR && PreAR->getNoWrapFlags(SCEV::FlagNSW) &&

Instead of

if (PreAR && AR->getNoWrapFlags(SCEV::FlagNSW) &&

I think the later check, which is what you have in this patch, preserves the original optimization (which unfortunately has no unit tests because it only affects LSR).

You could add an assert and avoid calling this when we don't have AR<nsw>. I'm not sure it could have any effect on optimization. At any rate, the fix you have in this patch actually seems more clear, as long as the comments aren't misleading.

...canonicalizing sext within SCEV is a really horrible business. Sorry!

[sanjoy]

I think the later check, which is what you have in this patch, preserves the original optimization (which unfortunately has no unit tests because it only affects LSR).

I'm not sure I understand what the "original optimization" is in this
context. I assume the previous change you're talking about is this:
http://reviews.llvm.org/D7331 -- that's a separate fix as far as I can
tell.

• Sanjoy

[atrick]

Correct. Never mind my comment about the PreRA/nsw check you added earlier -- that check was already there to begin with.

The additional AR/nsw check is only needed for the second condition, which is exactly what you've done. This patch is good as-is.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

static const SCEV *getOverflowLimitForStep(const SCEV *Step,
   if (SE->isKnownNegative(Step)) {
     *Pred = ICmpInst::ICMP_SGT;
     return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
                        SE->getSignedRange(Step).getSignedMin());
   }
   return nullptr;
 }
 
-// The recurrence AR has been shown to have no signed wrap. Typically, if we can
-// prove NSW for AR, then we can just as easily prove NSW for its preincrement
-// or postincrement sibling. This allows normalizing a sign extended AddRec as
-// such: {sext(Step + Start),+,Step} => {(Step + sext(Start),+,Step} As a
-// result, the expression "Step + sext(PreIncAR)" is congruent with
-// "sext(PostIncAR)"
+// The recurrence AR has been shown to have no signed wrap or something close to
+// it.  Typically, if we can prove NSW for AR, then we can just as easily prove
+// NSW for its preincrement or postincrement sibling. This allows normalizing a
+// sign extended AddRec as such: {sext(Step + Start),+,Step} => {(Step +
+// sext(Start),+,Step} As a result, the expression "Step + sext(PreIncAR)" is
+// congruent with "sext(PostIncAR)"
 static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
                                             Type *Ty,
                                             ScalarEvolution *SE) {
   const Loop *L = AR->getLoop();
   const SCEV *Start = AR->getStart();
   const SCEV *Step = AR->getStepRecurrence(*SE);
 
   // Check for a simple looking step prior to loop entry.
static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
   // 2. Direct overflow check on the step operation's expression.
   unsigned BitWidth = SE->getTypeSizeInBits(AR->getType());
   Type *WideTy = IntegerType::get(SE->getContext(), BitWidth * 2);
   const SCEV *OperandExtendedStart =
     SE->getAddExpr(SE->getSignExtendExpr(PreStart, WideTy),
                    SE->getSignExtendExpr(Step, WideTy));
   if (SE->getSignExtendExpr(Start, WideTy) == OperandExtendedStart) {
     // Cache knowledge of PreAR NSW.
-    if (PreAR)
+    if (PreAR && AR->getNoWrapFlags(SCEV::FlagNSW))
       const_cast<SCEVAddRecExpr *>(PreAR)->setNoWrapFlags(SCEV::FlagNSW);
     // FIXME: this optimization needs a unit test
     DEBUG(dbgs() << "SCEV: untested prestart overflow check\n");
     return PreStart;
   }
 
   // 3. Loop precondition.
   ICmpInst::Predicate Pred;