Golang dev.ssa branch merged into tip • Hacker News Board

Re: Golang dev.ssa branch merged into tip

#21

Post by UniQP » Wed, Mar 02, 2016, 2:57 PM UTC

jlouis wrote: post #19

gillianseed wrote: post #18

Earlier quoted context omitted.

True, an increase in optimizations will likely mean longer compile times, on the other hand, with better optimized code, the compiler itself (as it's written in Go) will also perform better, which may negate some of the increase in compile time.

One of the alluring things of SSA form is that many optimizations are much faster to execute on the form. The costly part is to raise the SSA form in the first place which in the standard implementation requires one to build a costly dominator tree. You don't need to add every optimization known to man to a compiler, so you can sometimes keep a few of the important ones and then skip every other optimization. A prior…

As stated in [1] they use a variant of "Simple and Efficient Construction of Static Single Assignment Form" [2], which does not require a dominator tree (or a liveness analysis).

[1] https://github.com/golang/go/blob/master/src/cmd/compile/int...

[2] http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun1...

Re: Golang dev.ssa branch merged into tip

#22

Post by UniQP » Wed, Mar 02, 2016, 3:15 PM UTC

After libfirm [1], the Go compiler now seems to be the second mature compiler with an SSA-based backend. I hope more compilers will follow.

I missed some references to corresponding papers in the source code. For instance, is the register allocator an implementation of "Linear Scan Register Allocation on SSA Form" [2]?

Also some facts mention in comments [3] are a bit scary but I guess this will be resolved over time.

[1] http://pp.ipd.kit.edu/firm/

[2] http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer1...

[3] https://github.com/golang/go/blob/master/src/cmd/compile/int...

Re: Golang dev.ssa branch merged into tip

#23

Post by qznc » Wed, Mar 02, 2016, 4:01 PM UTC

gillianseed wrote: post #18

rurban wrote: post #14

Earlier quoted context omitted.

And typically longer compile times. Most variables are split into ("phi") variants, for each assignment, and many more costly optimization steps are now possible.

True, an increase in optimizations will likely mean longer compile times, on the other hand, with better optimized code, the compiler itself (as it's written in Go) will also perform better, which may negate some of the increase in compile time.

I think Wirth with his Pascal compiler had this as a rule. If you added an optimization (which takes additional time), it must speed up the compiler enough that compilation times are not longer.

Re: Golang dev.ssa branch merged into tip

#24

Post by electrum » Wed, Mar 02, 2016, 4:09 PM UTC

UniQP wrote: post #22

After libfirm [1], the Go compiler now seems to be the second mature compiler with an SSA-based backend. I hope more compilers will follow. I missed some references to corresponding papers in the source code. For instance, is the register allocator an implementation of "Linear Scan Register Allocation on SSA Form" [2]? Also some facts mention in comments [3] are a bit scary but I guess this will be resolved over time…

According to Wikipedia, SSA is used extensively by GCC, LLVM and every major JIT: https://en.wikipedia.org/wiki/Static_single_assignment_form#...

Re: Golang dev.ssa branch merged into tip

#25

Post by UniQP » Wed, Mar 02, 2016, 4:22 PM UTC

electrum wrote: post #24

UniQP wrote: post #22

After libfirm [1], the Go compiler now seems to be the second mature compiler with an SSA-based backend. I hope more compilers will follow. I missed some references to corresponding papers in the source code. For instance, is the register allocator an implementation of "Linear Scan Register Allocation on SSA Form" [2]? Also some facts mention in comments [3] are a bit scary but I guess this will be resolved over time…

According to Wikipedia, SSA is used extensively by GCC, LLVM and every major JIT: https://en.wikipedia.org/wiki/Static_single_assignment_form#...

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

Re: Golang dev.ssa branch merged into tip

#26

Post by DannyBee » Wed, Mar 02, 2016, 4:30 PM UTC

UniQP wrote: post #25

electrum wrote: post #24

Earlier quoted context omitted.

According to Wikipedia, SSA is used extensively by GCC, LLVM and every major JIT: https://en.wikipedia.org/wiki/Static_single_assignment_form#...

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

Most of LLVM's backend is SSA, actually. At some point it lowers out of SSA, but you have to do that at some point anyway.

It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc)

My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenance or whatever benefits, great.

There are theoretical benefits, but in practice, LLVM does pretty well with it's current scheme.

Because of this, it's not really near the top of any todo list, nor should it be.

Re: Golang dev.ssa branch merged into tip

#27

Post by UniQP » Wed, Mar 02, 2016, 5:05 PM UTC

DannyBee wrote: post #26

UniQP wrote: post #25

Earlier quoted context omitted.

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

Most of LLVM's backend is SSA, actually. At some point it lowers out of SSA, but you have to do that at some point anyway. It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc) My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenan…

> At some point it lowers out of SSA, but you have to do that at some point anyway.

libfirm never goes out of SSA (since it uses a graph-based representation it's simply impossible: the data dependency edges need one target). It converts the programm to CSSA and assigns the same register to all phi operands. When finally emitting the program, phi nodes emit nothing.

Re: Golang dev.ssa branch merged into tip

#28

Post by UniQP » Wed, Mar 02, 2016, 5:19 PM UTC

DannyBee wrote: post #26

UniQP wrote: post #25

Earlier quoted context omitted.

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

Most of LLVM's backend is SSA, actually. At some point it lowers out of SSA, but you have to do that at some point anyway. It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc) My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenan…

> There are theoretical benefits, but in practice, LLVM does pretty well with it's current scheme.

I think having a decoupled spilling phase is nice feature of the SSA-based scheme. However, I don't say that LLVM (or GCC) should switch to the SSA-based scheme. I just appreciate that the Go compiler switched to the SSA-based scheme, because it may bring some new insights to the research community.

Re: Golang dev.ssa branch merged into tip

#29

Post by DannyBee » Wed, Mar 02, 2016, 5:24 PM UTC

UniQP wrote: post #27

DannyBee wrote: post #26

Earlier quoted context omitted.

Most of LLVM's backend is SSA, actually. At some point it lowers out of SSA, but you have to do that at some point anyway. It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc) My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenan…

> At some point it lowers out of SSA, but you have to do that at some point anyway. libfirm never goes out of SSA (since it uses a graph-based representation it's simply impossible: the data dependency edges need one target). It converts the programm to CSSA and assigns the same register to all phi operands. When finally emitting the program, phi nodes emit nothing.

Okay, sure, this is pretty much the same thing for a graph based IR. You can argue this isn't a form of lowering, but in practice, it doesn't matter.

Note that your claim "(since it uses a graph-based representation it's simply impossible: the data dependency edges need one target)"

is wrong :)

SSA also requires that things have a single, unique, reaching definition.

The fact that the graph edges have one target does not guarantee this (it is instead a representation that requires this for correctness) Open64 is another compiler with factored use-def chains like this (though the rest is not graph based), and has the same issue -

If you hoist something to various valid points (IE across existing live ranges), it's possible to generate multiple reaching definitions. This is because the dataflow definition of reaching definitions is not "whatever is on the end of this graph edge". So the fact that the graph edges only point to one of those definitions just makes the graph edges wrong.

So it's not impossible, but libfirm avoids it or performs the necessary phi insertion in various places to avoid creating invalid SSA for the representation it has.

(Note: It is possible to have IR's where the only ordering is a data dependence ordering, and so the graph is the source of truth and where it points is where it points. There are also representations where the control flow is implied by the graph nodes. In these representations, what you say would be correct. From what i know of libfirm, it has basic blocks and control flow edges, and it uses that to give some ordering. In this world, it's possible to screw up the SSA properties with pretty simple operations, and make the graph no longer correct)

Re: Golang dev.ssa branch merged into tip

#30

Post by pklausler » Wed, Mar 02, 2016, 5:26 PM UTC

DannyBee wrote: post #26

UniQP wrote: post #25

Earlier quoted context omitted.

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

Most of LLVM's backend is SSA, actually. At some point it lowers out of SSA, but you have to do that at some point anyway. It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc) My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenan…

I've written a graph-coloring register assigner that stayed in SSA form in an optimizing compiler for the Cray X1 and BlackWidow architectures. The key idea is to treat each phi function as being a copy, perhaps coalescable, located at the foot of each of the block's predecessors. Works great.