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: relax recursive restriction while inlining #29737

Closed
randall77 opened this issue Jan 14, 2019 · 6 comments
Closed

cmd/compile: relax recursive restriction while inlining #29737

randall77 opened this issue Jan 14, 2019 · 6 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Backlog

Comments

@randall77
Copy link
Contributor 

package main

func main() {
	f(100)
}

func f(x int) {
	if x < 0 {
		return
	}
	g(x - 1)
}
func g(x int) {
	h(x - 1)
}
func h(x int) {
	f(x - 1)
}

The compiler refuses to inline anything in this example:

$ go tool compile -m=2 tmp.go
tmp.go:7:6: cannot inline f: recursive
tmp.go:13:6: cannot inline g: recursive
tmp.go:16:6: cannot inline h: recursive
tmp.go:3:6: can inline main as: func() { f(100) }

There's no reason to not inline, e.g., g into f.
As long as we're not inlining a function into itself, it should be ok (and even that might be ok, as long as we don't do it an infinite number of times).

This comes up only with mid-stack inlining. When we only inlined leaves, it was perfectly reasonable to abort on recursion. Now we don't have to.

This came up when looking at runtime.pcdatavalue. I had a CL (CL 157799) which modified it, and the modified version should have inlined. It didn't because of this issue, because pcdatavalue it is part of a reasonably large recursive loop.
@randall77 randall77 added this to the Go1.13 milestone Jan 14, 2019
@randall77
Copy link
Contributor Author

@josharian

@josharian
Copy link
Contributor

This might also help with a problem @CAFxX ran into (which also has another possible solution).

@randall77
Copy link
Contributor Author

Nothing planned for 1.13, punting.

@randall77 randall77 modified the milestones: Go1.13, Go1.14 May 6, 2019
@bcmills bcmills added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label May 28, 2019
@CAFxX
Copy link
Contributor

CAFxX commented Jul 29, 2019 •
edited

I just ran into a similar problem again; also in my case the recursion loop was fairly big and, crucially, it contained non-inlineable functions (both way over budget as well as containing non-inlineable constructs).

In the spirit of @josharian's CL this would require filtering out not just functions marked as noinline, but also any function that effectively has no chances of being inlined.

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@gopherbot
Copy link

Change https://golang.org/cl/226818 mentions this issue: cmd/compile: allow mid-stack inlining when there is a cycle of recursion

@gopherbot
Copy link

Change https://golang.org/cl/227346 mentions this issue: runtime/pprof: clarify recursive inline heuristic

gopherbot pushed a commit that referenced this issue Apr 13, 2020
@prattmic
runtime/pprof: clarify recursive inline heuristic
ce52871 
Following CL 226818, the compiler will allow inlining a single cycle in
an inline chain. Immediately-recursive functions are still disallowed,
which is what this heuristic refers to.

Add a regression test for this case.

Note that in addition to this check, if the compiler were to inline
multiple cycles via a loop (i.e., rather than appending duplicate code),
much more work would be required here to handle a single address
appearing in multiple different inline frames.

Updates #29737

Change-Id: I88de15cfbeabb9c04381e1c12cc36778623132a5
Reviewed-on: https://go-review.googlesource.com/c/go/+/227346
Run-TryBot: Michael Pratt <mpratt@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Dan Scales <danscales@google.com>
Reviewed-by: Hyang-Ah Hana Kim <hyangah@gmail.com>
@golang golang locked and limited conversation to collaborators Apr 6, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
6 participants
@josharian @rsc @CAFxX @bcmills @randall77 @gopherbot