[tools] internal/flow: avoid quadratic behavior for loops with many backedges
0 views
Skip to first unread message
Dominik Honnef (Gerrit)
2:13 PM (8 hours ago) 2:13 PM
to goph...@pubsubhelper.golang.org, Dominik Honnef, golang-co...@googlegroups.com
Dominik Honnef has uploaded the change for review![]( "Open in Gerrit")
Commit message
internal/flow: avoid quadratic behavior for loops with many backedges
Consider a loop with many backedges:
for {
switch x {
case 1:
...
case 2:
...
case 3:
...
...
}
}
Its CFG has the following shape:
+-> arm 0 --+
| |
entry -> header -> ... -+-+
^ | | |
| +-> arm N --+ |
+---------------+
Now consider a bit-vectoring data-flow problem in which each arm
contributes a distinct bit.
With a single reverse post-order (RPO) priority queue, an update from an
arm immediately makes the header the highest-priority node. This
reprocesses the header and its successors before the remaining arm
updates can be coalesced. For n arms, this results in n(n+3)/2 arm
visits.
Instead, process nodes in RPO sweeps. Maintain an active priority queue
and a deferred worklist. If an update targets a node whose RPO position
has already been passed in the current sweep, add it to the deferred
worklist. Once the active queue is empty, promote the deferred worklist
and begin another sweep.
This allows all arms to contribute their facts before the header is
revisited. For the example above, each arm is visited once to contribute
its bit and once more with the merged result, for 2n arm visits.
Change-Id: Ia164ac66d7c2cd45b67977b1c8fb53ef6a6a6964
Change diff
diff --git a/internal/flow/forward.go b/internal/flow/forward.go
index d2cb27c..9833da4 100644
--- a/internal/flow/forward.go
+++ b/internal/flow/forward.go
@@ -125,16 +125,19 @@
//
// We use this ordering so forward analysis converges more quickly.
type nodeHeap struct {
- heap []int
- inQueue []int64 // Bitmap over node IDs
- prio []int // NodeID -> priority
+ heap []int // Remaining nodes in the current sweep
+ deferred []int // Nodes of next sweep
+ inQueue []int64 // Bitmap over node IDs
+ prio []int // NodeID -> priority
+ currentPrio int // Priority of last dequeued node, or -1
}
func (h *nodeHeap) init(g graph.Graph[int]) {
nNodes := g.NumNodes()
*h = nodeHeap{
- inQueue: make([]int64, (nNodes+63)/64),
- prio: make([]int, nNodes),
+ inQueue: make([]int64, (nNodes+63)/64),
+ prio: make([]int, nNodes),
+ currentPrio: -1,
}
for p, nid := range graph.ReversePostorder(g) {
h.prio[nid] = p
@@ -146,16 +149,30 @@
return
}
h.inQueue[nid/64] |= 1 << (nid % 64)
- heap.Push(h, nid)
+ if h.prio[nid] <= h.currentPrio {
+ // This is a retreating edge, self-edge, or other update to a node
+ // already passed in this sweep. Coalesce it into the next sweep.
+ h.deferred = append(h.deferred, nid)
+ } else {
+ heap.Push(h, nid)
+ }
}
func (h *nodeHeap) dequeue() int {
+ if len(h.heap) == 0 {
+ // Start the next RPO sweep.
+ h.heap, h.deferred = h.deferred, h.heap[:0]
+ h.currentPrio = -1
+ heap.Init(h)
+ }
nid := h.heap[0]
heap.Pop(h)
h.inQueue[nid/64] &^= 1 << (nid % 64)
+ h.currentPrio = h.prio[nid]
return nid
}
+func (h nodeHeap) pending() bool { return len(h.heap) != 0 || len(h.deferred) != 0 }
func (h nodeHeap) Len() int { return len(h.heap) }
func (h nodeHeap) Less(i, j int) bool { return h.prio[h.heap[i]] < h.prio[h.heap[j]] }
func (h nodeHeap) Swap(i, j int) { h.heap[i], h.heap[j] = h.heap[j], h.heap[i] }
@@ -175,7 +192,7 @@
}
func (fb *fwdBuilder[L, Fact, NodeID]) propagate() {
- for fb.queue.Len() > 0 {
+ for fb.queue.pending() {
bi := fb.queue.dequeue()
block := &fb.blocks[bi]
diff --git a/internal/flow/forward_test.go b/internal/flow/forward_test.go
index e7c81cc..ebb75d6 100644
--- a/internal/flow/forward_test.go
+++ b/internal/flow/forward_test.go
@@ -160,6 +160,70 @@
)
}
+func TestFlowOrderLoop(t *testing.T) {
+ // Construct a loop with many latches:
+ //
+ // +-> arm 0 --+
+ // | |
+ // entry -> header -> ... -+-+
+ // ^ | | |
+ // | +-> arm N --+ |
+ // +---------------+
+ //
+ // Each arm contributes one bit to the fact propagated back to the header.
+ // An eager RPO priority queue processes the header immediately after each
+ // individual backedge update. This prevents updates from being coalesced
+ // and causes the loop body to be processed a quadratic number of times.
+ // A sweep-based RPO scheduler defers the header until the current sweep has
+ // finished and processes it only a small number of times.
+ const (
+ arms = 32
+ entry = 0
+ header = 1
+ firstArm = 2
+ )
+
+ edges := make([][]int, 2+arms)
+ edges[entry] = []int{header}
+ for i := range arms {
+ arm := firstArm + i
+ edges[header] = append(edges[header], arm)
+ edges[arm] = []int{header}
+ }
+ g := &simpleGraph{
+ numNodes: len(edges),
+ edges: edges,
+ }
+
+ transfers := 0
+ headerEdgeTransfers := 0
+ transfer := func(from, to int, in nodeSet) nodeSet {
+ transfers++
+ if from == header {
+ headerEdgeTransfers++
+ }
+ if from >= firstArm {
+ return in | set(from-firstArm)
+ }
+ return in
+ }
+
+ result := flow.Forward[nodeSetUnion](g, nil, transfer)
+ want := nodeSet((uint64(1) << arms) - 1)
+ if got := result.In(header); got != want {
+ t.Fatalf("header input: got %064b, want %064b", got, want)
+ }
+
+ // The header has one outgoing edge per arm, so this bounds the number of
+ // times its transfer function was evaluated to two complete sweeps.
+ if max := 2 * arms; headerEdgeTransfers > max {
+ t.Errorf("header edges transferred %d times, want at most %d", headerEdgeTransfers, max)
+ }
+ if max := 4*arms + 1; transfers > max {
+ t.Errorf("got %d total transfer calls, want at most %d", transfers, max)
+ }
+}
+
func TestFlowOrder(t *testing.T) {
// This test constructs a "Spine with Bottleneck" graph in which a naive
// visit order would result in quadratic time.
Change information
Files:
- M internal/flow/forward.go
- M internal/flow/forward_test.go
Change size: M
Delta: 2 files changed, 88 insertions(+), 7 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Dominik Honnef (Gerrit)
2:14 PM (8 hours ago) 2:14 PM
to Dominik Honnef, goph...@pubsubhelper.golang.org, Austin Clements, Alan Donovan, golang-co...@googlegroups.com
Attention needed from Austin Clements
Dominik Honnef voted Commit-Queue+1![]( "Open in Gerrit")
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages