feat: improve function return value tracking#6065
feat: improve function return value tracking#6065cyyynthia wants to merge 8 commits intorollup:masterfrom
Conversation
|
The latest updates on your projects. Learn more about Vercel for GitHub.
|
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## master #6065 +/- ##
==========================================
- Coverage 98.79% 98.78% -0.02%
==========================================
Files 271 271
Lines 10622 10699 +77
Branches 2840 2870 +30
==========================================
+ Hits 10494 10569 +75
- Misses 88 90 +2
Partials 40 40 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
Thank you for your contribution! ❤️You can try out this pull request locally by installing Rollup via npm install cyyynthia/rollup#function-return-valuesNotice: Ensure you have installed the latest nightly Rust toolchain. If you haven't installed it yet, please see https://www.rust-lang.org/tools/install to learn how to download Rustup and install Rust. or load it into the REPL: |
Performance report
|
lukastaegert
left a comment
There was a problem hiding this comment.
This PR does a lot of things, and the concept of locallyReachable makes me a little uneasy. Also, I do not fully understand this concept, is this meant as a "there is a chance this node might be included at some point"?
If, for instance, we would just take the literal value of all included return statements into account and then deoptimize if another return statement is included, would this deoptimize too often because the value is queried too early before any return statement is included?
Another point is that so far, I have avoided to track multiple return expressions out of fear of a performance regression. Below is a (completely artificial) example that demonstrates this. At least for me, this will basically make the browser hang for a long time. Removing the pr=6065& from the URL, i.e. using production Rollup, will make it load quickly:
As this is an artificial example, many code-bases will not have this issue. But some will, or at least they will be noticeably slowed, especially if they have some functions with a lot of return statements. To that end, I would make this feature opt-in, e.g. as treeshake.trackAllReturnValues, but add this to the treeshake.preset: "smallest" preset.
So in general, this is how I would propose to proceed
- Look into aborting binding in a separate PR.
- Tracking multiple return values shop be opt-in via parameter
- Can we implement tracking multiple return statements without the additional "isLocallyReachable" static analysis? While the logic is not too complicated, I am worried that it is another separate layer of executed code path analysis that is only used for this one feature, where bugs may be noticed very late, and which will not benefit from improvements in other areas. Another way to do this could be to start tracking return statements the first time either
hasEffects,includeorincludePathare called on a return statement, as that is equivalent to "we know this return statement is in an executed code path". This is also the semantic we use forapplyDeoptimizationsand actually, this could just become another "deoptimization" to perform on return statements I theirapplyDeoptimizationsmethod, i.e. add a return value. Now the important thing would be to make sure that when a return statement is added and a consumer already queried the literal return value of the function (tracked via theoriginparameter), then that consumer is deoptimized. However, I hope this is not a wild goose chase.
What do you think?
| if (!this.blockEndReached && node.haltsCodeFlow()) { | ||
| this.blockEndReached = true; | ||
| this.lastReachableBlock = index; | ||
| } |
There was a problem hiding this comment.
Interesting question if we can just stop binding here. I first thought "no" because there can be hoisted declarations after such a point, but those do not need binding anyway, so this might actually be fine.
There was a problem hiding this comment.
I initially implemented it that way, but it did cause issues with function declarations in effectively unreachable blocks that were no longer properly dealt with iirc.
| haltsCodeFlow(allowOptimizations?: boolean): boolean { | ||
| for (const node of this.body) { | ||
| if (node.haltsCodeFlow(allowOptimizations)) return true; | ||
| } | ||
| return false; | ||
| } |
There was a problem hiding this comment.
For effect checks and inclusion, we already have a different solution that effectively does the same thing, but slightly differently. This is what the execution context and "brokenFlow" are designed for:
rollup/src/ast/ExecutionContext.ts
Line 15 in 59c16b9
This can effectively track how far e.g. a labelled break or a return statement interrupt the code flow. I am not sure we should build a different mechanism in parallel.
Admittedly, this solution is not "simpler" than your solution as you would still need to write some logic for the bind handler on several different nodes. Just do a full text search for brokenFlow to see what would need to be touched. This logic relies on a context that is passed to each call of include or hasEffects which tracks if we are in reachable code and which labels we have, basically what is in the ControlFlowContext interface. This can then abort hasEffects checks in BlockStatements and SwitchCases
If we go there, I would hope we can move this to a separate PR to make the review easier and allow a separate release.
There was a problem hiding this comment.
I initially used that, but since it relies on hasEffects which is a more expensive function and does not really allow granularity with whether to take optimizations into account or not. I also feared the more complex rules around break statements and continue statements would make it quite a lot more difficult to map to the concept of reachability, since breaking out of a loop and returning in a loop have different code reachability implications that'd be difficult to distinguish.
Initially I wanted to use treeshaking information for local reachability, but it's actually not going to work well because then it'd mean getting accurate treeshaking information requires accurate treeshaking information, so we have a chicken and egg problem.
So my idea here was to make a pessimistic, lower-quality and coarse check that'd be cheap enough to call without fear of harming performance too much, that can be used to solve that issue. Given Rollup's design, it's impossible to assume a node included until proven dead code, since it works the other way around and there's no way to exclude a node once it's been included.
Another concern is that I'm not sure whether the hasEffects check is going to be as exhaustive as I'd like it to be, especially if it aborts early because it knows there are effects quite a bit higher up in the hierarchy and doesn't bother exploring further (which would be a correct behavior given what it tries to establish, but that wouldn't give me the information I'm looking for I think... 🤔)
There was a problem hiding this comment.
Hmm, another issue seems to be that if return statements start to get included, that means we already gave up on the idea of getting rid of the function as a whole, meaning if we end up being able to inline all the places where it's called it'll still be included in the bundle (#5063)
There was a problem hiding this comment.
Hm, you're definitely right that this kind of performance regression is unacceptable (regardless of the exotic/synthetic nature of the scenario). I convinced myself along the way that it shouldn't be too much of a performance issue but I overlooked the exponential growth of return values in deep recursive function call chains that can definitely show up in the real world.
Having full-depth search opt-in seems a good idea. I'm wondering if depth control would allow for a good balance between performance and output quality (by default have a depth of only 1 or 2, and in the smallest preset have a depth of Infinity; i.e. exhaustive return value search.
It's very likely that performance can be improved for some scenarios through caching and smarter exploration, perhaps beyond just this use-case if getLiteralValue* gets smarter. I'll explore this further :)
| if (!this.blockEndReached && node.haltsCodeFlow()) { | ||
| this.blockEndReached = true; | ||
| this.lastReachableBlock = index; | ||
| } |
There was a problem hiding this comment.
I initially implemented it that way, but it did cause issues with function declarations in effectively unreachable blocks that were no longer properly dealt with iirc.
| haltsCodeFlow(allowOptimizations?: boolean): boolean { | ||
| for (const node of this.body) { | ||
| if (node.haltsCodeFlow(allowOptimizations)) return true; | ||
| } | ||
| return false; | ||
| } |
There was a problem hiding this comment.
I initially used that, but since it relies on hasEffects which is a more expensive function and does not really allow granularity with whether to take optimizations into account or not. I also feared the more complex rules around break statements and continue statements would make it quite a lot more difficult to map to the concept of reachability, since breaking out of a loop and returning in a loop have different code reachability implications that'd be difficult to distinguish.
Initially I wanted to use treeshaking information for local reachability, but it's actually not going to work well because then it'd mean getting accurate treeshaking information requires accurate treeshaking information, so we have a chicken and egg problem.
So my idea here was to make a pessimistic, lower-quality and coarse check that'd be cheap enough to call without fear of harming performance too much, that can be used to solve that issue. Given Rollup's design, it's impossible to assume a node included until proven dead code, since it works the other way around and there's no way to exclude a node once it's been included.
Another concern is that I'm not sure whether the hasEffects check is going to be as exhaustive as I'd like it to be, especially if it aborts early because it knows there are effects quite a bit higher up in the hierarchy and doesn't bother exploring further (which would be a correct behavior given what it tries to establish, but that wouldn't give me the information I'm looking for I think... 🤔)
still not viable as enabled-by-default, but SIGNIFICANTLY better than exponential runtime
5de9123 to
5d16167
Compare
5d16167 to
cf8e36c
Compare
5369863 to
96b5453
Compare
|
Hi, I am somewhat I slightly lost track of this. What is the current state here, is this currently in a releasable state from your side? Then I would focus on finishing the review next. |
|
Hi! The state of things hasn't moved much since your last review and the concerns you raised still are valid. I tried a bunch of things locally, with more often than not more issues created than solved... And then I ran out of free time to mess with this PR :( The main issue remains that the information I need for the reachability check is not known prior to the inclusion process being in progress, at which point it is too late to react (since Rollup works via an additive only strategy). This is the key to solve #5063 robustly, and is quite important to make deep function return evaluation worth the effort. The PR can likely be split in 2 separate ones; one adding the deep function return value evaluation capabilities, the other making reachability analysis smarter such that treeshaking can have a "recursive" effect without resorting to treeshaking over and over until we have a stable result which would be prohibitively expensive >:) There are some low hanging fruits that can be cherry picked from the PR and improves some situations too, such as making blocks return undefined (instead of UnknownValue) through their implicit return statement. |
|
Thanks for the quick response! I think I will leave it like this for a little longer from my side and focus on getting Rollup 5 ready, there is a lot still to do. After happy I am happy to invest more time here. But feel free to drive this forward in the meantime yourself. |
This PR contains:
Are tests included?
Breaking Changes?
List any relevant issue numbers:
Description
This PR improves the way return values are resolved inside function calls. It does so via 3 changes:
MultiExpressionnode. It has been expanded to allow resolving literal values if all paths agree on a specific value, trying to resolve its truthiness if there are different values being returned.