dfplus_iter_test.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  	"fmt"
     9  	"iter"
    10  	"slices"
    11  	"testing"
    12  
    13  	"cmd/compile/internal/ssa/block"
    14  )
    15  
    16  // genCrossLadder builds a k-column, 2-rail cross ladder CFG:
    17  //
    18  //	entry → L1  R1
    19  //	        │╲ ╱│     every block branches to BOTH blocks of
    20  //	        │ ╳ │     the next column
    21  //	        │╱ ╲│
    22  //	        L2  R2
    23  //	         ...
    24  //	        Lk  Rk
    25  //	         ↘  ↙
    26  //	         exit
    27  //
    28  // The cross edges help to do quadratic DF+ walks (assume each of N blocks has another def
    29  // and needs to iterate with f.IterDomFrontierPlus O(N) blocks).
    30  // Returned are the function and its column blocks, column by column.
    31  func genCrossLadder(k int) (*Func, []*Block) {
    32  	f := (&Config{}).NewFunc(nil, &Cache{})
    33  	entry := f.NewBlock(block.BlockIf)
    34  	f.Entry = entry
    35  	exit := f.NewBlock(block.BlockExit)
    36  	col := make([]*Block, 0, 2*k)
    37  	prevL, prevR := entry, entry
    38  	for i := 0; i < k; i++ {
    39  		kind := block.BlockIf
    40  		if i == k-1 {
    41  			kind = block.BlockPlain // goto exit
    42  		}
    43  		l := f.NewBlock(kind)
    44  		r := f.NewBlock(kind)
    45  		col = append(col, l, r)
    46  		prevL.AddEdgeTo(l)
    47  		prevL.AddEdgeTo(r)
    48  		prevR.AddEdgeTo(l)
    49  		prevR.AddEdgeTo(r)
    50  		prevL, prevR = l, r
    51  	}
    52  	col[len(col)-2].AddEdgeTo(exit)
    53  	col[len(col)-1].AddEdgeTo(exit)
    54  	return f, col
    55  }
    56  
    57  // BenchmarkIterDomFrontierPlus walks the iterated dominance frontier of every
    58  // column block of a cross ladder, the merge-set stress shape.
    59  // Ideally, ns/block (ns/op ÷ blocks/op) stays flat as k grows.
    60  func BenchmarkIterDomFrontierPlus(b *testing.B) {
    61  	for _, k := range []int{8, 16, 32} {
    62  		b.Run(fmt.Sprintf("k=%d", k), func(b *testing.B) {
    63  			f, col := genCrossLadder(k)
    64  			b.ReportAllocs()
    65  			b.ResetTimer()
    66  			var n int
    67  			for i := 0; i < b.N; i++ {
    68  				for j := range col {
    69  					for range f.IterDomFrontierPlus(slices.Values(col[j : j+1])) {
    70  						n++
    71  					}
    72  				}
    73  			}
    74  			b.StopTimer()
    75  			b.ReportMetric(float64(n)/float64(b.N), "blocks/op")
    76  			if n != 2*k*k*b.N {
    77  				b.Fatalf("walked %d blocks per round, want %d", n/b.N, 2*k*k)
    78  			}
    79  		})
    80  	}
    81  }
    82  
    83  // TestIterDomFrontierPlusSeedAtMerge tests DF+ of a small CFG with a loop
    84  // where its header is both a seed and a merge point.
    85  // A def in an unreachable block (u → b3) must not join the merge set,
    86  // and the header (b2) must be in it.
    87  func TestIterDomFrontierPlusSeedAtMerge(t *testing.T) {
    88  	//
    89  	//	x := 0
    90  	// loop:
    91  	//	x = x + 1         // b2: def in the loop head
    92  	//	if c { continue } // b4 → b2, back edge 1
    93  	//	if d { break }    // b5 → b3
    94  	//	goto loop         // b5 → b2, back edge 2
    95  	//	return x          // b3
    96  	// unreachable: x = 9; // u → b3
    97  	//
    98  	f := (&Config{}).NewFunc(nil, &Cache{})
    99  	b1 := f.NewBlock(block.BlockPlain) // entry: x:=0
   100  	f.Entry = b1
   101  	b2 := f.NewBlock(block.BlockIf)    // loop head: x = x + 1; if c
   102  	b4 := f.NewBlock(block.BlockPlain) // { continue }
   103  	b5 := f.NewBlock(block.BlockIf)    // if d { break }; goto loop
   104  	b3 := f.NewBlock(block.BlockExit)
   105  	u := f.NewBlock(block.BlockPlain) // unreachable; goto b3
   106  
   107  	b1.AddEdgeTo(b2)
   108  	b2.AddEdgeTo(b4)
   109  	b2.AddEdgeTo(b5)
   110  	b4.AddEdgeTo(b2) // back edge 1
   111  	b5.AddEdgeTo(b3) // break
   112  	b5.AddEdgeTo(b2) // back edge 2
   113  	u.AddEdgeTo(b3)  // goto b3
   114  
   115  	got := collectBlockIDs(f.IterDomFrontierPlus(slices.Values([]*Block{b1, b2, u})))
   116  	if want := []ID{b2.ID}; !slices.Equal(got, want) {
   117  		t.Errorf("got DF+ = %v, want %v", got, want)
   118  	}
   119  }
   120  
   121  func collectBlockIDs(seq iter.Seq[*Block]) []ID {
   122  	var ids []ID
   123  	for b := range seq {
   124  		ids = append(ids, b.ID)
   125  	}
   126  	return ids
   127  }
   128
View as plain text