dfplus_iter.go

     1  // Copyright 2026 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  	"container/heap"
     9  	"iter"
    10  )
    11  
    12  // DF(x), the dominance frontier of x, holds every block y such that x
    13  // dominates a predecessor of y but does not strictly dominate y. Its
    14  // transitive closure DF+ (also called the merge set) is where a phi
    15  // may need to be placed for a variable defined in x. DF+ of a set of
    16  // blocks S, denoted IDF(S) (iterated dominance frontier), is the union
    17  // of the DF+ of the blocks in S.
    18  
    19  // IterDomFrontierPlus iterates the DF+ of seeds: every block at which
    20  // a phi may need to be placed if a variable were defined in the seed
    21  // blocks. Blocks are yielded at most once, in a deterministic order;
    22  // an early break stops the walk. Seed blocks themselves are not
    23  // yielded as such, but a seed that is also a merge point (e.g. a loop
    24  // header) is.
    25  // seeds iterator is consumed in full before the walk starts (the current
    26  // algorithm has to walk deeper roots first).
    27  // CFG must not change while iteration is in progress; inserting
    28  // values (like phis) is fine.
    29  func (f *Func) IterDomFrontierPlus(seeds iter.Seq[*Block]) iter.Seq[*Block] {
    30  	return func(yield func(*Block) bool) {
    31  		// Materialize the seeds into a pooled slice reused by walkDFPlus.
    32  		s := f.Cache.AllocBlockSlice(f.NumBlocks())[:0]
    33  		defer f.Cache.FreeBlockSlice(s[:cap(s)])
    34  		for b := range seeds {
    35  			s = append(s, b)
    36  		}
    37  		f.walkDFPlus(s, yield)
    38  	}
    39  }
    40  
    41  // Per-block state of a DF+ walk, packed into one flag byte per block.
    42  // None of the bits is cleared during the walk. Each of the following happens at
    43  // most once per block:
    44  // - enters the work queue,
    45  // - is banked as a root,
    46  // - is yielded.
    47  const (
    48  	// The block's subtree walk is done or pending on q.
    49  	flagQueued = 1 << iota
    50  	// The block has been added to the PiggyBank: a seed, or a block
    51  	// yielded earlier in this walk.
    52  	flagPiggyBanked
    53  	// The block has been yielded to the caller.
    54  	flagYielded
    55  )
    56  
    57  // walkDFPlus is the engine under IterDomFrontierPlus.
    58  // The walk is the Sreedhar & Gao DJ-graph algorithm, "A Linear Time
    59  // Algorithm for Placing Φ-Nodes". Work is proportional to the dominator
    60  // subtrees walked (skipping subtrees already covered, deeper roots)
    61  // plus the frontier found, and memory is O(f.NumBlocks()). The walk reads
    62  // the CFG's edges and uses the cached dominator tree.
    63  // The seeds slice is reused in place by the PiggyBank.
    64  func (f *Func) walkDFPlus(seeds []*Block, yield func(*Block) bool) {
    65  	sdom := f.Sdom()
    66  
    67  	// Roots to process, deepest first.
    68  	piggyBank := blockHeap{t: sdom, a: seeds[:0]}
    69  
    70  	// The worklist is a pooled slice, freed after the walk is done.
    71  	// Each block enters it at most once, so it never outgrows its capacity.
    72  	q := f.Cache.AllocBlockSlice(f.NumBlocks())[:0]
    73  	defer f.Cache.FreeBlockSlice(q[:cap(q)])
    74  
    75  	// per-block walk state; see the flag constants above.
    76  	flags := f.Cache.AllocInt8Slice(f.NumBlocks())
    77  	defer f.Cache.FreeInt8Slice(flags)
    78  
    79  	// Bank the seeds as roots, compacting in place to drop duplicates.
    80  	for _, b := range seeds {
    81  		if flags[b.ID]&flagPiggyBanked == 0 {
    82  			flags[b.ID] |= flagPiggyBanked
    83  			piggyBank.a = append(piggyBank.a, b)
    84  		}
    85  	}
    86  	heap.Init(&piggyBank)
    87  
    88  	// Visit the roots from deepest to shallowest.
    89  	for len(piggyBank.a) > 0 {
    90  		currentRoot := heap.Pop(&piggyBank).(*Block)
    91  		// Walk the subtree below the root, skipping subtrees already
    92  		// covered by previous (deeper) roots, and find the edges
    93  		// exiting it: their targets are the dominance frontier.
    94  		// Roots are popped deepest first, so any block a later root's walk could
    95  		// queue lies strictly below that root and was already queued
    96  		// by its own root-push.
    97  		if flags[currentRoot.ID]&flagQueued != 0 {
    98  			f.Fatalf("root already in queue")
    99  		}
   100  		flags[currentRoot.ID] |= flagQueued
   101  		q = append(q, currentRoot)
   102  		for len(q) > 0 {
   103  			b := q[len(q)-1]
   104  			q = q[:len(q)-1]
   105  
   106  			currentRootLevel := sdom.Level(currentRoot)
   107  			for _, e := range b.Succs {
   108  				c := e.Block()
   109  				if sdom.Level(c) > currentRootLevel {
   110  					// a D-edge, or an edge whose target is in currentRoot's subtree.
   111  					continue
   112  				}
   113  				if flags[c.ID]&flagYielded != 0 {
   114  					continue
   115  				}
   116  				flags[c.ID] |= flagYielded
   117  				if flags[c.ID]&flagPiggyBanked == 0 {
   118  					// Bank c as a root; its subtree may find further frontier edges.
   119  					// Invariant: piggyBanked = seeds ∪ yielded
   120  					flags[c.ID] |= flagPiggyBanked
   121  					heap.Push(&piggyBank, c)
   122  				}
   123  				if !yield(c) {
   124  					return
   125  				}
   126  			}
   127  
   128  			// Visit children if they have not been visited yet.
   129  			for ch := sdom.Child(b); ch != nil; ch = sdom.Sibling(ch) {
   130  				if flags[ch.ID]&flagQueued == 0 {
   131  					flags[ch.ID] |= flagQueued
   132  					q = append(q, ch)
   133  				}
   134  			}
   135  		}
   136  	}
   137  }
   138  
   139  // A block heap is used as a priority queue to implement the PiggyBank
   140  // from Sreedhar and Gao.  That paper uses an array which is better
   141  // asymptotically but worse in the common case when the PiggyBank
   142  // holds a sparse set of blocks.
   143  type blockHeap struct {
   144  	a []*Block   // blocks in heap
   145  	t SparseTree // dominator tree; provides block levels for priority
   146  }
   147  
   148  func (h *blockHeap) Len() int      { return len(h.a) }
   149  func (h *blockHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }
   150  
   151  func (h *blockHeap) Push(x any) {
   152  	v := x.(*Block)
   153  	h.a = append(h.a, v)
   154  }
   155  func (h *blockHeap) Pop() any {
   156  	old := h.a
   157  	n := len(old)
   158  	x := old[n-1]
   159  	h.a = old[:n-1]
   160  	return x
   161  }
   162  func (h *blockHeap) Less(i, j int) bool {
   163  	return h.t.Level(h.a[i]) > h.t.Level(h.a[j])
   164  }
   165
View as plain text