code review 124690043: go.tools/go/rta: implement Rapid Type Analysis for Go.

go.tools/go/rta: implement Rapid Type Analysis for Go.

This is an algorithm for callgraph construction that is faster
but much less precise than pointer analysis.
(I evaluated this for the Go Oracle last year but shelved it,
but it's a natural fit for the work Brian is doing on
automatic program minimization.)

[adonovan, 2014-08-21 01:24:49]

Hello gri@golang.org, crawshaw@golang.org (cc: bwkster@gmail.com,
golang-codereviews@googlegroups.com),

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

[gri, 2014-08-23 00:35:29]

some preliminary comments - will take some more time next week

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode1
go/rta/rta.go:1: // Copyright 2013 The Go Authors. All rights reserved.
it's 2014

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode36
go/rta/rta.go:36: // until a fixed point is achieved.
s/fixed point/fixpoint/

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode118
go/rta/rta.go:118: // markReachable marks a function as potentially callable at
run-time,
s/markReachable/addReachable/

seems clearer

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode122
go/rta/rta.go:122: reachable := r.result.Reachable
s/reachable/m/

and perhaps s/sz/n/

and this becomes less of a see of chars

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode219
go/rta/rta.go:219: rands := instr.Operands(space[:0])
I don't see where there's ever something added to rands in this loop. What am I
missing?

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode259
go/rta/rta.go:259: if len(roots) == 0 {
Is this common to warrant the extra check? Do you want to get nil as a result
(so one possibly dies and thus catches errors)?

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode269
go/rta/rta.go:269: // TODO(adonovan): get rid of the notion of a fake root
?

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode282
go/rta/rta.go:282: // Use double-buffering of the worklist.
is this really called double-buffering?

this might be clearer if you'd say this is the fixpoint iteration

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta_test.go
File go/rta/rta_test.go (right):

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta_test.go#newcode1
go/rta/rta_test.go:1: package rta_test
copyright notice

[adonovan, 2014-08-25 15:27:20]

https://codereview.appspot.com/124690043/diff/40001/go/rta/testdata/func.go
File go/rta/testdata/func.go (right):

https://codereview.appspot.com/124690043/diff/40001/go/rta/testdata/func.go#n...
go/rta/testdata/func.go:17: C = func(int) {}
make C standalone

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode1
go/rta/rta.go:1: // Copyright 2013 The Go Authors. All rights reserved.
On 2014/08/23 00:35:28, gri wrote:
> it's 2014

True, but I wrote this last year.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode36
go/rta/rta.go:36: // until a fixed point is achieved.
On 2014/08/23 00:35:29, gri wrote:
> s/fixed point/fixpoint/

"Fixpoint" as a noun feels like slang.  Usually you see it as a qualifier
(fixpoint iteration, fixpoint combinator).

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode118
go/rta/rta.go:118: // markReachable marks a function as potentially callable at
run-time,
On 2014/08/23 00:35:29, gri wrote:
> s/markReachable/addReachable/
> 
> seems clearer

Done.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode122
go/rta/rta.go:122: reachable := r.result.Reachable
On 2014/08/23 00:35:28, gri wrote:
> s/reachable/m/
> 
> and perhaps s/sz/n/
> 
> and this becomes less of a see of chars

Done.  Agreed.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode219
go/rta/rta.go:219: rands := instr.Operands(space[:0])
On 2014/08/23 00:35:29, gri wrote:
> I don't see where there's ever something added to rands in this loop. What am
I
> missing?

Operands returns the operands of instr, by appending to its argument space[:0],
an empty slice with slack.
rands is then just used for iteration.

Equivalent but less efficient:
for _, op := range instr.Operands(nil) {

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode259
go/rta/rta.go:259: if len(roots) == 0 {
On 2014/08/23 00:35:29, gri wrote:
> Is this common to warrant the extra check? Do you want to get nil as a result
> (so one possibly dies and thus catches errors)?

It's not common but it is possible, and probably worth treating specially by not
returning an empty non-nil Result instance.

Some kind of check is of course needed because the roots[0] operation below
would panic without it.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode269
go/rta/rta.go:269: // TODO(adonovan): get rid of the notion of a fake root
On 2014/08/23 00:35:29, gri wrote:
> ?

Cryptic note to self.  Changed to:

// TODO(adonovan): change callgraph API to eliminate the
// notion of a distinguished root node.  Some callgraphs
// have many roots, or none.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode282
go/rta/rta.go:282: // Use double-buffering of the worklist.
On 2014/08/23 00:35:29, gri wrote:
> is this really called double-buffering?

It's a classic worklist pattern: you have two arrays, one of which is growing
while the other is being iterated.  Then you flip them over and repeat.  (I
think the name originates in graphics, where you draw to one frame buffer while
the other one is visible, then flip them.)

> this might be clearer if you'd say this is the fixpoint iteration

Done.

// Visit functions, processing their instructions, and adding
// new functions to the worklist, until a fixed point is
// reached.
var shadow []*ssa.Function // for efficiency, we double-buffer the worklist

[adonovan, 2014-08-25 15:27:21]

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode27
go/rta/rta.go:27: // discovered, call graph edges are added from to each
compatible
from to

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode30
go/rta/rta.go:30: // In addition, we must treat all exported methods of any
runtime type
treat -> consider

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode33
go/rta/rta.go:33: // Each time an newly added call edge causes a new function to
become
a newly

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode65
go/rta/rta.go:65: // This includes exported methods of address-taken types,
since
AT types  -> runtime

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode121
go/rta/rta.go:121: func (r *rta) markReachable(f *ssa.Function, at bool) {
AT

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode133
go/rta/rta.go:133: func (r *rta) addEdge(site ssa.CallInstruction, callee
*ssa.Function, at bool) {
AT

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode259
go/rta/rta.go:259: result: &Result{
join lines

https://codereview.appspot.com/124690043/diff/40001/go/rta/rta.go#newcode265
go/rta/rta.go:265: const buildCallGraph = true
make this a param

https://codereview.appspot.com/124690043/diff/40001/go/rta/testdata/func.go
File go/rta/testdata/func.go (right):

https://codereview.appspot.com/124690043/diff/40001/go/rta/testdata/func.go#n...
go/rta/testdata/func.go:17: C = func(int) {}
make C standalone

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode1
go/rta/rta.go:1: // Copyright 2013 The Go Authors. All rights reserved.
On 2014/08/23 00:35:28, gri wrote:
> it's 2014

True, but I wrote this last year.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode36
go/rta/rta.go:36: // until a fixed point is achieved.
On 2014/08/23 00:35:29, gri wrote:
> s/fixed point/fixpoint/

"Fixpoint" as a noun feels like slang.  Usually you see it as a qualifier
(fixpoint iteration, fixpoint combinator).

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode118
go/rta/rta.go:118: // markReachable marks a function as potentially callable at
run-time,
On 2014/08/23 00:35:29, gri wrote:
> s/markReachable/addReachable/
> 
> seems clearer

Done.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode122
go/rta/rta.go:122: reachable := r.result.Reachable
On 2014/08/23 00:35:28, gri wrote:
> s/reachable/m/
> 
> and perhaps s/sz/n/
> 
> and this becomes less of a see of chars

Done.  Agreed.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode219
go/rta/rta.go:219: rands := instr.Operands(space[:0])
On 2014/08/23 00:35:29, gri wrote:
> I don't see where there's ever something added to rands in this loop. What am
I
> missing?

Operands returns the operands of instr, by appending to its argument space[:0],
an empty slice with slack.
rands is then just used for iteration.

Equivalent but less efficient:
for _, op := range instr.Operands(nil) {

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode259
go/rta/rta.go:259: if len(roots) == 0 {
On 2014/08/23 00:35:29, gri wrote:
> Is this common to warrant the extra check? Do you want to get nil as a result
> (so one possibly dies and thus catches errors)?

It's not common but it is possible, and probably worth treating specially by not
returning an empty non-nil Result instance.

Some kind of check is of course needed because the roots[0] operation below
would panic without it.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode269
go/rta/rta.go:269: // TODO(adonovan): get rid of the notion of a fake root
On 2014/08/23 00:35:29, gri wrote:
> ?

Cryptic note to self.  Changed to:

// TODO(adonovan): change callgraph API to eliminate the
// notion of a distinguished root node.  Some callgraphs
// have many roots, or none.

https://codereview.appspot.com/124690043/diff/60001/go/rta/rta.go#newcode282
go/rta/rta.go:282: // Use double-buffering of the worklist.
On 2014/08/23 00:35:29, gri wrote:
> is this really called double-buffering?

It's a classic worklist pattern: you have two arrays, one of which is growing
while the other is being iterated.  Then you flip them over and repeat.  (I
think the name originates in graphics, where you draw to one frame buffer while
the other one is visible, then flip them.)

> this might be clearer if you'd say this is the fixpoint iteration

Done.

// Visit functions, processing their instructions, and adding
// new functions to the worklist, until a fixed point is
// reached.
var shadow []*ssa.Function // for efficiency, we double-buffer the worklist

[Sameer Ajmani, 2014-11-12 18:40:16]

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode39
go/rta/rta.go:39: // analysis, but the algorithm is much faster.
Worth documenting the big-O behavior of rta and pta here?

Perhaps include example wall-clock running time for rta vs. pta on a nontrivial
binary.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode67
go/rta/rta.go:67: // The value indicates whether the function is address-taken.
Make the value a struct instead, so it's obvious that existence in the map is
all that matters.  It's very common to use map[T]bool as a set so that "if m[t]"
tests membership; that's not what you mean here.  And a struct would let you
document the value better:
  Reachable map[*ssa.Function]Reachability

type Reachability struct {
  AddressTaken bool
}

or AddrTaken, if you prefer

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode92
go/rta/rta.go:92: atFuncsBySig typeutil.Map
addrTakenFuncsBySig

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode120
go/rta/rta.go:120: // AT indicates whether to mark f as "address-taken".
s/AT/addrTaken/g

Then you don't need the comments.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode148
go/rta/rta.go:148: // visitATFunc is called each time we encounter an
address-taken function f.
visitAddrTakenFunc

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go
File go/rta/rta_test.go (right):

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
go/rta/rta_test.go:41: func TestRTA(t *testing.T) {
Document how this test works: what the config files are and what syntax they
require (notably the WANT comments).

Could do this at the top of the file as a package comment.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
go/rta/rta_test.go:112: for f := range res.Reachable {
not checking the addrTaken bit?

[adonovan, 2014-11-12 19:01:29]

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go
File go/rta/rta.go (right):

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode39
go/rta/rta.go:39: // analysis, but the algorithm is much faster.
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> Worth documenting the big-O behavior of rta and pta here?

I don't think so.  RTA is O(n) and PTA is O(n^3) but in practice it's much
closer to linear.


> Perhaps include example wall-clock running time for rta vs. pta on a
nontrivial binary.

Done.  (2.1s for RTA vs 5.4 for PTA, running callgraph on itself.)

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode67
go/rta/rta.go:67: // The value indicates whether the function is address-taken.
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> Make the value a struct instead, so it's obvious that existence in the map is
> all that matters.  It's very common to use map[T]bool as a set so that "if
m[t]"
> tests membership; that's not what you mean here.  And a struct would let you
> document the value better:
>   Reachable map[*ssa.Function]Reachability
> 
> type Reachability struct {
>   AddressTaken bool
> }
> 
> or AddrTaken, if you prefer

Done.  (Though not without a grumbly feeling that the righteous uses of
map[T]bool to represent a partial function from T to bool have been penalized by
the uses by sets.)

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode92
go/rta/rta.go:92: atFuncsBySig typeutil.Map
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> addrTakenFuncsBySig

Done.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode120
go/rta/rta.go:120: // AT indicates whether to mark f as "address-taken".
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> s/AT/addrTaken/g
> 
> Then you don't need the comments.

Done.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode148
go/rta/rta.go:148: // visitATFunc is called each time we encounter an
address-taken function f.
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> visitAddrTakenFunc

Done.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go
File go/rta/rta_test.go (right):

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
go/rta/rta_test.go:41: func TestRTA(t *testing.T) {
On 2014/11/12 18:40:16, Sameer Ajmani wrote:
> Document how this test works: what the config files are and what syntax they
> require (notably the WANT comments).
> 
> Could do this at the top of the file as a package comment.

Done.

https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
go/rta/rta_test.go:112: for f := range res.Reachable {
On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> not checking the addrTaken bit?

No, that's not important for the test.

[Sameer Ajmani, 2014-11-12 20:03:57]

On 2014/11/12 19:01:29, adonovan wrote:
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go
> File go/rta/rta.go (right):
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode39
> go/rta/rta.go:39: // analysis, but the algorithm is much faster.
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > Worth documenting the big-O behavior of rta and pta here?
> 
> I don't think so.  RTA is O(n) and PTA is O(n^3) but in practice it's much
> closer to linear.
> 
> 
> > Perhaps include example wall-clock running time for rta vs. pta on a
> nontrivial binary.
> 
> Done.  (2.1s for RTA vs 5.4 for PTA, running callgraph on itself.)
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode67
> go/rta/rta.go:67: // The value indicates whether the function is
address-taken.
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > Make the value a struct instead, so it's obvious that existence in the map
is
> > all that matters.  It's very common to use map[T]bool as a set so that "if
> m[t]"
> > tests membership; that's not what you mean here.  And a struct would let you
> > document the value better:
> >   Reachable map[*ssa.Function]Reachability
> > 
> > type Reachability struct {
> >   AddressTaken bool
> > }
> > 
> > or AddrTaken, if you prefer
> 
> Done.  (Though not without a grumbly feeling that the righteous uses of
> map[T]bool to represent a partial function from T to bool have been penalized
by
> the uses by sets.)
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode92
> go/rta/rta.go:92: atFuncsBySig typeutil.Map
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > addrTakenFuncsBySig
> 
> Done.
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode120
> go/rta/rta.go:120: // AT indicates whether to mark f as "address-taken".
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > s/AT/addrTaken/g
> > 
> > Then you don't need the comments.
> 
> Done.
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta.go#newcode148
> go/rta/rta.go:148: // visitATFunc is called each time we encounter an
> address-taken function f.
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > visitAddrTakenFunc
> 
> Done.
> 
> https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go
> File go/rta/rta_test.go (right):
> 
>
https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
> go/rta/rta_test.go:41: func TestRTA(t *testing.T) {
> On 2014/11/12 18:40:16, Sameer Ajmani wrote:
> > Document how this test works: what the config files are and what syntax they
> > require (notably the WANT comments).
> > 
> > Could do this at the top of the file as a package comment.
> 
> Done.
> 
>
https://codereview.appspot.com/124690043/diff/140001/go/rta/rta_test.go#newco...
> go/rta/rta_test.go:112: for f := range res.Reachable {
> On 2014/11/12 18:40:15, Sameer Ajmani wrote:
> > not checking the addrTaken bit?
> 
> No, that's not important for the test.

LGTM

[adonovan, 2014-11-12 22:34:18]

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

go.tools/go/rta: implement Rapid Type Analysis for Go.

This is an algorithm for callgraph construction that is faster
but much less precise than pointer analysis.
(I evaluated this for the Go Oracle last year but shelved it,
but it's a natural fit for the work Brian is doing on
automatic program minimization.)

LGTM=sameer
R=gri, crawshaw, sameer
CC=bwkster, golang-codereviews
https://codereview.appspot.com/124690043