code review 37230043: go.tools/ssa: expose dominator tree of control-flow gra...

go.tools/ssa: expose dominator tree of control-flow graph in API.

New APIs:
  (*BasicBlock).{Idom,Dominees,Dominates}
  (*Function).DomPreorder

Messy but systematic refactoring of domNode:
- renamed "domInfo".
- embedded directly in BasicBlock, not as pointer. Block field removed.
- Level field removed; was unused.
- Working state of LT algorithm now in its own type.
  {semi,parent,ancestor} fields moved into it.
- remaining fields made private; accessors added.
- use 32-bit ints for pre/postorder numbers.
- allocate LT working space (5 copies of fn.Blocks) contiguously.

dom.go is simpler but somewhat more verbose.

Also:
- we always build the domtree now---yet memory usage is down 5%.
- number the Recover block too.
- add sanity check for DomPreorder.

[adonovan, 2013-12-04 17:38:11]

Hello gri@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go.tools

[gri, 2013-12-05 01:34:10]

LGTM

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go
File ssa/dom.go (right):

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode53
ssa/dom.go:53: order := make([]*BasicBlock, n, n)
make(byDomPreorder, n, n)

and get rid of cast below

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode61
ssa/dom.go:61: idom      *BasicBlock   // immediate dominator (parent in
dominator tree)
why not parent?

you call the children children

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode68
ssa/dom.go:68: type lt struct {
lt seems a bit terse - lenTarState? ltState?

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode70
ssa/dom.go:70: semi     []*BasicBlock // b's semidominator
semidom? dom?

(semi is misleading)

[adonovan, 2013-12-05 14:50:20]

*** Submitted as
https://code.google.com/p/go/source/detail?r=5ff8080945aa&repo=tools ***

go.tools/ssa: expose dominator tree of control-flow graph in API.

New APIs:
  (*BasicBlock).{Idom,Dominees,Dominates}
  (*Function).DomPreorder

Messy but systematic refactoring of domNode:
- renamed "domInfo".
- embedded directly in BasicBlock, not as pointer. Block field removed.
- Level field removed; was unused.
- Working state of LT algorithm now in its own type.
  {semi,parent,ancestor} fields moved into it.
- remaining fields made private; accessors added.
- use 32-bit ints for pre/postorder numbers.
- allocate LT working space (5 copies of fn.Blocks) contiguously.

dom.go is simpler but somewhat more verbose.

Also:
- we always build the domtree now---yet memory usage is down 5%.
- number the Recover block too.
- add sanity check for DomPreorder.

R=gri
CC=golang-dev
https://codereview.appspot.com/37230043

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go
File ssa/dom.go (right):

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode53
ssa/dom.go:53: order := make([]*BasicBlock, n, n)
On 2013/12/05 01:34:10, gri wrote:
> make(byDomPreorder, n, n)
> 
> and get rid of cast below

Neat!  I had assumed the copy would fail, but it works.

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode61
ssa/dom.go:61: idom      *BasicBlock   // immediate dominator (parent in
dominator tree)
On 2013/12/05 01:34:10, gri wrote:
> why not parent?
> 
> you call the children children

idom is what this is called in all the literature, and the name 'parent' is used
for a different concept in LT (a predecessor in the control-flow graph).

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode68
ssa/dom.go:68: type lt struct {
On 2013/12/05 01:34:10, gri wrote:
> lt seems a bit terse - lenTarState? ltState?

Isn't terse good? :)

I've gone with ltState.

https://codereview.appspot.com/37230043/diff/40001/ssa/dom.go#newcode70
ssa/dom.go:70: semi     []*BasicBlock // b's semidominator
On 2013/12/05 01:34:10, gri wrote:
> semidom? dom?
> 
> (semi is misleading)

Changed to sdom, under which name this is known in the all the literature.