Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Golang dev.ssa branch merged into tip

github.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Golang dev.ssa branch merged into tip

#31

Post by DannyBee »

UniQP wrote: post #28
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…

> 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.

SSA is not a pre-req to a decoupled spilling phase :)

In fact, the guy who wrote LLVM's current register allocation did his thesis on decoupled SSA register allocation - http://www.theses.fr/2012ENSL0777

But he still decided not to go that way in LLVM when decoupling regalloc from spilling.

"because it may bring some new insights to the research community."

No offense, but this seems pretty unlikely. It's been 10 years and the number of production optimizing compilers that use SSA based regalloc (for example) is still hovering close to 0.

Sad (because i helped fund a ton of that research), but true.

The same thing is sadly true of libfirm. While a really impressive piece of work, it hasn't spurred much that i can see ...

(FWIW: I had the same hopes)

Re: Golang dev.ssa branch merged into tip

#32

Post by DannyBee »

pklausler wrote: post #30
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…

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.

Explicitly inserting copies is lowering :)

Re: Golang dev.ssa branch merged into tip

#34

Post by pklausler »

rurban wrote: post #14
gillianseed wrote: post #9

Earlier quoted context omitted.

Improved optimizations which will also be easier to implement, with the result being faster and also typically smaller code.

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

It depends on the compiler. The great thing about SSA conversion is that you only have to do it once, whereas a classical def/use-chaining analysis may have to be redone many times in an old-style optimizer.

SSA is a conversion of the program into a representation of its data flow. I've used it in multiple compilers and found it to be a big win for easing other analyses (e.g., induction variable recognition become trivial) and reducing bugs due to the update problem.

Re: Golang dev.ssa branch merged into tip

#35

Post by UniQP »

DannyBee wrote: post #29
UniQP wrote: post #27

Earlier quoted context omitted.

> 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…

> 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.

It's impossible to have one edge pointing to multiple reaching definitions.

Re: Golang dev.ssa branch merged into tip

#36

Post by enneff »

vruiz wrote: post #15
zamalek wrote: post #10

Earlier quoted context omitted.

SSA, once you understand it, is easier to work with than almost all other forms of instruction sets. I'd argue that it would only accelerate new architecture in the long-run. I'm interested in why LLVM was disqualified. Was it simply never considered or is it incompatible with the Go type system, calling convention, etc.?

> I'm interested in why LLVM was disqualified. They simply used what they knew best: > If step one had been "learn the GCC or LLVM toolchains well enough to add segmented stacks", I'm not sure we'd have gotten to step two. > Honestly, if we'd built on GCC or LLVM, we'd be moving so slowly I'd probably have left the project years ago. https://news.ycombinator.com/item?id=8817990

Even today we can still re-build the entire tool chain and standard library in one minute on a modest machine.

If we were using LLVM...

Re: Golang dev.ssa branch merged into tip

#37

Post by DannyBee »

UniQP wrote: post #35
DannyBee wrote: post #29

Earlier quoted context omitted.

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…

> 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. It's impossible to have one edge pointing to multiple reaching definitions.

Of course, but I think you missed the point of what i said. Which was: It's possible to get into situations where that that node could have multiple possible reaching definitions, even if it only points to one at a given time. That is still not SSA. In that case, the edge is just wrong, even if it only points to one arbitrarily selected possible reaching definition.

In short: Your argument is "it's SSA because the data structures only allow for a single reaching definition". This is not right. If i don't insert phi nodes, and just have the IR point at random reaching definitions, it's not magically SSA, because there is not actually a unique reaching definition for each point, it just happens you've pointed the edges at arbitrarily selected reaching definitions (IE made the graph wrong :P)

Post reply on HN