1 // Copyright 2024 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 package ssa
6 7 import (
8 "sync/atomic"
9 )
10 11 // Each task has two states: it is initially "active",
12 // and transitions to "done".
13 //
14 // tasks form a directed graph. An edge from x to y (with y in x.edges)
15 // indicates that the task x waits on the task y to be done.
16 // Cycles are permitted.
17 //
18 // Calling x.wait() blocks the calling goroutine until task x,
19 // and all the tasks transitively reachable from x are done.
20 //
21 // The nil *task is always considered done.
22 type task struct {
23 done chan unit // close when the task is done.
24 edges map[*task]unit // set of predecessors of this task.
25 transitive atomic.Bool // true once it is known all predecessors are done.
26 }
27 28 func (x *task) isTransitivelyDone() bool { return x == nil || x.transitive.Load() }
29 30 // addEdge creates an edge from x to y, indicating that
31 // x.wait() will not return before y is done.
32 // All calls to x.addEdge(...) should happen before x.markDone().
33 func (x *task) addEdge(y *task) {
34 if x == y || y.isTransitivelyDone() {
35 return // no work remaining
36 }
37 38 // heuristic done check
39 select {
40 case <-x.done:
41 panic("cannot add an edge to a done task")
42 default:
43 }
44 45 if x.edges == nil {
46 x.edges = make(map[*task]unit)
47 }
48 x.edges[y] = unit{}
49 }
50 51 // markDone changes the task's state to markDone.
52 func (x *task) markDone() {
53 if x != nil {
54 close(x.done)
55 }
56 }
57 58 // wait blocks until x and all the tasks it can reach through edges are done.
59 func (x *task) wait() {
60 if x.isTransitivelyDone() {
61 return // already known to be done. Skip allocations.
62 }
63 64 // Use BFS to wait on u.done to be closed, for all u transitively
65 // reachable from x via edges.
66 //
67 // This work can be repeated by multiple workers doing wait().
68 //
69 // Note: Tarjan's SCC algorithm is able to mark SCCs as transitively done
70 // as soon as the SCC has been visited. This is theoretically faster, but is
71 // a more complex algorithm. Until we have evidence, we need the more complex
72 // algorithm, the simpler algorithm BFS is implemented.
73 //
74 // In Go 1.23, ssa/TestStdlib reaches <=3 *tasks per wait() in most schedules
75 // On some schedules, there is a cycle building net/http and internal/trace/testtrace
76 // due to slices functions.
77 work := []*task{x}
78 enqueued := map[*task]unit{x: {}}
79 for i := 0; i < len(work); i++ {
80 u := work[i]
81 if u.isTransitivelyDone() { // already transitively done
82 work[i] = nil
83 continue
84 }
85 <-u.done // wait for u to be marked done.
86 87 for v := range u.edges {
88 if _, ok := enqueued[v]; !ok {
89 enqueued[v] = unit{}
90 work = append(work, v)
91 }
92 }
93 }
94 95 // work is transitively closed over dependencies.
96 // u in work is done (or transitively done and skipped).
97 // u is transitively done.
98 for _, u := range work {
99 if u != nil {
100 x.transitive.Store(true)
101 }
102 }
103 }
104