Page MenuHomePhabricator

[SCEV] Add option to forget everything in SCEV.
ClosedPublic

Authored by asbirlea on Apr 2 2019, 11:55 AM.

Details

Summary

Create a method to forget everything in SCEV.
Add a cl::opt and PassManagerBuilder option to use this in LoopUnroll.

Motivation: Certain Halide applications spend a very long time compiling in forgetLoop, and prefer to forget everything and rebuild SCEV from scratch.
Sample difference in compile time reduction: 21.04 to 14.78 using current ToT release build.
Testcase showcasing this cannot be opensourced and is fairly large.

The option disabled by default, but it may be desirable to enable by
default. Evidence in favor (two difference runs on different days/ToT state):

File Before (s) After (s)
clang-9.bc 7267.91 6639.14
llvm-as.bc 194.12 194.12
llvm-dis.bc 62.50 62.50
opt.bc 1855.85 1857.53

File Before (s) After (s)
clang-9.bc 8588.70 7812.83
llvm-as.bc 196.20 194.78
llvm-dis.bc 61.55 61.97
opt.bc 1739.78 1886.26

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Apr 2 2019, 11:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 2 2019, 11:55 AM
fhahn added a subscriber: fhahn.Apr 2 2019, 12:40 PM

Out of curiosity, would it be possible to provide a .bc file of such a program? Maybe there is some common structure where forgetting everything is faster or some heuristic we can use.

I'm looking to see if a reduced case I have can be open-sourced in a PR and have this patch point to it.

I tried to reduce the problem (bugpoint) before sending this out, hoping it would show some pathological case that it hits in SCEV, but it didn't seem to be the case. For the problem to persist, the testcase needs to remain very large, which seems to confirm the comment on forgetLoop: This call is potentially expensive for large loop bodies..

Here are the times I got for compiling the aggregated bitcode files for clang and a few others. Before is ToT, After is with -forget-scev-loop-unroll=true
File Before (s) After (s)
clang-9.bc 7267.91 6639.14
llvm-as.bc 194.12 194.12
llvm-dis.bc 62.50 62.50
opt.bc 1855.85 1857.53

The current test I have is not publishable, I'm still trying to get one.
In the mean time, the above results might motivate having this enabled by default.

Here are the times I got for compiling the aggregated bitcode files for clang and a few others. Before is ToT, After is with -forget-scev-loop-unroll=true
File Before (s) After (s)
clang-9.bc 7267.91 6639.14
llvm-as.bc 194.12 194.12
llvm-dis.bc 62.50 62.50
opt.bc 1855.85 1857.53

The current test I have is not publishable, I'm still trying to get one.
In the mean time, the above results might motivate having this enabled by default.

These numbers look great!

include/llvm/Transforms/Utils/UnrollLoop.h
66 ↗(On Diff #193338)

Unrelated to this change, but the parameter lists are getting really long here. What do you think about creating a struct holding all these params in a later change?

lib/Analysis/ScalarEvolution.cpp
6792 ↗(On Diff #193338)

What about LoopPropertiesCache?

6793 ↗(On Diff #193338)

forgetEverything is not a good name for this function since e.g. we're not forgetting UniqueSCEVs (and we shouldn't). Can we have a more specific name for this function and the boolean you're passing around? Perhaps: forgetAllLoops?

6796 ↗(On Diff #193338)

I also propose we should be explicit about what we're *not* clearing here (in the form of a comment) to not confuse future readers, and what the criteria should be to add a newly added cache to these of caches being cleared here.

lib/Transforms/Scalar/LoopUnrollPass.cpp
1135 ↗(On Diff #193338)

This didn't really parse, did you mean "only forget everything in the topmost loop"?

fhahn added a comment.Apr 4 2019, 1:25 PM

Here are the times I got for compiling the aggregated bitcode files for clang and a few others. Before is ToT, After is with -forget-scev-loop-unroll=true
File Before (s) After (s)
clang-9.bc 7267.91 6639.14
llvm-as.bc 194.12 194.12
llvm-dis.bc 62.50 62.50
opt.bc 1855.85 1857.53

The current test I have is not publishable, I'm still trying to get one.
In the mean time, the above results might motivate having this enabled by default.

Thank you very much for looking into it!

IIUC forgetTopmostLoop currently can be quite expensive for loops with lots of subloops/deeply-nested loops, where it has to visit all sub loops and selectively erase a bunch of stuff. And if we manage to unroll a large number of such loops, we have to invalidate most things anyways. Could that be the case in your test case?

asbirlea updated this revision to Diff 193978.Apr 5 2019, 3:29 PM
asbirlea marked 6 inline comments as done.

Address comments.

asbirlea added inline comments.Apr 5 2019, 3:30 PM
include/llvm/Transforms/Utils/UnrollLoop.h
66 ↗(On Diff #193338)

Ack, added to TODO list.

lib/Analysis/ScalarEvolution.cpp
6792 ↗(On Diff #193338)

Could I ask you to please double check I have not missed other caches?

6796 ↗(On Diff #193338)

That makes sense!
Might I ask for your suggestions on extending the comment I added, as to what else we are *not* clearing? I don't know enough about SCEV to fill that in.

IIUC forgetTopmostLoop currently can be quite expensive for loops with lots of subloops/deeply-nested loops, where it has to visit all sub loops and selectively erase a bunch of stuff. And if we manage to unroll a large number of such loops, we have to invalidate most things anyways. Could that be the case in your test case?

Yes, that's almost certain the case.

sanjoy accepted this revision.Apr 10 2019, 7:11 PM

lgtm

lib/Analysis/ScalarEvolution.cpp
6793 ↗(On Diff #193978)

Suggested comment:

This method should invalidate caches as if the following happened:

  • The trip count of all loops have changed arbitrarily.
  • Every llvm::Value has been updated in place to produce a different result .
This revision is now accepted and ready to land.Apr 10 2019, 7:11 PM
asbirlea edited the summary of this revision. (Show Details)Apr 12 2019, 12:04 PM
This revision was automatically updated to reflect the committed changes.