[llvm-dev] Late setting of SCEV NoWrap flags does bad with cache

[Sanjoy Das via llvm-dev]

Hi Max,

On Wed, Jan 24, 2018 at 10:03 PM, Maxim Kazantsev via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I want to raise a discussion about reasonability of late setting of
> nsw/nuw/nw flags to SCEV AddRecs through setNoWrapFlags method. A discussion
> about this have already happened in August last year, there was a concern
> about different no-wrap flags that come from different sequences of SCEV
> flags invocations. It was mentioned there that late setting of flags is
> actually a hack to save some compile time.
>
> Recently I've stumbled over a different problem related to this late flag
> setting. The problem is that current SCEV implementation caches a lot of
> data about SCEVs. In particular, information about ranges and loop backedge
> taken counts. A side effect of that is that if we had an AddRec like {1,+,1}
> and cached its range as [MIN_INT, MAX_INT+1), and then later found out that
> this recurrency provably has <nsw>, its cached range doesn't get updated. As
> well as ranges of all other SCEVs that depend on that. As result, we have a
> very weird behavior of SCEV that is unable to prove that sext({1,+,1}<nsw>)
> is a positive value just because it has outdated cached ranges.

Yes, this problem has come up several times and it is counter-intuitive.

Part of the problem is (I'm guessing, I wasn't there when SCEV was
written) that SCEV is tuned for C/C++ and for C/C++ add recurrences
are almost always nsw on construction so you don't have these, let's
say "phase ordering", issues.

However, for Java, I was under the impression that despite this
caching issue we are fairly effective at proving ranges.  Of course
"fairly effective" does not help if the one thing we don't optimize is
90% of an Important Benchmark(TM).

I see a couple of ways out of this:

  1. Eagerly compute nsw/nuw on AddRec construction.  I'd be happy
with this if you can show that we don't regress compile time.  Other
than the test-suite, you can probably ask for interesting compile time
benchmarks on this list.

  2. Don't cache ranges so much.  Especially for things like
sext({1,+,1}), just recomputing the ranges may not be significantly
worse than the densemap lookup, assuming the backedge taken count is
already computed.  Of course for complex SCEVs we should still cache
ranges, but for those perhaps we're okay with "locking in" a more
conservative result.  We could even return conservatives result for
recursion deeper than a certain depth, like we do for Values in
ComputeKnownBits. I like this philosophically since it reduces caching
(a lot of the complexity in SCEV is due to caching), but again, you'll
have to show that we don't regress compile time.

  3. Precise invalidation via use-lists -- add use lists to SCEV and
use that to precisely kick values out of caches as you infer NSW/NUW
etc.  We can optimize the representation of use lists by e.g. avoiding
keeping use lists for SCEVConstants and exploiting the fact that we
don't delete SCEVs so use lists don't need fast deletion.  Again,
you'll need to show compile time memory usage does not go up by very
much.

> You may find the example of such behavior if you re-enable the assertion
> from patch https://reviews.llvm.org/rL323309 . The test that was added with

For that case specifically:  I don't think such asserts are a good
idea, unless you've already checked SE.isKnownNonNegative(X) (i.e. not
only do you know that X is "supposed to be" non-negative, but you also
know that SCEV can prove it).  For instance see
https://bugs.llvm.org/show_bug.cgi?id=25170 where SCEV can prove "A-B"
is a constant but can't prove that "B-A" is a constant.  I think this
behavior is fine btw, SCEV is allowed to be arbitrarily conservative.

> My question is: do we still want to have this hack with late setting of
> nsw/nuw given that this flag does not give us any benefits in many real
> situations? What would you think?

We can't just remove it (because you'll regress the cases where it
does help), but we can replace it with something that is more
effective.

-- Sanjoy