I prototyped a piece of this a couple of months ago in an attempt to work out how to build an immediate dominator tree so as to perfectly prune clinits. The problem is, you'd have to practically rewrite the entire compiler. I think at this point, it's a little too much, maybe something for GWT 3.0.
My middle ground was to consider a sort of 'overlay' SSA to gather information for optimizations in the AST. That is, process the AST and build up an SSA IR, and then use that to compute information needed for optimizations later (e.g. dominator tree). Then, you do the optimizations on the AST and choose optimizations which do not violate invariants that would cause the need to recompute the auxiliary IR. For example, in the case of dominators, there are known optimizations which do not change dominance relationships, so are safe to do and allow you to cache that information. Another possibility is to do value numbering instead of SSA. You could process blocks and value number all assignments. Afterwards, you can efficiently detect use-def patterns and use this for copy-prop, cse, dead removal. Finally, you follow up with a 'register allocator' pass that renames all the values back by allocating symbols as needed according to liveness ranges. For example, something like String s1 = "Hello": Window.alert(s1); String s2 = "World"; Window.alert(s2); would become String s1 = "Hello"; Window.alert(s1); s1 = "World"; Window.alert(s2); This would eliminate a 'var' declaration from the JS, which should have some benefit to both size and speed. -Ray On Tue, Jun 16, 2009 at 10:27 AM, Matt Mastracci<[email protected]> wrote: > > I've been pondering an SSA structure for the compiler that would make > some of this stuff a lot easier to deal with. Instead of keeping the > AST for the Java and JS trees around, we'd put everything into a > unified data flow graph in memory (with appropriate side-effect > barriers), optimize the graph, then reconstitute Java and JS code as > appropriate. > > It's a huge undertaking, but there's some bonus end-results (some of > these fall out of the process of converting between AST and SSA forms: > > - Many optimizations would now apply to both Java and JS code > - Cross-language Java<->JS inlining and static evaluation would be > easier > - Easier inlining/common subexpression elimination > - More opportunities for static evaluation > - Incremental type tightening - the compiler could make more > methods static by knowing more about types/nullness deep within the > data flows: if (x instanceof Blah) { ((Blah)x).foo(); } > > By traversing the data flow graph, the compiler would be able to see > that the JS object was effectively equivalent to the associative array > literal { 'a': 1, 'b': 2 } before it was even accessed by other code. > In cases where the developer is building other complex datastructures, > the compiler could potentially replace those with fully baked > equivalents as needed. > > Matt. > > On 16-Jun-09, at 9:59 AM, Ray Cromwell wrote: > >> >> Even before the inliner gets it, a JSO chained expression like >> a().b().c() is going to look like c(b(a())) so the inliner can only >> inline the first call. >> >> Automatically introducing temporaries would seem a lot harder. You'd >> have to teach the compiler that 'this' is effectively final, and >> therefore any method returning this, effectively always returns the >> same value, regardless of side effects. Then, you'd have to introduce >> the idea that the compiler can introduce temporaries (speculatively), >> and later use common subexpression elimination to detect multiple >> identical ones and hoist them out. >> >> e.g. >> >> c(b(a())) >> >> becomes >> >> var t1, t2, t3; >> t1 = c(t2 = b(t3 = a())) >> >> then, recognizing the that t1=t2=t3=builder=a() with copy propagation >> t1 = builder >> a(t1) >> b(t1) >> c(t1) >> >> and now they can be inlined. >> >> This just seems hard to me, since introducing temporaries is >> speculative and you'd have introduce another pass to remove them in >> the cases where they provided no benefit. However, this could end up >> leading to infinite loops if you're not careful. >> >> -Ray >> >> >> >> On Mon, Jun 15, 2009 at 6:11 PM, Brian Stoler<[email protected]> >> wrote: >>> >>> Hi gwtc, >>> >>> I was playing with using super-source to emulate some existing code >>> that uses a builder pattern and make it efficient in GWT as a >>> JavaScriptObject. I was hoping that the I could make the Builder just >>> compile away, but that doesn't seem to be happening. I started >>> debugging in JsInliner but started to get a bit lost. This is using >>> svn r5557 on trunk FYI (very recent). >>> >>> What I am seeing is that if you use a chaining call pattern, the >>> inliner doesn't realize some of the optimization it can do. >>> >>> Example usage code: >>> >>> void example() { >>> MyData myData = MyData.Builder.create() >>> .setBar("a") >>> .setFoo("b").build(); >>> >>> Window.alert(myData.getBar()); >>> Window.alert(myData.getFoo()); >>> } >>> >>> >>> Output I get (extraneous bits removed, PRETTY mode): >>> >>> function init(){ >>> var myData; >>> myData = $setFoo($setBar(new Object(), 'a'), 'b'); >>> $wnd.alert(myData.bar); >>> $wnd.alert(myData.foo); >>> } >>> >>> function $setBar(this$static, s){ >>> this$static.bar = s; >>> return this$static; >>> } >>> >>> function $setFoo(this$static, s){ >>> this$static.foo = s; >>> return this$static; >>> } >>> >>> >>> However, with this similar code: >>> >>> void example2() { >>> MyData.Builder builder = MyData.Builder.create(); >>> builder.setBar("a"); >>> builder.setFoo("b"); >>> >>> MyData myData = builder.build(); >>> >>> Window.alert(myData.getBar()); >>> Window.alert(myData.getFoo()); >>> } >>> >>> >>> The code compiles better (no setters): >>> >>> builder = new Object(); >>> builder.bar = 'a'; >>> builder.foo = 'b'; >>> myData = builder; >>> $wnd.alert(myData.bar); >>> $wnd.alert(myData.foo); >>> >>> >>> The biggest issue seemed to be that the inliner didn't introduce a >>> local variable for "new Object()", and because of that, it correctly >>> concluded it couldn't keep copying that expression around. (I traced >>> through it having issues due to "new" having side effects.) Even if I >>> manually create a variable for the Builder at the outset, it still >>> doesn't help. (FYI, I am using new Object() instead of {} to work >>> around http://code.google.com/p/google-web-toolkit/issues/detail?id=3568) >>> >>> I was going to try to dig some more in to the inliner, but any ideas >>> how to improve this? >>> >>> Will a later pass remove useless variable aliasing? (Seems like not >>> from my other example?) If so, I was thinking it might work to have >>> the inliner introduce a local all the time when it is trying to >>> inline >>> a non-void function. Smarter methods are of course possible, but I >>> thought that might be worth a shot. >>> >>> Any other ideas welcome. MyData class attached below. I tried a >>> variety of small tweaks to the MyData class and nothing made a >>> difference. >>> >>> FYI, my eventual goal is: >>> >>> var myData = {bar:'a',foo:'b'}; >>> >>> But that seems like an orthogonal optimization (and perhaps >>> generically useful). >>> >>> Thanks for your interest, if you read this far, >>> -brian >>> >>> PS: I am open to any changes to the MyData code below that a) >>> preserve >>> the JSO-ness and b) leave the external API the same. >>> >>> public static interface MyData { >>> String getFoo(); >>> String getBar(); >>> >>> public static final class Builder extends JavaScriptObject >>> implements MyData { >>> protected Builder() {} >>> >>> public static native Builder create() /*-{ >>> return new Object(); >>> }-*/; >>> >>> public native String getFoo() /*-{ >>> return this.foo; >>> }-*/; >>> >>> public native String getBar() /*-{ >>> return this.bar; >>> }-*/; >>> >>> public Builder setFoo(String s) { >>> setFooImpl(s); >>> return this; >>> } >>> >>> private native void setFooImpl(String s) /*-{ >>> this.foo = s; >>> }-*/; >>> >>> public Builder setBar(String s) { >>> setBarImpl(s); >>> return this; >>> } >>> >>> private native void setBarImpl(String s) /*-{ >>> this.bar = s; >>> }-*/; >>> >>> public MyData build() { >>> return this; >>> } >>> } >>> } >>> >>>> >>> >> >> > > > > > > --~--~---------~--~----~------------~-------~--~----~ http://groups.google.com/group/Google-Web-Toolkit-Contributors -~----------~----~----~----~------~----~------~--~---
