go.tools/go/ssa: introduce a sanity check for dead referrers

go.tools/go/ssa: introduce a sanity check for dead referrers

This extends the sanity checker to identify and report referrers
which do not appear in the function's instruction lists, and fixes two
bugs in the lifting algorithm which were caught by the sanity check.

[adonovan, 2014-07-07 14:31:53]

Thanks for fixing this.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go
File go/ssa/lift.go (right):

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode213
go/ssa/lift.go:213: if prefs := newval.Referrers(); prefs != nil {
Could you break out the if-body into a little function?  Like so:

for _, v := range np.phi.Edges {
    if refs := v.Referrers(); refs != nil {
        *refs = removeInstr(*refs, np.phi)
    }
}

func removeInstr([]Instruction, Instruction) []Instruction { ... }

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode215
go/ssa/lift.go:215: k := 0
I tend to use 'o' for the output index, but 'i' is fine if this is broken out
into a little function.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode222
go/ssa/lift.go:222: }
Also nil out the pointers between len and cap in the slice, so the Phi can be
reclaimed by GC.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode515
go/ssa/lift.go:515: rs := *refs
I think you can call removeInstr again here:

if refs := instr.Val.Referrers(); refs != nil {
    *refs = removeInstr(*refs, instr)
}

Your code here stops at the first match, whereas removeInstr does not.  The only
case where this could matter is when the same operand appears twice, which means
hypothetical code like this:

   type T *T
   p := new(T)
   *p = p

but the types dictate an an implicit ChangeType, so in fact the store *p=p would
not have a repeated operand, so I think it never matters.   It might be good to
visually inspect the generated code in this case though.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go
File go/ssa/sanity.go (right):

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode390
go/ssa/sanity.go:390: s.errorf("%s missing referrer list", v)
You want v.Name() here, ideally:

  ("%s has missing referrer list", v.Name())

A value-defining instruction has two aspects, what it defines (which is printed
by Value.Name), and what it consumes/computes, which is printed by
Instruction.String.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode395
go/ssa/sanity.go:395: s.errorf("referrer %d of %s (%s) is dead", i, v, ref)
"%s.Referrers()[%d] = %s is not an instruction belonging to this function",
v.Name(), i, ref

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode441
go/ssa/sanity.go:441: s.instrs[instr] = struct{}{}
Does this extra pass measurably slow down the ssa/interp tests?

[pcc, 2014-07-08 04:13:14]

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go
File go/ssa/lift.go (right):

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode213
go/ssa/lift.go:213: if prefs := newval.Referrers(); prefs != nil {
On 2014/07/07 14:31:53, adonovan wrote:
> Could you break out the if-body into a little function?  Like so:
> 
> for _, v := range np.phi.Edges {
>     if refs := v.Referrers(); refs != nil {
>         *refs = removeInstr(*refs, np.phi)
>     }
> }
> 
> func removeInstr([]Instruction, Instruction) []Instruction { ... }

Done.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode215
go/ssa/lift.go:215: k := 0
On 2014/07/07 14:31:53, adonovan wrote:
> I tend to use 'o' for the output index, but 'i' is fine if this is broken out
> into a little function.

Done.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode222
go/ssa/lift.go:222: }
On 2014/07/07 14:31:53, adonovan wrote:
> Also nil out the pointers between len and cap in the slice, so the Phi can be
> reclaimed by GC.

Done.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/lift.go#newcode515
go/ssa/lift.go:515: rs := *refs
On 2014/07/07 14:31:53, adonovan wrote:
> I think you can call removeInstr again here:
> 
> if refs := instr.Val.Referrers(); refs != nil {
>     *refs = removeInstr(*refs, instr)
> }
> 
> Your code here stops at the first match, whereas removeInstr does not.  The
only
> case where this could matter is when the same operand appears twice, which
means
> hypothetical code like this:
> 
>    type T *T
>    p := new(T)
>    *p = p
> 
> but the types dictate an an implicit ChangeType, so in fact the store *p=p
would
> not have a repeated operand, so I think it never matters.   It might be good
to
> visually inspect the generated code in this case though.

