A very interesting idea, a sort of hybrid AST/SSA (hmm, I recall GCC now has some kind of 'Tree SSA' too) although I think the real win wouldn't come until you could replace conditionals like JWhile/JIf/JFor with their SSA equivalents.The reason being, you'd be limited from doing intra-block flow analysis without it, so only small methods would benefit.
Ah, here's the paper I remember reading: http://www.airs.com/dnovillo/Papers/tree-ssa-gccs03-slides.pdf I think this could seriously be adapted for GWT, and using your idea of incrementally doing it, I think would work to get experimental results without blowing up the existing architecture. -Ray On Tue, Jun 16, 2009 at 11:11 AM, Matt Mastracci<[email protected]> wrote: > > Could we build out SSA incrementally (brainstorming a bit here)? > Maybe start by replacing the Java and JS expressions with their SSA > equivalent in the tree? The consecutive JExpressionStatements in a > JBlock or JsBlock could be extracted into SSA form and inserted as a > new type of statement - JSsaStatement. This would let us perform all > the SSA analysis on a limited scale without having to rewrite the > whole compiler - just the parts that operate on JExpressions. > > BTW, value numbering looks like a quick win to me. Reusing locals has > another additional benefit - it allows the browser to GC values at > reassignment time, rather than waiting for the scope to exit (which > may be far in the future in the case of closures). > > On 16-Jun-09, at 11:49 AM, Ray Cromwell wrote: > >> >> 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 -~----------~----~----~----~------~----~------~--~---
