This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Add missing cache queries
ClosedPublic

Authored by ekatz on Nov 11 2019, 12:14 PM.

Details

Summary

Calculating SCEVs can be cumbersome, and may take very long time (even hours, for very long expressions). To prevent recalculating expressions over and over again, we cache them.
This change add cache queries to key positions, to prevent recalculation of the expressions.

Fix PR43571.

Diff Detail

Event Timeline

ekatz created this revision.Nov 11 2019, 12:14 PM

compile time numbers? how this speeds up eg. bootstrap of clang?

ekatz added a comment.Nov 12 2019, 3:13 AM

compile time numbers? how this speeds up eg. bootstrap of clang?

It seems like a simple performance boost, but this actually fixes PR43571, and I quote, "...it's been nearly 10hrs".
With this change it takes a less than a second.

fhahn added a subscriber: fhahn.Nov 12 2019, 2:02 PM

Can you explain where the claimed speed-up is coming from? We were missing cases in the caching before? Is it simply not rebuilding the folding set node multiple times? Something else?

This change appears to have a mix of functional change, and refactoring intermixed. It would make review much easier if you were to split them apart. In particular, a couple of suggestions:

  1. The getOrCreateX functions appear to be easily implementable with the new infrastructure. Please do so, as this avoids changes to the (delicate!) flag handling which will otherwise slow review.
  2. Separate any removal/movement of caching routine calls into a separate change if possible. (Not sure this is possible, which is the source of confusion.)
llvm/include/llvm/Analysis/ScalarEvolution.h
1906

Having the insert point as part of the key seems odd structurally. I'm also concerned about invalidation if the cache is otherwise modified between setting the IP and using it.

1913

Looks like this forward declare can be in the cpp.

llvm/lib/Analysis/ScalarEvolution.cpp
1271

It seems natural this should be before the rewrite rules?

ekatz updated this revision to Diff 230815.Nov 24 2019, 11:07 AM
ekatz retitled this revision from [SCEV] Optimize SCEV cache usage to [SCEV] Add missing cache queries.
ekatz edited the summary of this revision. (Show Details)

Remove unrelated changes. Now only the missing cache queries are present in the patch.

ekatz added a comment.Dec 2 2019, 9:30 AM
This comment was removed by ekatz.
ekatz added a comment.Dec 11 2019, 1:39 PM
This comment was removed by ekatz.
ekatz added a comment.Dec 23 2019, 7:21 PM
This comment was removed by ekatz.
ekatz added a comment.Jan 2 2020, 6:42 AM
This comment was removed by ekatz.
ekatz added a comment.Jan 20 2020, 4:57 AM

@reames any comment on the change?

mkazantsev added inline comments.Jan 30 2020, 3:39 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2939

This code piece is reocurring over the code. Please factor out into a separate method that takes ArrayRef<Value *> or something.

mkazantsev added inline comments.Jan 30 2020, 3:51 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2461

This is not correct unless you also add no wrap flags into it.

This comment was removed by mkazantsev.
mkazantsev added a comment.EditedJan 30 2020, 3:59 AM

Your code basically duplicates functionality of getOrCreateAddExpr and such, with only difference that you don't create a new SCEV if the lookup failed. I think what you really want to do is to refector it, separating lookup from creation, call the lookup in the beginning and if it succeeded, just return it. That would make sense.

Do you have a simple test demonstrating a claimed speedup?

mkazantsev added inline comments.Jan 30 2020, 4:08 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2461

See how it's done in getOrCreateAddExpr.

ekatz added a comment.Feb 6 2020, 3:19 AM

Do you have a simple test demonstrating a claimed speedup?

Yes. As described in the summary - this solves bug PR43571.
Please refer to https://bugs.llvm.org/show_bug.cgi?id=43571#c1, to test/reproduce.

ekatz marked 2 inline comments as done.Feb 6 2020, 4:05 AM
ekatz added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
2461

Will be fixed.

2939

I'll change it to use findExistingSCEVInCache instead.

ekatz updated this revision to Diff 242859.Feb 6 2020, 4:09 AM

Fixed noted issues.

loladiro added inline comments.Feb 25 2020, 12:52 PM
llvm/lib/Analysis/ScalarEvolution.cpp
2455

I know we do this in a few other places, but why is this legal? Isn't it possible we're still using the old SCEV somewhere, but without the flags?

ekatz marked an inline comment as done.Feb 25 2020, 11:09 PM
ekatz added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
2455

That's a question I also had.. I am not an expert of this code, but I wanted to be consistent with all other places, where this flag is set on the cached value.
Maybe someone more familiar with the code can elaborate.
I guess you can raise that question in llvm-dev, but if it is a bug, then we should open a separate one - specific for this.

mkazantsev accepted this revision.Mar 13 2020, 1:49 AM

Looks good. Sorry for long delay.

llvm/lib/Analysis/ScalarEvolution.cpp
2455

This has been a weird exception from SCEV immutability for a long enough time. The idea is that all SCEVs should be the same in all places of the program. It means that if in one place we can guarantee nsw for some addition, it should affect other places too. There have been discussions about how to get rid of it, but afaik we don't currently have a conclusive decision. The best way of action here is to follow the existing model.

This revision is now accepted and ready to land.Mar 13 2020, 1:49 AM
This revision was automatically updated to reflect the committed changes.

Please revert; also broke builds of the Linux kernel: https://bugs.llvm.org/show_bug.cgi?id=45195