[SCEV] Removed an unnecessary assertion in SCEV.

[Yangguang]

Summary

The assertion in computeExitLimitFromCondFromBinOp() is meant to check that when the the exit condition is in select form, we would always return a backedge taken count of zero (BECount->isZero()) if the exit limit for the first operand is zero (EL0.ExactNotTaken->isZero()).

If the exit condition is in AND/OR form, it is okay to return BECount as Umin(EL0.ExactNotTaken, EL1.ExactNotTaken) since AND/OR is poison-safe. This is not the case if the the exit condition is in select form.

So the correct assertion is the following

assert(isa<BinaryOperator>(ExitCond) || !EL0.ExactNotTaken->isZero() ||
             BECount->isZero());

which means if ExitCond is in AND/OR form, nothing needs to be checked further. Otherwise (it is in select form), and we will need to return a backedge taken count of zero if the exit limit for the first operand is zero.

With the current assert, if if ExitCond is in select form, the condition in the assert always returns true due to !isa<BinaryOperator>(ExitCond) and the check for !EL0.ExactNotTaken->isZero() || BECount->isZero()) is never triggerred, which is not what the assert meant to be.

Dropping the first check so the assertion cover ExitCond in both AND/OR form and select form.

---

As suggested in the comment I removed the whole assertion since the select form is handled in ScalarEvolution::getSequentialMinMaxExpr.

[lebedev.ri]

Test?

[Yangguang]

In D122835#3419988, @lebedev.ri wrote:

Test?

I can't create a test that fails the original assertion. When the ExitCond is NOT a BinaryOperator (which means it's in select form/short-circuit form), the original assert will always pass and we won't need to do the next two checks. But according to the comment above the assertion and the original design for the assertion, we should be checking the next two conditions when the ExitCond is in select form. I updated the summary, please refer for more info.

[lebedev.ri]

In D122835#3420684, @Yangguang wrote:

In D122835#3419988, @lebedev.ri wrote:

Test?

I can't create a test that fails the original assertion. When the ExitCond is NOT a BinaryOperator (which means it's in select form/short-circuit form), the original assert will always pass and we won't need to do the next two checks. But according to the comment above the assertion and the original design for the assertion, we should be checking the next two conditions when the ExitCond is in select form. I updated the summary, please refer for more info.

I mean the test on which the unfixed assertion fires.
Though, i suspect that the assertion is still wrong, and the fix should be to just drop the !isa<BinaryOperator>(ExitCond) || part.

[Yangguang]

In D122835#3420698, @lebedev.ri wrote:

In D122835#3420684, @Yangguang wrote:

In D122835#3419988, @lebedev.ri wrote:

Test?

I can't create a test that fails the original assertion. When the ExitCond is NOT a BinaryOperator (which means it's in select form/short-circuit form), the original assert will always pass and we won't need to do the next two checks. But according to the comment above the assertion and the original design for the assertion, we should be checking the next two conditions when the ExitCond is in select form. I updated the summary, please refer for more info.

I mean the test on which the unfixed assertion fires.
Though, i suspect that the assertion is still wrong, and the fix should be to just drop the !isa<BinaryOperator>(ExitCond) || part.

Fixed as suggested and changed the comment accordingly. Please check if it make sense.

[lebedev.ri]

This seems correct to me, but any chance for a test?

[Yangguang]

In D122835#3423347, @lebedev.ri wrote:

This seems correct to me, but any chance for a test?

Whenever EL0.ExactNotTaken==0, getUMinFromMismatchedTypes() will always return 0 for BECount. I don't see a way to generate a test case that fires the assertion.
But since ExitCond in AND/OR form is now also covered by the assertion, do you think it's helpful to have a test case in which ExitCond is in AND/OR form and won't fire the assertion when EL0.ExactNotTaken==0? (Note: we already have similar test case for ExitCond in select form under llvm\test\Analysis\ScalarEvolution\exit-count-select.ll.)

