[golang-dev] Re: code review 7229074: exp/ssa: build fully pruned SSA form. (issue 7229074)

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go
File src/pkg/exp/ssa/blockopt.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode18
src/pkg/exp/ssa/blockopt.go:18: // markReachable set Index=-1 for all
blocks reachable from b.
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode31
src/pkg/exp/ssa/blockopt.go:31: func collectUnreachable(f *Function) {
Done (actually "deleteUnreachableBlocks").

("Collect" was intended in the spirit of "collect garbage", but I see
the confusion when I think of methods like types.collectFields, etc.)

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode32
src/pkg/exp/ssa/blockopt.go:32: // We use b.Index as the mark bit: 0
means white, -1 means black.
Black/white marking is pretty standard in the literature of both graph
theory and of GC. I also find it easier to visualise algorithms
expressed this way.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode51
src/pkg/exp/ssa/blockopt.go:51: for i, b := range f.Blocks {
Done; factored into Function.removeNilBlocks.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode102
src/pkg/exp/ssa/blockopt.go:102: f.Blocks[b.Index] = nil // delete b
I'd rather not, since (a) it would hide what's going on (introduction of
nils, which demands a subsequent call to removeNilBlocks) and (b) a
deleteBlock function would have to take a block index, not a
*BasicBlock, to be safe to call from within deleteUnreachableBlocks
where the Index numbers have been repurposed. That seems like a
confusing interface.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode136
src/pkg/exp/ssa/blockopt.go:136: f.Blocks[b.Index] = nil // delete b
Ditto.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode146
src/pkg/exp/ssa/blockopt.go:146: collectUnreachable(f)
Done: "deleteUnreachableBlocks".

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode178
src/pkg/exp/ssa/blockopt.go:178: // Eliminate nils from Blocks and
update Index.
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/doc.go
File src/pkg/exp/ssa/doc.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/doc.go#newcode37
src/pkg/exp/ssa/doc.go:37: // called "lifting", to improve the accuracy
and performance of
period?

Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go
File src/pkg/exp/ssa/dom.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode11
src/pkg/exp/ssa/dom.go:11: // We also apply the optimisations to SLT
described in Georgiadis et
Done, globally. Though I'm sure there are more Commonwealth than US
speakers on the team. :)

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode26
src/pkg/exp/ssa/dom.go:26: type domTree struct {
A node is a tree. :)

But I vacillated. It's back to domNode again. It does seem better.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode228
src/pkg/exp/ssa/dom.go:228: for changed {
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode262
src/pkg/exp/ssa/dom.go:262: panic("sanityCheckDomTree failed for " +
f.FullName())
Ack.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode276
src/pkg/exp/ssa/dom.go:276: // printDomTreeDot prints the dominator tree
of f in AT&T GraphViz format.
It's the same format, except "dot" is less helpful than "AT&T GraphViz"
as a search term for someone seeing this for the first time.

(Strictly, 'dot' is the name of the tool that renders GraphViz files
using the Sugiyama algorithm; there are other tools and algos.)

Changed to "in AT&T GraphViz (.dot) format".

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/func.go
File src/pkg/exp/ssa/func.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/func.go#newcode44
src/pkg/exp/ssa/func.go:44: panic(fmt.Sprintf("no edge %s -> %s", c, b))
panic has different control flow implications than an ordinary function
call. It would be inconvenient to write:

panicf("%s, world", "goodbye")
panic("no, I really mean it")

each time I want to abort at the end of a nonvoid function.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/func.go#newcode241
src/pkg/exp/ssa/func.go:241: // (value-defining Instructions) in f, to
aid deubgging.
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/func.go#newcode546
src/pkg/exp/ssa/func.go:546: // emit. comment is an optional string to
improve readability.
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/lift.go
File src/pkg/exp/ssa/lift.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/lift.go#newcode151
src/pkg/exp/ssa/lift.go:151: // During this pass we will replace deleted
some
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/lift.go#newcode256
src/pkg/exp/ssa/lift.go:256: // take removes an arbitrary element from a
set s and
No, but since that's all I need from it, that's all I specified in the
contract.

"Arbitrary" != "random", only "unspecified".

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/lift.go#newcode399
src/pkg/exp/ssa/lift.go:399: // constructing it lazily if it's the
implicit zero initialization.
Done.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/sanity.go
File src/pkg/exp/ssa/sanity.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/sanity.go#newcode301
src/pkg/exp/ssa/sanity.go:301: // they were "optimised" away, even the
entry block.
Done.

https://codereview.appspot.com/7229074/

*** Submitted as
https://code.google.com/p/go/source/detail?r=95914f6d6c36 ***

exp/ssa: build fully pruned SSA form.

Overview: Function.finish() now invokes the "lifting" pass which
replaces local allocs and loads and stores to such cells by SSA
registers. We use very standard machinery:

(1) we build the dominator tree for the function's control flow graph
(CFG) using the "Simple" Lengauer-Tarjan algorithm. (Very "simple" in
fact: even simple path compression is not yet implemented.)

In sanity-checking mode, we cross check the dominator tree against an
alternative implementation using a simple iterative dataflow algorithm.
This all lives in dom.go, along with some diagnostic printing routines.

(2) we build the dominance frontier for the entire CFG using the Cytron
et al algorithm. The DF is represented as a slice of slices, keyed by
block index. See buildDomFrontier() in lift.go.

(3) we determine for each Alloc whether it can be lifted: is it only
subject to loads and stores? If so, we traverse the iterated dominance
frontier (IDF) creating φ-nodes; they are not prepended to the blocks
yet.
See liftAlloc() in lift.go.

(4) we perform the SSA renaming algorithm from Cytron et al, replacing
all loads to lifted Alloc cells by the value stored by the dominating
store operation, and deleting the stores and allocs. See rename() in
lift.go.

(5) we eliminate unneeded φ-nodes, then concatenate the remaining ones
with the non-deleted instructions of the block into a new slice. We
eliminate any lifted allocs from Function.Locals.

To ease reviewing, I have avoided almost all optimisations at this
point, though there are many opportunities to explore. These will be
easier to understand as follow-up changes.

All the existing tests (pending CL 7313062) pass. (Faster!)

Details:

"NaiveForm" BuilderMode flag suppresses all the new logic.
Exposed as 'ssadump -build=N'.

BasicBlock:
- add .Index field (b.Func[b.Index]==b), simplifying
algorithms such as Kildall-style dataflow with bitvectors.
- rename the Name field to Comment to better reflect its
reduced purpose. It now has a String() method.
- 'dom' field holds dominator tree node; private for now.
- new predIndex method.
- hasPhi is now a method

dom.go:
- domTree: a new struct for a node in a dominator tree.
- buildDomTree builds the dominator tree using the simple
variant Lengauer/Tarjan algorithm with Georgiadis'
bucket optimizations.
- sanityCheckDomTree builds dominance relation using
Kildall-style dataflow and ensures the same result is
obtained.
- printDomTreeDot prints the CFG/DomTree in GraphViz format.

blockopt.go:
- perform a mark/sweep pass to eliminate unreachable
cycles; the previous prune() opt would only eliminate
trivially dead blocks. (Needed for LT algo.)
- using .Index, fuseblocks can now delete fused blocks directly.
- delete prune().

sanity.go: more consistency checks:
- Phi with missing edge value
- local Alloc instructions must appear in Function.Locals.
- BasicBlock.Index, Func consistency
- CFG edges are all intraprocedural.
- detect nils in BasicBlock.Instrs.
- detect Function.Locals with Heap flag set.
- check fn.Blocks is nil if empty.

Also:
- Phi now has Comment field for debugging.
- Fixed bug in Select.Operands()
(took address of temporary copy of field)
- new Literal constructor zeroLiteral().
- algorithms steal private fields Alloc.index,
BasicBlock.gaps to avoid allocating maps.
- We print Function.Locals in DumpTo.
- added profiling support to ssadump.

R=iant, gri
CC=golang-dev
https://codereview.appspot.com/7229074


https://codereview.appspot.com/7229074/

Just FYI.


https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go
File src/pkg/exp/ssa/blockopt.go (right):

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode31
src/pkg/exp/ssa/blockopt.go:31: func collectUnreachable(f *Function) {
Except that in GC, unused blocks are actually collected and returned to
the pool of free memory. Here nothing is collected and returned.

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode32
src/pkg/exp/ssa/blockopt.go:32: // We use b.Index as the mark bit: 0
means white, -1 means black.
this way.

Sure. But theory is often not easier to understand for the uninvited
(i.e., not you, but a casual reader). So if you call it used/unused, the
algorithm becomes immediately clear, while if you call it black/white,
the reader has to be either familiar with the specific literature, or do
another mental mapping in his/her head. It's not like this is a very
complex function that cannot be understood anyway, w/o full knowledge of
the literature (in that case, I agree that sticking to the same name as
some documented algorithm in literature is using is better).

https://codereview.appspot.com/7229074/

Ok. Will change when I'm next in that file.