cmd/compile: allow mid-stack inlining when there is a cycle of recursion

We still disallow inlining for an immediately-recursive function, but allow
inlining if a function is in a recursion chain.

If all functions in the recursion chain are simple, then we could inline
forever down the recursion chain (eventually running out of stack on the
compiler), so we add a map to keep track of the functions we have
already inlined at a call site. We stop inlining when we reach a
function that we have already inlined in the recursive chain. Of course,
normally the inlining will have stopped earlier, because of the cost
function.

We could also limit the depth of inlining by a simple count (say, limit
max inlining of 10 at any given site). Would that limit other
opportunities too much?

Added a test in test/inline.go. runtime.BenchmarkStackCopyNoCache() is
also already a good test that triggers the check to stop inlining
when we reach the start of the recursive chain again.

For the bent benchmark suite, the performance improvement was mostly not
statistically significant, but the geomean averaged out to: -0.68%. The text size
increase was less than .1% for all bent benchmarks. The cmd/go text size increase
was 0.02% and the cmd/compile text size increase was .1%.

Fixes #29737

Change-Id: I892fa84bb07a947b3125ec8f25ed0e508bf2bdf5
Reviewed-on: https://go-review.googlesource.com/c/go/+/226818
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 18 insertions, 0 deletions

diff --git a/test/inline.go b/test/inline.go
index 8ebffedfb7..0b3ad55d46 100644
--- a/test/inline.go
+++ b/test/inline.go
@@ -180,3 +180,21 @@ func (T) meth2(int, int) { // not inlineable - has 2 calls.
 	runtime.GC()
 	runtime.GC()
 }
+
+// Issue #29737 - make sure we can do inlining for a chain of recursive functions
+func ee() { // ERROR "can inline ee"
+	ff(100) // ERROR "inlining call to ff" "inlining call to gg" "inlining call to hh"
+}
+
+func ff(x int) { // ERROR "can inline ff"
+	if x < 0 {
+		return
+	}
+	gg(x - 1)
+}
+func gg(x int) { // ERROR "can inline gg"
+	hh(x - 1)
+}
+func hh(x int) { // ERROR "can inline hh"
+	ff(x - 1) // ERROR "inlining call to ff"  // ERROR "inlining call to gg"
+}