cmd/compile: fix exponential-time init-cycle reporting

I have a real 7,000-line Go program (not so big)
that took over two minutes to report a trivial init cycle.
I thought the compiler was in an infinite loop but
it was actually just very slow.

CL 170062 rewrote init cycle reporting but replaced
a linear-time algorithm with an exponential one:
it explores all paths through the call graph of functions
involved in the cycle.

The net effect was that  Go 1.12 took 0.25 seconds to load,
typecheck, and then diagnose the cycle in my program,
while Go 1.13 takes 600X longer.

This CL makes the new reporting code run in linear time,
restoring the speed of Go 1.12 but preserving the semantic
fixes from CL 170062.

Change-Id: I7d6dc95676d577d9b96f5953b516a64db93249bf
Reviewed-on: https://go-review.googlesource.com/c/go/+/282314
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

1 files changed, 36 insertions, 0 deletions

diff --git a/test/initexp.go b/test/initexp.go
new file mode 100644
index 0000000000..f279a7c528
--- /dev/null
+++ b/test/initexp.go
@@ -0,0 +1,36 @@
+// errorcheck -t 10
+
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package p
+
+// The init cycle diagnosis used to take exponential time
+// to traverse the call graph paths. This test case takes
+// at least two minutes on a modern laptop with the bug
+// and runs in a fraction of a second without it.
+// 10 seconds (-t 10 above) should be plenty if the code is working.
+
+var x = f() + z() // ERROR "initialization loop"
+
+func f() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func z() int { return x }
+
+func a1() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a2() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a3() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a4() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a5() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a6() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a7() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+func a8() int { return b1() + b2() + b3() + b4() + b5() + b6() + b7() }
+
+func b1() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b2() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b3() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b4() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b5() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b6() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b7() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }
+func b8() int { return a1() + a2() + a3() + a4() + a5() + a6() + a7() }