SSA-able and canSSA meaning in Go compiler's SSA backend?

[Mohit Verma]

Hi All,

I was reading Go compiler's SSA backend code at cmd/compile/internal/gc/ssa/go & cmd/compile/internal/ssa, and I keep on seeing some code generation logic depending on if a type is "SSA-able". 

For example, 

While building SSA tree for an assignment operation, I see comments like this:

// We're assigning to a field of an ssa-able value. We need to build a new structure with the new value for the field we're assigning and the old values for the other fields. For instance:
// type T struct {a, b, c int}
// var T x
// x.b = 5
// For the x.b = 5 assignment we want to generate x = T{x.a, 5, x.c}

which seems like a sub-optimal way of updating only one element of a struct. My question is: 

What is a SSA-able value/type for Go compiler? What is a SSA-able node in Go's AST representation? How is it different from other non SSA-able values? What special purpose does it serve?

Can anyone help me understand this/point me to links to existing literature around this?

Thanks!

Mohit

[Keith Randall]

On Wednesday, September 18, 2019 at 1:50:27 PM UTC-7, Mohit Verma wrote:

Hi All,

I was reading Go compiler's SSA backend code at cmd/compile/internal/gc/ssa/go & cmd/compile/internal/ssa, and I keep on seeing some code generation logic depending on if a type is "SSA-able". 

For example, 

While building SSA tree for an assignment operation, I see comments like this:

// We're assigning to a field of an ssa-able value. We need to build a new structure with the new value for the field we're assigning and the old values for the other fields. For instance:
// type T struct {a, b, c int}
// var T x
// x.b = 5
// For the x.b = 5 assignment we want to generate x = T{x.a, 5, x.c}

 

which seems like a sub-optimal way of updating only one element of a struct.

If T is SSAable, then one of the optimization passes decomposes x into its constituent parts.

So we effectively rewrite this to:

var x_a int  \

var x_b int   |  from var T x

var x_c int  /

x.a = x.a \

x.b = 5     | from x.b = 5

x.c = x.c  /

The two trivial assignments are then quickly optimized away.

My question is: 

What is a SSA-able value/type for Go compiler? What is a SSA-able node in Go's AST representation? How is it different from other non SSA-able values? What special purpose does it serve?

First types. An array type with len>1 can't be represented in SSA, because there is no way to encode indexing operations.

In addition, as a heuristic we don't SSA large types, as SSAing them usually means breaking them up into their component values, and that can run the compiler out of registers pretty quickly.

(this is canSSAType)

Then variables. If a variable doesn't have an SSAable type, then we won't generate any SSA for it. In addition, if its address is taken we can't SSA it, because SSA representation has no way to represent possible side effects through pointers. There are a few other cases which also forbid making a variable SSAable.

(this is (*state).canSSA)

[howar...@gmail.com]

Read this wiki page to understand what the goal is:

https://en.wikipedia.org/wiki/Static_single_assignment_form

Basically, SSA-form allows certain optimizations that are harder without it, but SSA is also itself hard to apply. SSA examples are often posed in the form of simple variables, but real code has structs and arrays and maps and slices. So they mark things that are worth the effort of applying SSA to and things they've (the compiler writers, that is) have decided are not worth of pushing down to an SSA form.

So, the special purpose it serves is to enable a class of optimizations. And the difference from non-SSA-able values is simply one of cost/benefit. Non-SSA-able values are actually those where implementing SSA was deemed either not possible or too expensive (either in terms of time, or code, or just the compiler author's brainspace).

Here is a link to a talk from a Go developer about adding SSA to the compiler:

https://about.sourcegraph.com/go/generating-better-machine-code-with-ssa

(P.S. if this ends up posting multiple times, I apologize. It has told me there was an error communicating with the server twice now.)

[Agniva De Sarker]

> Here is a link to a talk from a Go developer about adding SSA to the compiler

That Go developer is the one who answered OP's question :)