[L] Change in dart/sdk[main]: [dart2wasm] Prune library imports after TFA for better deferred modul...
Ömer Ağacan (Gerrit)
Ömer Ağacan voted and added 17 comments![]( "Open in Gerrit")
Votes added by Ömer Ağacan
| Code-Review | +1 |
17 comments
I think the overall idea makes sense. It's probably too much work to maintain a minimal set of improts as you do transformations in the front-end or TFA (there may be many small transformations that need to update import lists all the time, and accurately).
Instead of that having one pass after all the transformations are done is easier to implement, maintain, keep correct etc. as there will be one place where you deal with the imports (instead of many in each transformation).
the ladder "statically". Other uses of `Reference`s from otherladder --> latter
// procedure. This can have a varity of reasons:How did those libraries without a module work before?
// but unused).What is RTA?
"less precised" --> "less precise"
// Copyright (c) 2025, the Dart project authors. Please see the AUTHORS fileEverything in this library can be made private other than `unusedDeferredLibraryPrefix` and `pruneLibraryDependencies`.
Makes it easier to see what's the public interface and what are implementation details.
// -> The main wasm module has all RTT information atmBy RTT do you mean the Wasm types? (structs, rec groups etc.)
Or is this some Dart-level thing that the main module includes?
// -> No need to import a library to use classes from it in types.This is because the structs etc. need to be added to the using module anyway, because we can't import types?
void pruneLibraryDependencies(LibraryIndex libraryIndex, Component component) {Does this modify the kernels other than the `Library.dependencies` members? It may be helpful to document what it's modifying.
final collector = Collector(library, constantToLibrarySet);You could initialize the collector in `ImportPruner` to make it clear that it's per pruner and can't (or shouldn't) be shared with different pruners.
Actually it looks like you only need the `usedLibraries`, so I think it would be even better to just pass `collector.usedLibraries` to `ImportPruner`. Makes dependencies smaller (pruner depends on a set of libs instead of a `Collector` class with other things)
}Does this need to visit all of the libraries? From the comment above "We import the library containing the definition of a [Reference] and not e.g. a library that may re-export it" it looks like we replace transitive imports with direct imports. So I think some of the libraries may end up being unused?
If that's the case, would it make sense to start from the main library and only process the libraries that are used?
// The new (possibly smaller) set of imports.Can it ever be larger?
if (!dep.isImport) {I checked the definition but I can't tell what `isImport` is.
I think this line checks for exported dependencies, but don't we replace transitive imports with direct imports, and doesn't that mean re-exports become unused?
dep.name;Is this line missing some parts? If not it can be removed.
removedDeps.add(dep);`removedDeps` seems to be unused? Should it be used?
// IgnoreMight be helpful to refer to your documentation above here. Something like "Ignore due to (a) above". (same below in `visitSupertype`)
}It may be just me but I can't figure out what this is doing.
Couldn't you start with an empty set for every constant, and add the things added to the empty set to the parent call's set?
E.g something like:
```
final childrenLibrariesSet = ConstantToLibrarySet(); // also always initialize the `currentSet` as empty set
constant.visitChildren(childrenLibrariesSet); // collect libraries of child nodes
currentSet.addAll(childrenLibrariesSet.currentSet); // add libraries of child nodes to current set
map[constant] = Set.from(currentSet); // current constant's libraries = child libraries + current libraries
```
I also can't tell which sets are shared here and which are their own copies. There's
- savedSet
- transitiveSet
- currentSet
and a bunch of assignments between them.
Feel free to ignore if it's clear to you.
if (dep.isExport) {Similar to my comment above, if we replace all transitive imports with direct imports I think this condition should be gone? (or maybe I misunderstand what `isExport` is, I assume it's re-export of another library)
Related details
- Martin Kustermann
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Martin Kustermann (Gerrit)
Martin Kustermann added 17 comments![]( "Open in Gerrit")
Thanks, Omer!
I've tried to address all comments.
I've also added the test (see the removed code in main module after this CL in : https://dart-review.googlesource.com/c/sdk/+/464901/11..12/pkg/dart2wasm/test/ir_tests/deferred.constant.type_use.wat)
the ladder "statically". Other uses of `Reference`s from otherMartin Kustermannladder --> latter
Done
How did those libraries without a module work before?
Let's say
```
// other.dart
class FooClass {}
// main.dart
import 'other.dart';
main() {
print(FooClass);
}
```Before this CL, both libraries would be assigned to the same wasm module - due to the import statement.
But after this CL, we notice that `main.dart` doesn't actually use anything "statically" from `other.dart` (i.e. no constructor invocation, no static call, ...). It does use `FooClass` but only as a type literal.
Because of that we say that `main.dart` becomes a wasm module which leaves the `other.dart` library dangling. But the compiler wants each library to have an assigned wasm module, so we make this fake one here.
// but unused).What is RTA?
"less precised" --> "less precise"
The issue is the way TFA works: TFA starts with empty set of classes and empty set of selectors. Then it gradually analyzes code. If it hits a method invocation and there's only one possible receiver class, it devirtualizes it. But if it later sees another allocation, then it has to invalidate this earlier decision and re-analyze that (now incorrect) devirtualized code. These invalidations are costly and take compile-time.
So we run RTA before TFA. It will have a much faster, simpler algorithm to determine the set of live classes. It will then TFA immediately that those classes are alive, which will make TFA converge faster (less invalidations).
Overall it improves compile-time.
RTA == Rapid Type Analysis, https://github.com/dart-lang/sdk/blob/0f6928c311f394c2e33deddbcc6aa0a35e0883f0/pkg/vm/lib/transformations/type_flow/rta.dart#L196
// Copyright (c) 2025, the Dart project authors. Please see the AUTHORS fileEverything in this library can be made private other than `unusedDeferredLibraryPrefix` and `pruneLibraryDependencies`.
Makes it easier to see what's the public interface and what are implementation details.
Done.
Made the top-level classes/functions that are only used in this file private.
// -> The main wasm module has all RTT information atmBy RTT do you mean the Wasm types? (structs, rec groups etc.)
Or is this some Dart-level thing that the main module includes?
It means RunTimeType information (sometimes we call it also RTI). It's the kind of objects we use to represent Dart types in wasm and relationships between those dart types.
Rephrased.
// -> No need to import a library to use classes from it in types.This is because the structs etc. need to be added to the using module anyway, because we can't import types?
No, this isn't about wasm structs, it's about Dart types, Dart classes and their relationship.
For example if we compile `main() => print(foo<BarClass>() is BazClass);` then we need to create a runtime object for the `BarClass` type argument and we need the some lookup tables to see how `BarClass` is related to `BazClass`. But this information is already in the main module atm.
void pruneLibraryDependencies(LibraryIndex libraryIndex, Component component) {Does this modify the kernels other than the `Library.dependencies` members? It may be helpful to document what it's modifying.
Done
final collector = Collector(library, constantToLibrarySet);You could initialize the collector in `ImportPruner` to make it clear that it's per pruner and can't (or shouldn't) be shared with different pruners.
Actually it looks like you only need the `usedLibraries`, so I think it would be even better to just pass `collector.usedLibraries` to `ImportPruner`. Makes dependencies smaller (pruner depends on a set of libs instead of a `Collector` class with other things)
Done
Does this need to visit all of the libraries? From the comment above "We import the library containing the definition of a [Reference] and not e.g. a library that may re-export it" it looks like we replace transitive imports with direct imports. So I think some of the libraries may end up being unused?
If that's the case, would it make sense to start from the main library and only process the libraries that are used?
We run this code after TFA has run - so most unused libraries should be already removed from the `Component`.
It's a good point, I could make this algorithm start from roots and only work towards direct/used dependencies. Though in reality I think this would be almost the same.
Doing it only from `main` wouldn't be enough, as we would also need to do that for each library that contains `@pragma('wasm:export')`s for example. Discovering that already requires traversing all libraries.
Furthermore IMHO it's nice that after running this transformation we have established an invariant on AST that library dependencies are precise (i.e. there iff they are needed).
So I'd prefer to keep it this way.
Can it ever be larger?
Yes, e.g. if modular transforms inserted static calls to functions without adding imports.
Updated the comment.
I checked the definition but I can't tell what `isImport` is.
I think this line checks for exported dependencies, but don't we replace transitive imports with direct imports, and doesn't that mean re-exports become unused?
Changed `!dep.isImport` to `dep.isExport`.
This transformation needs the exports to determine whether an element may have come from a deferred library or a non-deferred. Imagine:
```
import 'def.dart' deferred as D;
import 'def.dart' as D2;
main() {
print(D.foo());
}
```For the `StaticInvocation(foo, [])` node I don't know for sure whether it was called via `D` or `D2`. The CFE desugaring looses this information.
So for a case like the above I'm going to look whether any deferred imports (`D` here) happens to define or re-export the library containing `foo`. If it does, then I consider the deferred import `D` to be alive - which we need for semantics, as the above program has to throw (due to missing `await D.loadLibrary()`).
Since libraries can import each other in cycles, we need the exports while we prune the libraries of the component.
But yes, you're right that we don't need exports afterwards anymore - so I could remove them. Let me do this as a final pass.
Is this line missing some parts? If not it can be removed.
Done
`removedDeps` seems to be unused? Should it be used?
Done - it was from earlier iterations of this transformer (which I've re-written a few times before sending for review)
Might be helpful to refer to your documentation above here. Something like "Ignore due to (a) above". (same below in `visitSupertype`)
Done
It may be just me but I can't figure out what this is doing.
Couldn't you start with an empty set for every constant, and add the things added to the empty set to the parent call's set?
E.g something like:
```
final childrenLibrariesSet = ConstantToLibrarySet(); // also always initialize the `currentSet` as empty set
constant.visitChildren(childrenLibrariesSet); // collect libraries of child nodes
currentSet.addAll(childrenLibrariesSet.currentSet); // add libraries of child nodes to current set
map[constant] = Set.from(currentSet); // current constant's libraries = child libraries + current libraries
```I also can't tell which sets are shared here and which are their own copies. There's
- savedSet
- transitiveSet
- currentSet
and a bunch of assignments between them.
Feel free to ignore if it's clear to you.
So constants form a DAG (directed acyclic graph). We want to scan constants not as a tree because that could visit each node in the DAG many times, which would make this algorithm run in exponential time. So we want to handle one constant only once.
We compute it via DFS: A constant's libraries are it's childrens libraries plus enclosing library if constant is TearOff/Instance constant.
This collection of child constants happens via side-effect of setting `currentSet` to `{}` then `constant.visitChildren` then using `currentSet`.
Now since collecting the libraries of child constants may recursively collect libraries of other constants, we save the set & restore after.
Adding to the parent set is hacky as a) we'd need to maintain a stack of sets and add to all of them b) we won't add to all parents only to the current parent chain.
I've split it into two classes now, one that does the recursion and another that collects the shallow/direct child constants. It's a bit less efficient but probably easier to understand.
Similar to my comment above, if we replace all transitive imports with direct imports I think this condition should be gone? (or maybe I misunderstand what `isExport` is, I assume it's re-export of another library)
The information computed here is needed for this algorithm to do the right pruning. We don't use this after the pruning is done.
See my other comment. This is basically used to determine a boolean: For a use `U` (of class/function/field/... in library `H`) in library `M` we need to know whether the use `U` could possibly have come from any deferred import of `H` in `M`.(The used `U` may be available via deferred and non-deferred import - in which case we have to keep the deferred import for semantics pursposes)
Related details
- Ömer Ağacan
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Ömer Ağacan (Gerrit)
Ömer Ağacan voted Code-Review+1![]( "Open in Gerrit")
- Martin Kustermann
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Slava Egorov (Gerrit)
Slava Egorov voted Code-Review+1![]( "Open in Gerrit")
| Code-Review | +1 |
Related details
- Martin Kustermann
- Ömer Ağacan
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Martin Kustermann (Gerrit)
Martin Kustermann voted Commit-Queue+2![]( "Open in Gerrit")
- Ömer Ağacan
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Commit Queue (Gerrit)
Commit Queue submitted the change![]( "Open in Gerrit")
Change information
[dart2wasm] Prune library imports after TFA for better deferred module splits
This significantly prunes the imports in the library graph which in
return significantly reduces code size of main module.
- gallery: -27% (-677 KB)
- essentials: -45% (-8.7 MB)
The main insight here is that for the purpose of splitting up
Dart libraries into wasm modules we only have a dependency of
one dart library on another if the former uses something from
the latter "statically". Other uses of `Reference`s from other
libraries (e.g. interface targets, dart types, etc) don't
require an import.
The other insight is that a library A may import library B which
may re-export library C1, C2, C3. If A only uses things from C2
then we can remove import B and inject import C2 instead. That
means library A no longer needs B, C1, C2.
For dart types specifically: Compared to other backends,
dart2wasm stores all RTI (runtime type information) in the
main module - i.e. deferred modules don't bring extra RTI -
which is why we don't have to load deferred module before we
can access it's types.
- M pkg/dart2wasm/lib/compile.dart
- M pkg/dart2wasm/lib/deferred_loading.dart
- A pkg/dart2wasm/lib/library_dependencies_pruner.dart
- A pkg/dart2wasm/test/ir_tests/deferred.constant.multi_module_use_module4.wat
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use.dart
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use.h.0.dart
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use.h.1.dart
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use.wat
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use_module1.wat
- A pkg/dart2wasm/test/ir_tests/deferred.constant.type_use_module2.wat
- A pkg/dart2wasm/test/ir_tests/deferred.constant_module3.wat
- A pkg/dart2wasm/test/ir_tests/import_name_module2.wat
Code-Review: +1 by Slava Egorov
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |