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

cmd/compile: infinite loop in -m=2 #35518

Open
mdempsky opened this issue Nov 11, 2019 · 8 comments
Assignees
Labels
Milestone

Comments

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 11, 2019

This compilation unit goes into an infinite loop when compiled with -m=2:

package x

type Node struct {
	Orig *Node
}

func (n *Node) copy() *Node {
	x := *n
	x.Orig = &x
	return &x
}

func f(n0 *Node) {
	n1 := n0.copy()
	n2 := n1.copy()
	sink = n2
}

var sink *Node

Distilled from cmd/compile/internal/gc, pointed out by @dr2chase .

@mdempsky mdempsky added this to the Go1.14 milestone Nov 11, 2019
@mdempsky mdempsky self-assigned this Nov 11, 2019
@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 11, 2019

Further simplified:

package x

type Node struct {
	Orig *Node
}

var sink *Node

func f() {
	var n Node
	n.Orig = &n

	m := n
	sink = &m
}
@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 11, 2019

And here's a loop involving multiple nodes:

package x

type Node struct {
	Orig *Node
}

var sink *Node

func f() {
	var n0, n1 Node
	n0.Orig = &n1
	n1 = n0

	m := n1
	sink = &m
}
@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 12, 2019

Interestingly, esc.go -m=2 doesn't seem to have printed an explanation for either of these cases, because they're "moved to heap" escapes rather than "escapes to heap".

@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 12, 2019

Go 1.13 didn't print anything useful about why these variables were heap allocated, so I don't think it's release critical that Go 1.14 print anything useful for them either. But it is release critical to not infinite loop compiling with -m=2.

Properly handling loops like this will require a bit more restructuring to the walk code, which I don't feel comfortable doing this late in the release. I'm inclined to simply detect that we've hit a loop, print a warning that the path is incomplete, and return. We can figure out how to better diagnose these rho-shaped loops in Go 1.15.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Nov 12, 2019

Change https://golang.org/cl/206619 mentions this issue: cmd/compile: fix -m=2 infinite loop in escape.go

@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 12, 2019

And finally, here's an example where the original node isn't part of the assignment cycle:

package x

type Node struct {
	Orig *Node
}

var sink *Node

func f() {
	var n1, n2 Node
	n1.Orig = &n1
	n1.Orig = &n2

	sink = n1.Orig.Orig
}

Context: I was wondering if CL 206619 was overkill, and I could just check if we loop back to src again rather than keeping track of every visited location. This example shows checking for src alone is insufficient to detect cycles.

gopherbot pushed a commit that referenced this issue Nov 12, 2019
This CL detects infinite loops due to negative dereference cycles
during escape analysis, and terminates the loop gracefully. We still
fail to print a complete explanation of the escape path, but esc.go
didn't print *any* explanation for these test cases, so the release
blocking issue here is simply that we don't infinite loop.

Updates #35518.

Change-Id: I39beed036e5a685706248852f1fa619af3b7abbc
Reviewed-on: https://go-review.googlesource.com/c/go/+/206619
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Nov 12, 2019

Change https://golang.org/cl/206820 mentions this issue: test: add another test case for #35518

@mdempsky mdempsky modified the milestones: Go1.14, Backlog Nov 12, 2019
@mdempsky

This comment has been minimized.

Copy link
Member Author

@mdempsky mdempsky commented Nov 12, 2019

Since CL 206619 is submitted, this isn't a release blocker for Go 1.14 anymore.

The underlying issue that there can be cycles in the escape path and we should ideally explain that properly is still a concern though.

gopherbot pushed a commit that referenced this issue Nov 12, 2019
Updates #35518.

Change-Id: Icd052c8c68aae32696b5831a29e04cc4cb224b06
Reviewed-on: https://go-review.googlesource.com/c/go/+/206820
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.