cmd/compile: merge order/walk/instrument into buildssa

[mdempsky]

Currently the compiler backend performs several stages of Node AST rewrites before generating SSA. We should investigate generating SSA directly from the AST produced by the frontend. Rationale:

1. order.go exists as a separate pass primarily to simplify maintaining order-of-evaluation in walk.go, but we can probably just as easily handle this when directly producing SSA.
2. order.go and walk.go iterate across the entire function AST a couple times, reading and writing to every pointer slot. Usually the values written are also identical to the values already in memory too.
3. AST rewrites requires the intermediary format to be representable in the AST too, which may complicate transitioning to package syntax. There are currently several gc.Ops generated and used only within the backend (e.g., OSQRT, OINDREGSP, OEFACE, ...).
4. The AST invariants between these phases are poorly documented or at least poorly understood.

/cc @randall77 @josharian

[josharian]

This sounds great! I see a few things to discuss.

• The gc-to-SSA converter started simple and grew organically, and it is already starting to be pretty hairy. A recent example is CL 32313 (which, for the record, I am excited about); the non-trivial complexity there has simply moved from walk to the SSA converter. It'd be nice to find some way to better organize the converter as part of expanding it.
• There are some manipulations/optimizations that are just easier to do on an AST than SSA, even though that means that they are less powerful. An example is integer in-range checks (cmd/compile: recognize and optimize "in range" booleans #15844). We'd probably want to leave an AST-manipulation phase for items like this.
• Doesn't this also require porting escape analysis and inlining and closure handling to the new AST? Escape analysis in particular worries me; it's the most complicated and hardest to debug.
• During the freeze, I hope to work on making the backend compile concurrently. That includes the gc-to-SSA converter, since it is a large part of compilation time. Substantively rewriting the converter and supporting concurrent compilation might easily collide. We should probably discuss this in a higher bandwidth medium and come up with an approach.

[martisch]

I am also in favor of refactoring order/walk/instrumenting e.g. into the ssa backend.
But i share josharians view that we should keep a lighter ast rewriting phase for some high level optimizations.

How does the new parsers node tree fit into this: Could we move some high level rewriting like in-range checks to a new phase that works on the new parsers node tree and other things into the buildssa backend until walk.go/order.go/... do no changes any more. Then replace the new_ast->old_ast->generic_ssa path by new_ast->generic_ssa?

OSQRT: i think is not needed anymore. we should be able to handle this completely just as intrinsic in the ssa backend. (i will do a CL for 1.9).

[stemar94]

Might be interesting:
http://link.springer.com/chapter/10.1007/978-3-642-37051-9_6

Abstract.
We present a simple SSA construction algorithm, which allows
direct translation from an abstract syntax tree or bytecode into an
SSA-based intermediate representation. The algorithm requires no prior
analysis and ensures that even during construction the intermediate
representation is in SSA form. This allows the application of SSA-based
optimizations during construction. After completion, the intermediate
representation is in minimal and pruned SSA form. In spite of its simplicity,
the runtime of our algorithm is on par with Cytron et al.’s algorithm

[mdempsky]

@stemar94 Thanks, we actually already use that algorithm for constructing SSA. :) See the comments at the top of https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/phi.go

This issue is about avoiding some of the intermediate IR rewrite passes that were needed before we switched to the SSA backend.

[josharian]

We made minor progress on this for 1.9 (e.g. walkmul and walkdiv). Moving to 1.10.

[mdempsky]

The bulk of racewalk.go's code has been moved to buildssa, which should allow us to start transitioning more walk.go lowering steps to buildssa.