JS tree shaking for incremental builds.

JS tree shaking for incremental builds.

This patch does two things:
1) Introduces the infrastructure that is needed by dart-level tree shaking so that it can properly deal with native JS code and thereby prune both dart and JS code.
2) Leverages the infrastructure above to enable JS-level tree shaking of the output of incremental builds by default.  Non-incremental builds are not impacted and neither are libraries without entry points.

Prior to this patch an empty application compiled to 558,508 bytes, but with it the size is reduced to 103,679 bytes.  It is important to note that the large lower bound is driven by the dependency chain introduced by isolate$processWorkerMessage in corelib/implementation/isolate.js.

For applications like total the savings are much bigger.  Prior to this patch Total compiled to 12,151,122 bytes, but with it the size is reduced to 3,758,174.  For an app the size of total this additional tree shaking takes about 2 seconds.

Once this patch lands the plan is to thread it into the pending dart-level tree shaking work if needed.  This second arc of work will allow us to further compress the output during non-incremental builds by eliding RTT, native JS code, dart methods exposed to native JS code and do dead code elimination.

Committed: https://code.google.com/p/dart/source/detail?r=2077

[mmendez, 2011-11-29 20:33:18]

See CL description for full details.

[zundel, 2011-11-30 15:09:57]

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile, Reader
inputFile) {
maybe a better name for nodesProcessed is nodesToEmit?

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:71:
inputFile.skip(node.getLength());
Why not just set currentPostion only after reading the file?  Then the
inputFile.skip() at the top of the try block handles this case.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:151:
inputFile.mark((int) (fileSize + 16));
FYI: From reading the BufferedReader source, I'm pretty sure this causes the
entire file to be cached in memory.   I don't have any good suggestions on how
to prevent it, other than modifying the ArtifactProvider to return you an actual
File object so you can create a second reader from scratch for the second pass.

If you wanted to go a middle route, you could just have your computeNodesToEmit
save the node text to emit as it encounters it in the parse.  You'd still be
storing lots of data in memory, but not as much as the entire file.

http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt.js
File compiler/lib/implementation/rtt.js (right):

http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt...
compiler/lib/implementation/rtt.js:211: function ImplementsAll(name) {
(what does this have to do with this patch?)

[codefu, 2011-11-30 23:43:33]

Other than Eric's comments, lgtm.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java:64:

nit; ws

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:110:
worklist.addAll(declVisitor.getEntryPoints());
aren't entry points technically global?

[fabiomfv, 2011-12-01 15:37:26]

On 2011/11/30 23:43:33, codefu wrote:
> Other than Eric's comments, lgtm.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java:64:
> 
> nit; ws
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:110:
> worklist.addAll(declVisitor.getEntryPoints());
> aren't entry points technically global?

LGTM - minor comment.

[fabiomfv, 2011-12-01 15:37:40]

LGTM - minor comment.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java:178:
outputFileSize = CharStreams.copy(artifactReader, artifactWriter);
could we just rename(move) the file instead of copying in this case? basically
we would only use the completeArtifact in case it has an entrypoint.

[mmendez, 2011-12-01 21:31:30]

PTAL.  I believe that I have addressed everyone's feedback.

Once this lands there are some more changes that we can make it to get the
incremental output down further.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java:178:
outputFileSize = CharStreams.copy(artifactReader, artifactWriter);
I can't rename with the current API, but what I will do is to just write into
the final name if we don't have an entry point.

On 2011/12/01 15:37:40, fabiomfv wrote:
> could we just rename(move) the file instead of copying in this case? basically
> we would only use the completeArtifact in case it has an entrypoint.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java:64:

On 2011/11/30 23:43:33, codefu wrote:
> nit; ws

Done.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile, Reader
inputFile) {
On 2011/11/30 15:09:57, zundel wrote:
> maybe a better name for nodesProcessed is nodesToEmit?

Done.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:71:
inputFile.skip(node.getLength());
On 2011/11/30 15:09:57, zundel wrote:
> Why not just set currentPostion only after reading the file?  Then the
> inputFile.skip() at the top of the try block handles this case.

Done.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:110:
worklist.addAll(declVisitor.getEntryPoints());
They are global but we treat them as roots that seed the worklist.

On 2011/11/30 23:43:33, codefu wrote:
> aren't entry points technically global?

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:151:
inputFile.mark((int) (fileSize + 16));
It will.  The research version of this code bypassed the whole artifact provider
and didn't suffer from this problem.  

Rather than tweak the artifcat provider API at this point, I'll just pass the
app and context the code will call back to get the Readers.
On 2011/11/30 15:09:57, zundel wrote:
> FYI: From reading the BufferedReader source, I'm pretty sure this causes the
> entire file to be cached in memory.   I don't have any good suggestions on how
> to prevent it, other than modifying the ArtifactProvider to return you an
actual
> File object so you can create a second reader from scratch for the second
pass.
> 
> If you wanted to go a middle route, you could just have your
computeNodesToEmit
> save the node text to emit as it encounters it in the parse.  You'd still be
> storing lots of data in memory, but not as much as the entire file.

http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt.js
File compiler/lib/implementation/rtt.js (right):

http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt...
compiler/lib/implementation/rtt.js:211: function ImplementsAll(name) {
Makes it such that properties are either x.y or x.prototype.y and therefore
easier to shake.

On 2011/11/30 15:09:57, zundel wrote:
> (what does this have to do with this patch?)

[zundel, 2011-12-02 12:33:43]

LGTM with nit

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile, Reader
inputFile) {
On 2011/12/01 21:31:30, mmendez wrote:
> On 2011/11/30 15:09:57, zundel wrote:
> > maybe a better name for nodesProcessed is nodesToEmit?
> 
> Done.

FYI - you didn't actually change it

[codefu, 2011-12-02 13:26:06]

LGTM 
On 2011/12/01 21:31:30, mmendez wrote:
> PTAL.  I believe that I have addressed everyone's feedback.
> 
> Once this lands there are some more changes that we can make it to get the
> incremental output down further.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java:178:
> outputFileSize = CharStreams.copy(artifactReader, artifactWriter);
> I can't rename with the current API, but what I will do is to just write into
> the final name if we don't have an entry point.
> 
> On 2011/12/01 15:37:40, fabiomfv wrote:
> > could we just rename(move) the file instead of copying in this case?
basically
> > we would only use the completeArtifact in case it has an entrypoint.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java:64:
> 
> On 2011/11/30 23:43:33, codefu wrote:
> > nit; ws
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
> private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile,
Reader
> inputFile) {
> On 2011/11/30 15:09:57, zundel wrote:
> > maybe a better name for nodesProcessed is nodesToEmit?
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:71:
> inputFile.skip(node.getLength());
> On 2011/11/30 15:09:57, zundel wrote:
> > Why not just set currentPostion only after reading the file?  Then the
> > inputFile.skip() at the top of the try block handles this case.
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:110:
> worklist.addAll(declVisitor.getEntryPoints());
> They are global but we treat them as roots that seed the worklist.
> 
> On 2011/11/30 23:43:33, codefu wrote:
> > aren't entry points technically global?
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:151:
> inputFile.mark((int) (fileSize + 16));
> It will.  The research version of this code bypassed the whole artifact
provider
> and didn't suffer from this problem.  
> 
> Rather than tweak the artifcat provider API at this point, I'll just pass the
> app and context the code will call back to get the Readers.
> On 2011/11/30 15:09:57, zundel wrote:
> > FYI: From reading the BufferedReader source, I'm pretty sure this causes the
> > entire file to be cached in memory.   I don't have any good suggestions on
how
> > to prevent it, other than modifying the ArtifactProvider to return you an
> actual
> > File object so you can create a second reader from scratch for the second
> pass.
> > 
> > If you wanted to go a middle route, you could just have your
> computeNodesToEmit
> > save the node text to emit as it encounters it in the parse.  You'd still be
> > storing lots of data in memory, but not as much as the entire file.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt.js
> File compiler/lib/implementation/rtt.js (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt...
> compiler/lib/implementation/rtt.js:211: function ImplementsAll(name) {
> Makes it such that properties are either x.y or x.prototype.y and therefore
> easier to shake.
> 
> On 2011/11/30 15:09:57, zundel wrote:
> > (what does this have to do with this patch?)

[mmendez, 2011-12-02 13:26:52]

I updated the patch with Eric's suggested rename.

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
File compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
(right):

http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile, Reader
inputFile) {
Sorry, I lost that delta when I rolled back some experiments yesterday.


On 2011/12/02 12:33:43, zundel wrote:
> On 2011/12/01 21:31:30, mmendez wrote:
> > On 2011/11/30 15:09:57, zundel wrote:
> > > maybe a better name for nodesProcessed is nodesToEmit?
> > 
> > Done.
> 
> FYI - you didn't actually change it

[fabiomfv, 2011-12-02 14:25:17]

On 2011/12/01 21:31:30, mmendez wrote:
> PTAL.  I believe that I have addressed everyone's feedback.
> 
> Once this lands there are some more changes that we can make it to get the
> incremental output down further.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/JavascriptBackend.java:178:
> outputFileSize = CharStreams.copy(artifactReader, artifactWriter);
> I can't rename with the current API, but what I will do is to just write into
> the final name if we don't have an entry point.
> 
> On 2011/12/01 15:37:40, fabiomfv wrote:
> > could we just rename(move) the file instead of copying in this case?
basically
> > we would only use the completeArtifact in case it has an entrypoint.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/DependencyComputer.java:64:
> 
> On 2011/11/30 23:43:33, codefu wrote:
> > nit; ws
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> File
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
> (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:47:
> private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile,
Reader
> inputFile) {
> On 2011/11/30 15:09:57, zundel wrote:
> > maybe a better name for nodesProcessed is nodesToEmit?
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
> compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:71:
> inputFile.skip(node.getLength());
> On 2011/11/30 15:09:57, zundel wrote:
> > Why not just set currentPostion only after reading the file?  Then the
> > inputFile.skip() at the top of the try block handles this case.
> 
> Done.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:110:
> worklist.addAll(declVisitor.getEntryPoints());
> They are global but we treat them as roots that seed the worklist.
> 
> On 2011/11/30 23:43:33, codefu wrote:
> > aren't entry points technically global?
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/java/com/google/dart/c...
>
compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java:151:
> inputFile.mark((int) (fileSize + 16));
> It will.  The research version of this code bypassed the whole artifact
provider
> and didn't suffer from this problem.  
> 
> Rather than tweak the artifcat provider API at this point, I'll just pass the
> app and context the code will call back to get the Readers.
> On 2011/11/30 15:09:57, zundel wrote:
> > FYI: From reading the BufferedReader source, I'm pretty sure this causes the
> > entire file to be cached in memory.   I don't have any good suggestions on
how
> > to prevent it, other than modifying the ArtifactProvider to return you an
> actual
> > File object so you can create a second reader from scratch for the second
> pass.
> > 
> > If you wanted to go a middle route, you could just have your
> computeNodesToEmit
> > save the node text to emit as it encounters it in the parse.  You'd still be
> > storing lots of data in memory, but not as much as the entire file.
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt.js
> File compiler/lib/implementation/rtt.js (right):
> 
>
http://codereview.chromium.org/8676041/diff/1/compiler/lib/implementation/rtt...
> compiler/lib/implementation/rtt.js:211: function ImplementsAll(name) {
> Makes it such that properties are either x.y or x.prototype.y and therefore
> easier to shake.
> 
> On 2011/11/30 15:09:57, zundel wrote:
> > (what does this have to do with this patch?)

LTGM+++++

[zundel, 2011-12-05 14:13:23]

still LGTM

[codefu, 2011-12-05 16:05:27]

On 2011/12/05 14:13:23, zundel wrote:
> still LGTM

3 for 3, LGTM (still)