Last Comment Bug 650715 - JM+TI: do SSA
: JM+TI: do SSA
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
-- normal (vote)
: ---
Assigned To: Brian Hackett (:bhackett)
: Jason Orendorff [:jorendorff]
Depends on: 652314 652414 665812
Blocks: TypeInference
  Show dependency treegraph
Reported: 2011-04-17 20:12 PDT by Brian Hackett (:bhackett)
Modified: 2011-06-20 18:03 PDT (History)
9 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

restructuring (214.49 KB, patch)
2011-04-18 13:03 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
WIP (251.49 KB, patch)
2011-04-20 12:00 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
WIP 2 (335.58 KB, patch)
2011-04-20 18:15 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
WIP 3 (367.01 KB, patch)
2011-04-21 14:37 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (368.16 KB, patch)
2011-04-22 08:11 PDT, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review

Description User image Brian Hackett (:bhackett) 2011-04-17 20:12:08 PDT
Backend optimizations in JM+TI already do things in several places that are subsumed by SSA, tracking values as they are pushed and values of variables in straight-line code.  Doing full-blown SSA would simplify these and would make future analysis and inference work easier and more precise (interval analysis for bug 650496, bug 649260).  IonMonkey will also need SSA, but its needs as I understand them will be somewhat different --- the plan there is an SSA-based IR which can be transformed by high level optimizations, while here we need static information that easily maps to and from the bytecode.  Can just implement this now (since we need it now) and figure out the interaction with IonMonkey later.
Comment 1 User image Brian Hackett (:bhackett) 2011-04-18 13:03:10 PDT
Created attachment 526798 [details] [diff] [review]

Restructure frontend analyses so that all analyses have the same lifetime as inference data (persist until the next GC) and allocate from the same per-compartment arena as type inference.  Also flattens analyze::Script, analyze::LifetimeScript and types::TypeScript into a single data structure analyze::ScriptAnalysis, which holds all analysis and type information for the script (destroyed on each GC).

There was a real hodgepodge of different lifetimes and arenas around, this simplifies things and makes it easier to add SSA as an optional frontend pass.  Skeleton SSA structures are here, no algorithm and all this does is compile.
Comment 2 User image Brian Hackett (:bhackett) 2011-04-20 12:00:02 PDT
Created attachment 527340 [details] [diff] [review]

Has an SSA implementation now, not tested at all and needs integration with inference, other analyses and the compiler itself.
Comment 3 User image Brian Hackett (:bhackett) 2011-04-20 18:15:16 PDT
Created attachment 527456 [details] [diff] [review]

Inference and Compiler using SSA values, works on small examples, still some missing functionality.
Comment 4 User image Brian Hackett (:bhackett) 2011-04-21 14:37:13 PDT
Created attachment 527650 [details] [diff] [review]

Passes jit-tests with --jitflags=na (i.e. no methodjit, but the methodjit changes aren't that big).
Comment 5 User image Brian Hackett (:bhackett) 2011-04-22 08:11:05 PDT
Created attachment 527772 [details] [diff] [review]

Patch landed on JM.

Speeds up SS and other benchmarks slightly for me, I think due to the lowered recompilation penalty --- we only need to do the compilation pass and not redo the analysis passes.  But doing this analysis doesn't seem to cost much, and the implementation is pretty clean.  One way it could be improved:

- Depends on lifetime analysis having been done first.  At loop heads we eagerly generate phi nodes for all variables modified in the loop, which requires lifetimes indicating to figure out that modified set.  Making this lazier would cut this dependency, which would be good as for IonMonkey the lifetime analysis will I believe want to be done on the SSA form.
Comment 6 User image Brian Hackett (:bhackett) 2011-04-22 15:40:35 PDT
Looks to have broken one of the Kraken crypto tests, does anyone mind doing a testcase reduction?  (Need to learn to use these myself one of these days...).  A new MochiTest-4 failure too, surprisingly green otherwise.

Note You need to log in before you can comment on or make changes to this bug.