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