Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

cmd/compile: bad liveness map #20029

Closed
randall77 opened this issue Apr 18, 2017 · 8 comments
Closed

cmd/compile: bad liveness map #20029

randall77 opened this issue Apr 18, 2017 · 8 comments
Labels
FrozenDueToAge
Milestone
Go1.8.3

Comments

@randall77
Copy link
Contributor 

package main

import "runtime"

func f(m map[int]int) {
outer:
        for i := 0; i < 10; i++ {
                for k := range m {
                        if k == 5 {
                                continue outer
                        }
                }
                runtime.GC()
                break
        }
        runtime.GC()
}

$ go tool compile -live tmp1.go
tmp1.go:5:18: live at entry to f: m
tmp1.go:8:12: live at call to mapiterinit: m .autotmp_4
tmp1.go:8:12: live at call to mapiternext: m .autotmp_4
tmp1.go:16:12: f: .autotmp_4 (type map.iter[int]int) is ambiguously live
tmp1.go:16:12: live at call to GC: .autotmp_4

The hiter for the inner loop (.autotmp_4) should not be live at the outer runtime.GC. It is live because liveness analysis sort of gives up on it (the "ambiguously live" comment there).
That's not so bad in and of itself; it's just imprecise.

But at the end of the inner loop we issue a VARKILL of .autotmp_4, so it definitely isn't live at the first runtime.GC (nothing with a pointer is live at that call, so it isn't even listed by -live). That means .autotmp_4 is live, then it isn't, then it is again. The first runtime.GC will free m, as nothing is holding m live at this point. The second runtime.GC finds m inside .autotmp_4 and tries to scan an already freed map. Boom.

This seems like a bad interaction between ambiguously live and VARKILL. Maybe fundamentally bad. Time to put my pondering cap on...

@aclements
@randall77 randall77 self-assigned this Apr 18, 2017
@randall77 randall77 added this to the Go1.9 milestone Apr 18, 2017
@randall77
Copy link
Contributor Author

1.9 for now. Likely will be promoted to 1.8.2.

@randall77
Copy link
Contributor Author

Maybe VARKILL for ambiguously live variables should do an explicit zeroing?

@randall77
Copy link
Contributor Author

Another fix would be to somehow get a VARKILL of the hiter at the "continue outer" statement. I'm not sure if that would be a complete fix. It's also hard to generate such a kill in order.go.

@randall77
Copy link
Contributor Author

I hacked up a fix to explicitly zero at VARKILLs of ambiguously live variables.

The hack is definitely a hack. The challenge here is that we don't know a variable is ambiguously live until very late in compilation, after regalloc & friends. So, for example, we can't clobber any registers to do the zeroing. And it is after lowering, so we'd need to repeat the logic for each architecture. Maybe we could push liveness analysis (or at least ambiguity analysis) earlier, but I suspect that would be hard. Maybe VARKILL can clobber a few registers on architectures that need it.

It only triggers once during make.bash and once more during go test std (in (*Checker).caseTypes and TestMapSparseIterOrder, in case you were wondering) so I'm not worried about efficiency very much. Just something simple should be adequate.

I'll see if I can get a CL out tomorrow.

@randall77 randall77 modified the milestones: Go1.8.2, Go1.9 Apr 21, 2017
@randall77 randall77 reopened this Apr 21, 2017
@randall77
Copy link
Contributor Author

Reopening for 1.8.2 consideration.

@gopherbot
Copy link

CL https://golang.org/cl/41076 mentions this issue.

@bradfitz bradfitz modified the milestones: Go1.8.2, Go1.8.3 May 18, 2017
@broady
Copy link
Contributor

broady commented May 23, 2017

The change doesn't apply cleanly to the 1.8 branch. @randall77, can you PTAL?

@gopherbot
Copy link

CL https://golang.org/cl/43998 mentions this issue.

gopherbot pushed a commit that referenced this issue May 24, 2017
@randall77
[release-branch.go1.8] cmd/compile: zero ambiguously live variables a…
e396667 
…t VARKILLs

This is a redo of CL 41076 backported to the 1.8 release branch.
There were major conflicts, so I had to basically rewrite it again
from scratch.  The way Progs are allocated changed.  Liveness analysis
and Prog generation got reordered.  Liveness analysis changed from
running on gc.BasicBlock to ssa.Block.  All that makes the logic quite
a bit different.

Please review carefully.

From CL 41076:

At VARKILLs, zero a variable if it is ambiguously live.
After the VARKILL anything this variable references
might be collected. If it were to become live again later,
the GC will see references to already-collected objects.

We don't know a variable is ambiguously live until very
late in compilation (after lowering, register allocation, ...),
so it is hard to generate the code in an arch-independent way.
We also have to be careful not to clobber any registers.
Fortunately, this almost never happens so performance is ~irrelevant.

There are only 2 instances where this triggers in the stdlib.

Fixes #20029

Change-Id: Ibb757eec58ee07f40df5e561b19d315684dc4bda
Reviewed-on: https://go-review.googlesource.com/43998
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@broady broady closed this as completed May 24, 2017
@golang golang locked and limited conversation to collaborators May 24, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.8.3
Development

No branches or pull requests
4 participants
@bradfitz @broady @randall77 @gopherbot