FAQ
LGTM

I have not studied the large algorithm sections. Overall the code looks
pretty clean.


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.
s/set/sets/

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) {
s/collectUnreachable/eliminateUnreachable/

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

const white = 0
const black = -1

why use comments when you can express it in code

btw. , wouldn't used/unused be better than black/white?

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 {
any reason for not compressing f.Blocks now? (remove the nil entries)
You're doing most of the work anyway. It's fine if you still want to be
able to deal with nil entries elsewhere.

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
make deleteBlock a method of f? - Then you don't need the comment.

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
dito

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode146
src/pkg/exp/ssa/blockopt.go:146: collectUnreachable(f)
better name and you don't need the comment

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.
The re-indexing and elimination of nil entries happens again here.
Definitively should be factored out.

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
the comma here seems odd to me. remove and replace ; on text line with
period?

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
optimizations ?

https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/dom.go#newcode26
src/pkg/exp/ssa/dom.go:26: type domTree struct {
why not domNode ?

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

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())
another use for panicf

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.
wow, really? why not dot format? how much is it different?

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))
if you have more of these (seems useful), consider defining panicf.

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

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.
s/to improve readability/for more readable debugging output/.

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
replace deleted some ... ? (sentence)

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
the algorithm doesn't remove an arbitrary element, though

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

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

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

--

---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Adonovan at Feb 21, 2013 at 4:04 pm
    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.
    On 2013/02/21 06:35:05, gri wrote:
    s/set/sets/
    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) {
    On 2013/02/21 06:35:05, gri wrote:
    s/collectUnreachable/eliminateUnreachable/
    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.
    On 2013/02/21 06:35:05, gri wrote:
    perhaps
    const white = 0
    const black = -1
    why use comments when you can express it in code Done.
    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.

    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 {
    On 2013/02/21 06:35:05, gri wrote:
    any reason for not compressing f.Blocks now? (remove the nil entries) You're
    doing most of the work anyway. It's fine if you still want to be able to deal
    with nil entries elsewhere.
    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
    On 2013/02/21 06:35:05, gri wrote:
    make deleteBlock a method of f? - Then you don't need the comment.
    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
    On 2013/02/21 06:35:05, gri wrote:
    dito
    Ditto.

    https://codereview.appspot.com/7229074/diff/11002/src/pkg/exp/ssa/blockopt.go#newcode146
    src/pkg/exp/ssa/blockopt.go:146: collectUnreachable(f)
    On 2013/02/21 06:35:05, gri wrote:
    better name and you don't need the comment
    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.
    On 2013/02/21 06:35:05, gri wrote:
    The re-indexing and elimination of nil entries happens again here.
    Definitively
    should be factored out.
    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
    On 2013/02/21 06:35:05, gri wrote:
    the comma here seems odd to me. remove and replace ; on text line with
    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
    On 2013/02/21 06:35:05, gri wrote:
    optimizations ?
    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 {
    On 2013/02/21 06:35:05, gri wrote:
    why not domNode ?
    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 {
    On 2013/02/21 06:35:05, gri wrote:
    for changed := true; 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())
    On 2013/02/21 06:35:05, gri wrote:
    another use for panicf
    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.
    On 2013/02/21 06:35:05, gri wrote:
    wow, really? why not dot format? how much is it different?
    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))
    On 2013/02/21 06:35:05, gri wrote:
    if you have more of these (seems useful), consider defining panicf.
    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.
    On 2013/02/21 06:35:05, gri wrote:
    debugging
    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.
    On 2013/02/21 06:35:05, gri wrote:
    s/to improve readability/for more readable debugging output/.
    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
    On 2013/02/21 06:35:05, gri wrote:
    replace deleted some ... ? (sentence)
    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
    On 2013/02/21 06:35:05, gri wrote:
    the algorithm doesn't remove an arbitrary element, though
    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.
    On 2013/02/21 06:35:05, gri wrote:
    double blank
    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.
    On 2013/02/21 06:35:05, gri wrote:
    optimized ?
    Done.

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

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Adonovan at Feb 21, 2013 at 4:12 pm
    *** 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/

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Gri at Feb 21, 2013 at 4:48 pm
    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, adonovan wrote:
    On 2013/02/21 06:35:05, gri wrote:
    s/collectUnreachable/eliminateUnreachable/
    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.)
    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.
    On 2013/02/21 16:03:59, adonovan wrote:
    On 2013/02/21 06:35:05, gri wrote:
    perhaps

    const white = 0
    const black = -1

    why use comments when you can express it in code Done.
    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).

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

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Alan Donovan at Feb 21, 2013 at 5:49 pm

    On 21 February 2013 11:48, 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.

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedFeb 21, '13 at 6:35a
activeFeb 21, '13 at 5:49p
posts5
users2
websitegolang.org

2 users in discussion

Alan Donovan: 3 posts Gri: 2 posts

People

Translate

site design / logo © 2022 Grokbase