diff options
| -rw-r--r-- | src/cmd/compile/internal/gc/initorder.go | 19 | ||||
| -rw-r--r-- | test/initexp.go | 36 |
2 files changed, 47 insertions, 8 deletions
diff --git a/src/cmd/compile/internal/gc/initorder.go b/src/cmd/compile/internal/gc/initorder.go index 41f1349bbe..e2084fd038 100644 --- a/src/cmd/compile/internal/gc/initorder.go +++ b/src/cmd/compile/internal/gc/initorder.go @@ -108,7 +108,7 @@ func initOrder(l []*Node) []*Node { errorexit() } - findInitLoopAndExit(firstLHS(n), new([]*Node)) + findInitLoopAndExit(firstLHS(n), new([]*Node), make(map[*Node]bool)) Fatalf("initialization unfinished, but failed to identify loop") } } @@ -181,10 +181,7 @@ func (o *InitOrder) flushReady(initialize func(*Node)) { // path points to a slice used for tracking the sequence of // variables/functions visited. Using a pointer to a slice allows the // slice capacity to grow and limit reallocations. -func findInitLoopAndExit(n *Node, path *[]*Node) { - // We implement a simple DFS loop-finding algorithm. This - // could be faster, but initialization cycles are rare. - +func findInitLoopAndExit(n *Node, path *[]*Node, ok map[*Node]bool) { for i, x := range *path { if x == n { reportInitLoopAndExit((*path)[i:]) @@ -201,12 +198,18 @@ func findInitLoopAndExit(n *Node, path *[]*Node) { *path = append(*path, n) for _, ref := range refers { // Short-circuit variables that were initialized. - if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone { + if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone || ok[ref] { continue } - - findInitLoopAndExit(ref, path) + findInitLoopAndExit(ref, path, ok) } + + // n is not involved in a cycle. + // Record that fact to avoid checking it again when reached another way, + // or else this traversal will take exponential time traversing all paths + // through the part of the package's call graph implicated in the cycle. + ok[n] = true + *path = (*path)[:len(*path)-1] } 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() } |