Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(58)

Issue 7229074: code review 7229074: exp/ssa: build fully pruned SSA form. (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
9 years, 8 months ago by adonovan
Modified:
9 years, 7 months ago
Reviewers:
gri
CC:
iant, golang-dev
Visibility:
Public.

Description

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.

Patch Set 1 #

Patch Set 2 : diff -r 9ff35ff05de6 https://go.googlecode.com/hg/ #

Patch Set 3 : diff -r dd18b993ba95 https://go.googlecode.com/hg/ #

Patch Set 4 : diff -r dd18b993ba95 https://go.googlecode.com/hg/ #

Patch Set 5 : diff -r dd18b993ba95 https://go.googlecode.com/hg/ #

Patch Set 6 : diff -r dd18b993ba95 https://go.googlecode.com/hg/ #

Total comments: 44

Patch Set 7 : diff -r 734059df2768 https://go.googlecode.com/hg/ #

Patch Set 8 : diff -r 734059df2768 https://code.google.com/p/go/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+1095 lines, -124 lines) Patch
M src/pkg/exp/ssa/blockopt.go View 1 2 3 4 5 6 7 chunks +45 lines, -58 lines 0 comments Download
M src/pkg/exp/ssa/builder.go View 1 2 3 4 5 6 5 chunks +5 lines, -4 lines 0 comments Download
M src/pkg/exp/ssa/doc.go View 1 2 3 4 5 6 1 chunk +5 lines, -4 lines 0 comments Download
A src/pkg/exp/ssa/dom.go View 1 2 3 4 5 6 1 chunk +296 lines, -0 lines 0 comments Download
M src/pkg/exp/ssa/func.go View 1 2 3 4 5 6 12 chunks +110 lines, -33 lines 0 comments Download
A src/pkg/exp/ssa/lift.go View 1 2 3 4 5 6 1 chunk +492 lines, -0 lines 0 comments Download
M src/pkg/exp/ssa/literal.go View 1 2 3 2 chunks +35 lines, -0 lines 0 comments Download
M src/pkg/exp/ssa/print.go View 1 2 3 chunks +13 lines, -5 lines 0 comments Download
M src/pkg/exp/ssa/sanity.go View 1 2 3 4 5 6 10 chunks +67 lines, -16 lines 0 comments Download
M src/pkg/exp/ssa/ssa.go View 1 2 3 4 5 6 5 chunks +11 lines, -4 lines 0 comments Download
M src/pkg/exp/ssa/ssadump.go View 1 2 5 chunks +16 lines, -0 lines 0 comments Download

Messages

Total messages: 6
adonovan
Hello iant@golang.org, gri@golang.org (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://go.googlecode.com/hg/
9 years, 7 months ago (2013-02-20 21:39:17 UTC) #1
gri
LGTM I have not studied the large algorithm sections. Overall the code looks pretty clean. ...
9 years, 7 months ago (2013-02-21 06:35:05 UTC) #2
adonovan
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 ...
9 years, 7 months ago (2013-02-21 16:03:59 UTC) #3
adonovan
*** Submitted as https://code.google.com/p/go/source/detail?r=95914f6d6c36 *** exp/ssa: build fully pruned SSA form. Overview: Function.finish() now invokes ...
9 years, 7 months ago (2013-02-21 16:12:03 UTC) #4
gri
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) { On 2013/02/21 16:03:59, ...
9 years, 7 months ago (2013-02-21 16:48:09 UTC) #5
adonovan
9 years, 7 months ago (2013-02-21 17:25:14 UTC) #6
On 21 February 2013 11:48, <gri@golang.org> wrote:

>  > btw. , wouldn't used/unused be better than black/white?
>>
>
>  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.
>
> 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).
>

Ok.  Will change when I'm next in that file.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b