This is an archive of the discontinued LLVM Phabricator instance.

SCEV incorrectly marks certain expressions as nsw
ClosedPublic

Authored by sanjoy on Feb 14 2015, 12:54 AM.

Details

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());
  }
}

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 19964.Feb 14 2015, 12:54 AM
sanjoy retitled this revision from to SCEV incorrectly marks certain expressions as nsw.
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: atrick, hfinkel.
sanjoy added a subscriber: Unknown Object (MLST).
hfinkel edited edge metadata.Feb 16 2015, 2:15 AM

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);

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 accepted this revision.Feb 16 2015, 11:35 PM
atrick edited edge metadata.

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!

This revision is now accepted and ready to land.Feb 16 2015, 11:35 PM

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

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.

This revision was automatically updated to reflect the committed changes.