[Yangguang]

In D122835#3423481, @Yangguang wrote:

In D122835#3423347, @lebedev.ri wrote:

This seems correct to me, but any chance for a test?

Whenever EL0.ExactNotTaken==0, getUMinFromMismatchedTypes() will always return 0 for BECount. I don't see a way to generate a test case that fires the assertion.
But since ExitCond in AND/OR form is now also covered by the assertion, do you think it's helpful to have a test case in which ExitCond is in AND/OR form and won't fire the assertion when EL0.ExactNotTaken==0? (Note: we already have similar test case for ExitCond in select form under llvm\test\Analysis\ScalarEvolution\exit-count-select.ll.)

@lebedev.ri What do you think of the idea of adding test case for AND/OR form that is also covered by the assertion after change?

[Yangguang]

@aqjune Could you help review this patch? The original assertion is wrong because it won't fire when ExitCond is in select form, the exit limit for the first operand is zero, and the backedge taken count is NOT zero. This patch fix the assertion and make it cover the case for AND/OR form as well.

[Yangguang]

@nikic @mkazantsev @reames Could you please help review the patch. Any feedback would be appreciated.

[nikic]

I think you can just delete the whole assertion. The invariant it checks is no longer relevant now that we have umin_seq nodes.

[aqjune]

Hi, sorry for my delay. The old assertion seems problematic.

+1 for totally removing the assertion as well, because in the select case the Sequential flag must be set, calling ScalarEvolution::getSequentialMinMaxExpr at last. The assert condition was for dealing with select form however.
Also, the condition (3) even seems to be removed now; originally it was introduced here: D93882, but now gone.

[reames]

LGTM, the simplified assert looks correct to me. Removing complexity which is no longer needed is always good.

[Yangguang]

Removed the whole assertion as suggested.

[Yangguang]

In D122835#3489265, @reames wrote:

LGTM, the simplified assert looks correct to me. Removing complexity which is no longer needed is always good.

Sorry, I just deleted the whole assertion as suggested by the reviews. Just right after you accepted the patch. Could you please double check if the correct version is accepted?

[nikic]

LG

[nikic]

Though for the title, I'd suggest invalid -> unnecessary. The assertion itself is fine, there's just no reason to check it here.

[reames]

My LGTM specifically applied to the prior version of the patch. I do see value in the assert, and would prefer that version I don't feel strongly about this, so feel free to land on nikic's LG.

[Yangguang]

In D122835#3489307, @nikic wrote:

Though for the title, I'd suggest invalid -> unnecessary. The assertion itself is fine, there's just no reason to check it here.

Thanks! Fixed as suggested.

[Yangguang]

In D122835#3489313, @reames wrote:

My LGTM specifically applied to the prior version of the patch. I do see value in the assert, and would prefer that version I don't feel strongly about this, so feel free to land on nikic's LG.

Thanks for the feedback!

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::computeExitLimitFromCondFromBinOp(
   if (EitherMayExit) {
     // Both conditions must be same for the loop to continue executing.
     // Choose the less conservative count.
     if (EL0.ExactNotTaken != getCouldNotCompute() &&
         EL1.ExactNotTaken != getCouldNotCompute()) {
       BECount = getUMinFromMismatchedTypes(
           EL0.ExactNotTaken, EL1.ExactNotTaken,
           /*Sequential=*/!isa<BinaryOperator>(ExitCond));
-
-      // If EL0.ExactNotTaken was zero and ExitCond was a short-circuit form,
-      // it should have been simplified to zero (see the condition (3) above)
-      assert(!isa<BinaryOperator>(ExitCond) || !EL0.ExactNotTaken->isZero() ||
-             BECount->isZero());
     }
     if (EL0.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL1.MaxNotTaken;
     else if (EL1.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL0.MaxNotTaken;
     else
       MaxBECount = getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken);
   } else {