Yes, this code produces a ChangeType.

I've changed it to call removeInstr, as I don't think it's worth having another
implementation here.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go
File go/ssa/sanity.go (right):

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode390
go/ssa/sanity.go:390: s.errorf("%s missing referrer list", v)
On 2014/07/07 14:31:53, adonovan wrote:
> You want v.Name() here, ideally:
> 
>   ("%s has missing referrer list", v.Name())
> 
> A value-defining instruction has two aspects, what it defines (which is
printed
> by Value.Name), and what it consumes/computes, which is printed by
> Instruction.String.

Done.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode395
go/ssa/sanity.go:395: s.errorf("referrer %d of %s (%s) is dead", i, v, ref)
On 2014/07/07 14:31:53, adonovan wrote:
> "%s.Referrers()[%d] = %s is not an instruction belonging to this function",
> v.Name(), i, ref

Done.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode441
go/ssa/sanity.go:441: s.instrs[instr] = struct{}{}
On 2014/07/07 14:31:53, adonovan wrote:
> Does this extra pass measurably slow down the ssa/interp tests?

I ran a best-of-three experiment which showed a ~3% slowdown. Is it worth trying
to optimize this? We probably don't care much about sanity checker performance,
right?

[adonovan, 2014-07-08 07:49:02]

LGTM

Thanks again.

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go
File go/ssa/sanity.go (right):

https://codereview.appspot.com/110210045/diff/20001/go/ssa/sanity.go#newcode441
go/ssa/sanity.go:441: s.instrs[instr] = struct{}{}
On 2014/07/08 04:13:14, pcc wrote:
> On 2014/07/07 14:31:53, adonovan wrote:
> > Does this extra pass measurably slow down the ssa/interp tests?
> 
> I ran a best-of-three experiment which showed a ~3% slowdown. Is it worth
trying
> to optimize this? We probably don't care much about sanity checker
performance,
> right?

3% is fine.  Thanks for measuring it.

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go
File go/ssa/lift.go (right):

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go#newcode120
go/ssa/lift.go:120: for tail := i; tail != len(refs); tail++ {
s/tail/j/g

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go#newcode121
go/ssa/lift.go:121: refs[tail] = nil
refs[j] = nil // aid GC

[pcc, 2014-07-10 01:51:05]

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go
File go/ssa/lift.go (right):

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go#newcode120
go/ssa/lift.go:120: for tail := i; tail != len(refs); tail++ {
On 2014/07/08 07:49:02, adonovan wrote:
> s/tail/j/g

Done.

https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go#newcode121
go/ssa/lift.go:121: refs[tail] = nil
On 2014/07/08 07:49:02, adonovan wrote:
> refs[j] = nil // aid GC

Done.

[adonovan, 2014-07-10 10:27:07]

LGTM
Thanks again.
Submitting...


On 9 July 2014 21:51, <pcc@google.com> wrote:

>
> https://codereview.appspot.com/110210045/diff/40001/go/ssa/lift.go
> File go/ssa/lift.go (right):
>
> https://codereview.appspot.com/110210045/diff/40001/go/
> ssa/lift.go#newcode120
> go/ssa/lift.go:120: for tail := i; tail != len(refs); tail++ {
> On 2014/07/08 07:49:02, adonovan wrote:
>
>> s/tail/j/g
>>
>
> Done.
>
>
> https://codereview.appspot.com/110210045/diff/40001/go/
> ssa/lift.go#newcode121
> go/ssa/lift.go:121: refs[tail] = nil
> On 2014/07/08 07:49:02, adonovan wrote:
>
>> refs[j] = nil // aid GC
>>
>
> Done.
>
> https://codereview.appspot.com/110210045/
>

[adonovan, 2014-07-10 10:27:28]

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

go.tools/go/ssa: introduce a sanity check for dead referrers

This extends the sanity checker to identify and report referrers
which do not appear in the function's instruction lists, and fixes two
bugs in the lifting algorithm which were caught by the sanity check.

LGTM=adonovan
R=adonovan
CC=axwalk, golang-codereviews
https://codereview.appspot.com/110210045

Committer: Alan Donovan <adonovan@google.com>