code review 36710043: go.tools/ssa: FindSwitches() utility infers multiway br...

go.tools/ssa/ssautil: Switches() utility infers multiway branches.

(Note new subpackage ssa/ssautil.)

[adonovan, 2013-12-03 20:58:27]

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

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

[axw, 2013-12-04 00:36:22]

On 2013/12/03 20:58:27, adonovan wrote:
> Hello mailto:gri@golang.org, mailto:axwalk@gmail.com (cc:
mailto:golang-dev@googlegroups.com),
> 
> I'd like you to review this change to
> https://code.google.com/p/go.tools/

Yes, I think this will be useful. LLVM has a switch instruction
(http://llvm.org/docs/LangRef.html#switch-instruction) that can be used with
this.

[gri1, 2013-12-04 01:09:49]

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go
File ssa/findswitch.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode14
ssa/findswitch.go:14: // - a lookup table (for a switch that maps constants to
constants)
this would also require that the switch simply produces a new constant value in
each case - not sure this is worthwhile detecting, especially because this case
tends to be easily written by hand as a map/lookup table

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode28
ssa/findswitch.go:28: type FoundSwitchCase struct {
odd name

ConstCase?

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode38
ssa/findswitch.go:38: type FoundSwitch struct {
odd name

ConstSwitch?
Switch?

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode68
ssa/findswitch.go:68: // 'switch' keyword in the source: for example, single a
source-level
s/single a/a single/ ?

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode70
ssa/findswitch.go:70: // many FoundSwitches, one per plural sequence of constant
cases.
s/plural // ?

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode103
ssa/findswitch.go:103: // block contains not just 'if x == v',
The block

(since you're writing a sentence)

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode105
ssa/findswitch.go:105: // making it unsafe to elide.
s/making/make/

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode109
ssa/findswitch.go:109: // block has multiple predecessors,
The block

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode145
ssa/findswitch.go:145: func domorder(fn *Function) []*BasicBlock {
domOrder

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go
File ssa/findswitch_test.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go#new...
ssa/findswitch_test.go:21: // of its first instruction (e.g. "print(42)")
the example is not very informative

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go#new...
ssa/findswitch_test.go:59: // Each (multiline) "switch" comment within
multi-line

https://codereview.appspot.com/36710043/diff/20001/ssa/testdata/findswitches.go
File ssa/testdata/findswitches.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/testdata/findswitches....
ssa/testdata/findswitches.go:13: // switch x {
You should try to change your tests such that these comments are the function
documentation. Then you can simply look at the ast.FuncDecl.Doc field instead of
having to extract comments tediously. The Doc field contains this comment, and
by using the CommentText (or Text?) method of that CommentGroup you get the
comment text. Should simplify the testing code.

It does mean that you need to write a new function for each case, but that seems
ok.

[adonovan, 2013-12-04 02:43:43]

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go
File ssa/findswitch.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode14
ssa/findswitch.go:14: // - a lookup table (for a switch that maps constants to
constants)
On 2013/12/04 01:09:49, gri1 wrote:
> this would also require that the switch simply produces a new constant value
in
> each case - not sure this is worthwhile detecting, especially because this
case
> tends to be easily written by hand as a map/lookup table

You're right about the restriction to constants, but it's not uncommon,
especially for type switches, and a compiled lookup table executes much faster
than a hash-table lookup.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode28
ssa/findswitch.go:28: type FoundSwitchCase struct {
On 2013/12/04 01:09:49, gri1 wrote:
> odd name
> 
> ConstCase?

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode38
ssa/findswitch.go:38: type FoundSwitch struct {
On 2013/12/04 01:09:49, gri1 wrote:
> odd name
> 
> ConstSwitch?
> Switch?

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode68
ssa/findswitch.go:68: // 'switch' keyword in the source: for example, single a
source-level
On 2013/12/04 01:09:49, gri1 wrote:
> s/single a/a single/ ?

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode70
ssa/findswitch.go:70: // many FoundSwitches, one per plural sequence of constant
cases.
On 2013/12/04 01:09:49, gri1 wrote:
> s/plural // ?

It signifies that an empty or singleton sequence is ignored by this algorithm.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode103
ssa/findswitch.go:103: // block contains not just 'if x == v',
On 2013/12/04 01:09:49, gri1 wrote:
> The block
> 
> (since you're writing a sentence)

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode105
ssa/findswitch.go:105: // making it unsafe to elide.
On 2013/12/04 01:09:49, gri1 wrote:
> s/making/make/

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode109
ssa/findswitch.go:109: // block has multiple predecessors,
On 2013/12/04 01:09:49, gri1 wrote:
> The block

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch.go#newcode145
ssa/findswitch.go:145: func domorder(fn *Function) []*BasicBlock {
On 2013/12/04 01:09:49, gri1 wrote:
> domOrder

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go
File ssa/findswitch_test.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go#new...
ssa/findswitch_test.go:21: // of its first instruction (e.g. "print(42)")
On 2013/12/04 01:09:49, gri1 wrote:
> the example is not very informative

Now:
// In this test, we will represent each block                                   
// by the String() of its first Instruction,                                    
// e.g. "print(42:int)".

https://codereview.appspot.com/36710043/diff/20001/ssa/findswitch_test.go#new...
ssa/findswitch_test.go:59: // Each (multiline) "switch" comment within
On 2013/12/04 01:09:49, gri1 wrote:
> multi-line

Done.

https://codereview.appspot.com/36710043/diff/20001/ssa/testdata/findswitches.go
File ssa/testdata/findswitches.go (right):

https://codereview.appspot.com/36710043/diff/20001/ssa/testdata/findswitches....
ssa/testdata/findswitches.go:13: // switch x {
On 2013/12/04 01:09:49, gri1 wrote:
> You should try to change your tests such that these comments are the function
> documentation. Then you can simply look at the ast.FuncDecl.Doc field instead
of
> having to extract comments tediously. 

Extracting them was not at all tedious; it's about four lines of actual code.  I
doubt the alternative would be easier to implement, and IMHO it would be less
nice to use (e.g. per your comment).

[adonovan, 2013-12-04 02:44:15]

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

Please take another look.

[adonovan, 2013-12-05 15:05:14]

NB: now split off into its ssa/ssautil subpackage.

(gri: please add this to your 'working set' for tests.)


On 3 December 2013 21:44, <adonovan@google.com> wrote:

> Hello gri@golang.org, axwalk@gmail.com, gri@google.com (cc:
> golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> https://codereview.appspot.com/36710043/
>

[gri1, 2013-12-05 18:04:35]

Should the findswitch.go file now simple be called switch.go ?

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go
File ssa/ssautil/findswitch.go (right):

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:18: // - a two-level switch (to partition constant
strings by their first byte).
what happens if there are fallthroughs?

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:50: // Exactly one of ConstCases and TypeCases is
non-empty.
non-empty or non-nil?

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:59: X          ssa.Value       // the switch operand
s/X/Value/

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:59: X          ssa.Value       // the switch operand
// value to switch on

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:66: // We represent each block by the String() of its
s/by/with/ ?

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:68: // This is a favour to the tests.
leave last sentence away - no need

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:70: if sw.ConstCases != nil {
here you're checking against nil, not len(sw.ConstCases) == 0 so the comment
about non-empty lists should be clearer

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
File ssa/ssautil/testdata/findswitches.go (right):

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:6: // Each multiway conditional with pure
constant cases (FoundSwitch)
FoundSwitch is now called Switch

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:27: fallthrough
I don't understand how the fallthrough is represented above

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:84: // case 3:int: print(34:int)
shouldn't the "body" of 3 and 4 be combined? (and as such reflected in the
String form?)

[adonovan, 2013-12-05 19:26:58]

> Should the findswitch.go file now simple be called switch.go ?

Done.  Also s/FindSwitches/Switches/g.

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go
File ssa/ssautil/findswitch.go (right):

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:18: // - a two-level switch (to partition constant
strings by their first byte).
On 2013/12/05 18:04:35, gri1 wrote:
> what happens if there are fallthroughs?

Comment is now:
// The optimal choice will
// depend on the data type, the specific case values, the code in the
// bodies of each case, and the hardware.

As far as this algorithm is concerned, the body of each case doesn't matter; it
can have arbitrary control flow.  If the client cares, it can look at the body.

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:50: // Exactly one of ConstCases and TypeCases is
non-empty.
On 2013/12/05 18:04:35, gri1 wrote:
> non-empty or non-nil?

Changed to be excruciatingly specific:

// One of ConstCases and TypeCases has length at least two; the other
// is nil.

(There's no single word to express nil <=> empty.)

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:59: X          ssa.Value       // the switch operand
On 2013/12/05 18:04:35, gri1 wrote:
> s/X/Value/

We use X liberally in ast.Expr and ssa.Instruction; why not here too?

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:66: // We represent each block by the String() of its
On 2013/12/05 18:04:35, gri1 wrote:
> s/by/with/ ?

Isn't "by" better here?  Merriam Webster has "represent by" but not "represent
with".

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:68: // This is a favour to the tests.
On 2013/12/05 18:04:35, gri1 wrote:
> leave last sentence away - no need

Removed.  (My point was that using the basic block names is more consistent with
ssa.Instruction.String(), but makes testing harder.)

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/findswitch.go...
ssa/ssautil/findswitch.go:70: if sw.ConstCases != nil {
On 2013/12/05 18:04:35, gri1 wrote:
> here you're checking against nil, not len(sw.ConstCases) == 0 so the comment
> about non-empty lists should be clearer

Clarified as suggested.

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
File ssa/ssautil/testdata/findswitches.go (right):

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:6: // Each multiway conditional with pure
constant cases (FoundSwitch)
On 2013/12/05 18:04:35, gri1 wrote:
> FoundSwitch is now called Switch

Done.

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:27: fallthrough
On 2013/12/05 18:04:35, gri1 wrote:
> I don't understand how the fallthrough is represented above

It doesn't---it's irrelevant to the test. It's there to ensure it doesn't affect
the result, but I could remove it if it's confusing.

https://codereview.appspot.com/36710043/diff/120001/ssa/ssautil/testdata/find...
ssa/ssautil/testdata/findswitches.go:84: // case 3:int: print(34:int)
On 2013/12/05 18:04:35, gri1 wrote:
> shouldn't the "body" of 3 and 4 be combined? (and as such reflected in the
> String form?)

I thought about it, but what if the first and third---but not second---cases
shared the same body?  (This is possible for switches found from ad-hoc control
flow.)  Should String() consolidate all such cases together, or only show
contiguous ones?  Since this is really just for debugging and testing (not ssa
disassembly) I just did the simplest thing.

[gri1, 2013-12-05 20:19:02]

LGTM

https://codereview.appspot.com/36710043/diff/160001/ssa/ssautil/switch.go
File ssa/ssautil/switch.go (right):

https://codereview.appspot.com/36710043/diff/160001/ssa/ssautil/switch.go#new...
ssa/ssautil/switch.go:51: // One of ConstCases and TypeCases has length at least
two;
has a length of at least 2 ?

or just

has a length >= 2

[adonovan, 2013-12-05 22:00:20]

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

go.tools/ssa/ssautil: Switches() utility infers multiway branches.

(Note new subpackage ssa/ssautil.)

R=gri, axwalk, gri
CC=golang-dev
https://codereview.appspot.com/36710043