[SCEV] Return zero from computeConstantDifference(X, X)

[n.bozhenov]

Summary

Without this patch computeConstantDifference returns None for cases like
these:

computeConstantDifference(%x, %x)
computeConstantDifference({%x,+,16}, {%x,+,16})

[lebedev.ri]

Test?

[n.bozhenov]

In D65474#1607075, @lebedev.ri wrote:

Test?

I agree that it would be nice to have a test for this, but I failed to find a way to test it. I would appreciate it if you could suggest how I could test the result of computeConstantDifference method. Please, keep in mind that the method is private.

Alternatively, we could commit this patch without a dedicated test, as the code is trivial. This piece of code is executed multiple times when running make check (about 400 lit tests). It doesn't change the observed behavior, though.

We use computeConstantDifference in some downstream code, and I was surprised to find out that it fails to compute (X - X) difference, unless X is a SCEVAddExpr.

[sanjoy]

We use computeConstantDifference in some downstream code, and I was surprised to find out that it fails to compute (X - X) difference, unless X is a SCEVAddExpr.

Can you use getMinusSCEV instead (which should DTRT)?

This looks like a small change, having many such cases (especially without unit tests) makes it difficult to refactor code confidently.

[n.bozhenov]

In D65474#1607285, @sanjoy wrote:

We use computeConstantDifference in some downstream code, and I was surprised to find out that it fails to compute (X - X) difference, unless X is a SCEVAddExpr.

Can you use getMinusSCEV instead (which should DTRT)?

This looks like a small change, having many such cases (especially without unit tests) makes it difficult to refactor code confidently.

Hi Sanjoy,

What I need is to check if two arbitrary SCEV expressions are constant distance apart or not, and compute that difference. That's exactly what computeConstantDifference does (except for the (%x - %x) case). I would be ok to use getMinusSCEV, but it does not do the right thing unfortunately. Given {%x, +, 1}<loop1> and {%x, +, 1}<loop2>, getMinusSCEV crashes instead of returning SCEVCouldNotCompute. And I am not aware of any existing API that checks whether two SCEVs are safe to subtract or not.

[lebedev.ri]

In D65474#1607424, @n.bozhenov wrote:

In D65474#1607285, @sanjoy wrote:

We use computeConstantDifference in some downstream code, and I was surprised to find out that it fails to compute (X - X) difference, unless X is a SCEVAddExpr.

Can you use getMinusSCEV instead (which should DTRT)?

This looks like a small change, having many such cases (especially without unit tests) makes it difficult to refactor code confidently.

Hi Sanjoy,

What I need is to check if two arbitrary SCEV expressions are constant distance apart or not, and compute that difference. That's exactly what computeConstantDifference does (except for the (%x - %x) case). I would be ok to use getMinusSCEV, but it does not do the right thing unfortunately. Given {%x, +, 1}<loop1> and {%x, +, 1}<loop2>, getMinusSCEV crashes instead of returning SCEVCouldNotCompute. And I am not aware of any existing API that checks whether two SCEVs are safe to subtract or not.

That already sounds like a test.

[fhahn]

IMO it would make sense to add isolated unit tests to llvm/unittests/Analysis/ScalarEvolutionTest.cpp for such behavior. It should be easy to test there. I *think* there should be no harm in making ScalarEvolutionTest a friend of ScalarEvolution to test private members.

[n.bozhenov]

I am afraid implementing a test through friendship would be pretty cumbersome.
ScalarEvolutionsTest performs checks inside lambdas, while the friendship does
not propagate inside lambdas.

A more straightforward approach would be to make computeConstantDifference
public. Please, check the updated patch with a unit test.

[sanjoy]

Let's make this a friend function, I'm already not super happy with how wide SCEV's API is. You can make the diff lambda a member function of ScalarEvolutionsTest to make this work.

Other than that lgtm.

[n.bozhenov]

Thanks for the suggestion, Sanjoy. Please, review the updated patch.

[sanjoy]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

   return true;
 }
 
 Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More,
                                                            const SCEV *Less) {
   // We avoid subtracting expressions here because this function is usually
   // fairly deep in the call stack (i.e. is called many times).
 
+  // X - X = 0.
+  if (More == Less)
+    return APInt(getTypeSizeInBits(More->getType()), 0);
+
   if (isa<SCEVAddRecExpr>(Less) && isa<SCEVAddRecExpr>(More)) {
     const auto *LAR = cast<SCEVAddRecExpr>(Less);
     const auto *MAR = cast<SCEVAddRecExpr>(More);
 
     if (LAR->getLoop() != MAR->getLoop())
       return None;
 
     // We look at affine expressions only; not for correctness but to keep