analysis.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 midway
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/syntax"
    10  	"cmd/compile/internal/types2"
    11  )
    12  
    13  // Analyzer holds the state for SIMD dependency analysis
    14  type Analyzer struct {
    15  	pkg                *types2.Package
    16  	info               *types2.Info
    17  	isDependentObj     map[types2.Object]bool // does an Object depend on a simd type in some way?
    18  	isDependentMethod  map[types2.Object]bool // is this dependent Object also a method? (methods are not renamed, their types are)
    19  	hasDependentMethod map[types2.Type]bool   // is this a type that has a dependent method?
    20  	visited            map[types2.Type]bool   // if in map, type has been visited, and value is whether type is dependent
    21  	inSimd             bool                   // true if the current package is the simd package (which is a special case)
    22  }
    23  
    24  func NewAnalyzer(pkg *types2.Package, info *types2.Info) *Analyzer {
    25  	return &Analyzer{
    26  		pkg:                pkg,
    27  		info:               info,
    28  		isDependentObj:     make(map[types2.Object]bool),
    29  		isDependentMethod:  make(map[types2.Object]bool),
    30  		hasDependentMethod: make(map[types2.Type]bool),
    31  		visited:            make(map[types2.Type]bool),
    32  		inSimd:             pkg.Path() == simdPkg,
    33  	}
    34  }
    35  
    36  // Analyze builds the set of SIMD-dependent objects
    37  func (a *Analyzer) Analyze(files []*syntax.File) bool {
    38  	// Phase 1: Seed dependence from types and signatures
    39  	hdmsize := len(a.hasDependentMethod)
    40  
    41  	for {
    42  		for _, obj := range a.info.Defs {
    43  			if obj != nil {
    44  				a.markIfDependent(obj)
    45  			}
    46  		}
    47  		for _, obj := range a.info.Uses {
    48  			if obj != nil {
    49  				a.markIfDependent(obj)
    50  			}
    51  		}
    52  		if hdmsize == len(a.hasDependentMethod) {
    53  			break
    54  		}
    55  		if base.Debug.Simd > 0 {
    56  			base.Warn("hasDependentMethod increased from %d to %d", hdmsize, len(a.hasDependentMethod))
    57  		}
    58  		hdmsize = len(a.hasDependentMethod)
    59  		clear(a.visited)
    60  	}
    61  
    62  	// Phase 2: Transitive closure via function bodies
    63  	changed := true
    64  	for changed {
    65  		changed = false
    66  		for _, file := range files {
    67  			for _, decl := range file.DeclList {
    68  				if fn, ok := decl.(*syntax.FuncDecl); ok {
    69  					if fn.Name == nil {
    70  						continue
    71  					}
    72  					obj := a.info.Defs[fn.Name]
    73  					if obj == nil || a.isDependentObj[obj] {
    74  						continue
    75  					}
    76  
    77  					if a.hasBodyDependency(fn) {
    78  						a.isDependentObj[obj] = true
    79  						changed = true
    80  					}
    81  				}
    82  			}
    83  		}
    84  	}
    85  
    86  	return len(a.isDependentObj) > 0
    87  }
    88  
    89  func (a *Analyzer) hasBodyDependency(fn *syntax.FuncDecl) bool {
    90  	if fn.Body == nil {
    91  		return false
    92  	}
    93  	// Walk the body and check identifiers
    94  	// This will also note any variable references that are dependent.
    95  	found := false
    96  	syntax.Inspect(fn.Body, func(n syntax.Node) bool {
    97  		if id, ok := n.(*syntax.Name); ok {
    98  			obj := a.info.Uses[id]
    99  			if obj == nil {
   100  				obj = a.info.Defs[id]
   101  			}
   102  			if obj != nil {
   103  				if _, isFunc := obj.(*types2.Func); !isFunc {
   104  					if a.isDependentObj[obj] {
   105  						found = true
   106  						return false
   107  					}
   108  				} else {
   109  					sig := obj.Type().(*types2.Signature)
   110  					if a.HasDependentSignature(sig) {
   111  						found = true
   112  						return false
   113  					}
   114  				}
   115  				if a.isDependentType(obj.Type()) {
   116  					// Whatever this is, it makes the outer object dependent.
   117  					// If this is a package variable with dependent type, mark the
   118  					// variable as dependent, so that references to it become dependent.
   119  					if obj, ok := obj.(*types2.Var); ok && obj.Kind() == types2.PackageVar {
   120  						// everything else is nested within a dependent function/struct/scope
   121  						// and does not need its own renaming
   122  						a.isDependentObj[obj] = true
   123  					}
   124  					found = true
   125  					return false
   126  				}
   127  				if isBaseSimdTypeObj(obj) {
   128  					found = true
   129  					return false
   130  				}
   131  			}
   132  		}
   133  		return true
   134  	})
   135  	return found
   136  }
   137  
   138  func (a *Analyzer) markIfDependent(obj types2.Object) bool {
   139  	if a.isDependentObj[obj] {
   140  		return true
   141  	}
   142  
   143  	isDep := false
   144  	isDepMeth := false
   145  	switch obj := obj.(type) {
   146  	case *types2.Var:
   147  		if obj.Pkg() == a.pkg && obj.Parent() == a.pkg.Scope() {
   148  			isDep = a.isDependentType(obj.Type())
   149  		}
   150  	case *types2.TypeName:
   151  		isDep = a.isDependentType(obj.Type())
   152  	case *types2.Func:
   153  		sig := obj.Type().(*types2.Signature)
   154  		if a.HasDependentSignature(sig) {
   155  			// NOT dependent if it is a method of one of the base SIMD types.
   156  			// TODO: what about aliases of base SIMD types?
   157  			if rcv := sig.Recv(); rcv == nil {
   158  				isDep = true
   159  			} else if named, ok := rcv.Type().(*types2.Named); !ok || !isBaseSimdType(named) {
   160  				isDep = true
   161  				t := rcv.Type()
   162  				if !a.isDependentType(t) {
   163  					a.markHasMethod(t)
   164  				}
   165  				isDepMeth = true
   166  			}
   167  		}
   168  	}
   169  
   170  	// Also check if obj name is "simd.Type" (base case)
   171  	if isBaseSimdTypeObj(obj) {
   172  		isDep = true
   173  	}
   174  
   175  	if isDep {
   176  		if base.Debug.Simd > 0 {
   177  			base.Warn("%s: %v is simd-dependent", obj.Pos().String(), obj)
   178  		}
   179  		a.isDependentObj[obj] = true
   180  	}
   181  	if isDepMeth {
   182  		if base.Debug.Simd > 0 {
   183  			base.Warn("%s: %v is simd-dependent method", obj.Pos().String(), obj)
   184  		}
   185  		a.isDependentMethod[obj] = true
   186  	}
   187  	return isDep
   188  }
   189  
   190  func (a *Analyzer) isDependentType(t types2.Type) bool {
   191  	return a.checkTypeRecursive(t)
   192  }
   193  
   194  func (a *Analyzer) checkTypeRecursive(t types2.Type) bool {
   195  	if t == nil {
   196  		return false
   197  	}
   198  	if a.hasDependentMethod[t] {
   199  		a.visited[t] = true
   200  	}
   201  	if b, ok := a.visited[t]; ok {
   202  		return b // Break cycles
   203  	}
   204  	a.visited[t] = false
   205  
   206  	memo := func(b bool) bool {
   207  		a.visited[t] = b
   208  		return b
   209  	}
   210  
   211  	// Unwrap aliases
   212  	if named, ok := t.(*types2.Named); ok {
   213  		if isBaseSimdType(named) {
   214  			return memo(true)
   215  		}
   216  		if a.checkTypeRecursive(named.Underlying()) {
   217  			return memo(true)
   218  		}
   219  	}
   220  
   221  	switch t := t.(type) {
   222  	case *types2.Basic:
   223  		return false
   224  	case *types2.Pointer:
   225  		return memo(a.checkTypeRecursive(t.Elem()))
   226  	case *types2.Slice:
   227  		return memo(a.checkTypeRecursive(t.Elem()))
   228  	case *types2.Array:
   229  		return memo(a.checkTypeRecursive(t.Elem()))
   230  	case *types2.Map:
   231  		return memo(a.checkTypeRecursive(t.Key()) ||
   232  			a.checkTypeRecursive(t.Elem()))
   233  	case *types2.Chan:
   234  		return memo(a.checkTypeRecursive(t.Elem()))
   235  	case *types2.Struct:
   236  		for i := 0; i < t.NumFields(); i++ {
   237  			if a.checkTypeRecursive(t.Field(i).Type()) {
   238  				return memo(true)
   239  			}
   240  		}
   241  	case *types2.Signature:
   242  		return memo(a.HasDependentSignature(t))
   243  	case *types2.Tuple:
   244  		for i := 0; i < t.Len(); i++ {
   245  			if a.checkTypeRecursive(t.At(i).Type()) {
   246  				return memo(true)
   247  			}
   248  		}
   249  	case *types2.Alias:
   250  		return memo(a.checkTypeRecursive(types2.Unalias(t)))
   251  	}
   252  	return false
   253  }
   254  
   255  // This attempts to mark types that are not otherwise dependent
   256  // as being dependent, if they have a method with a dependent
   257  // signature.
   258  func (a *Analyzer) markHasMethod(t types2.Type) {
   259  	if t == nil {
   260  		return
   261  	}
   262  	if a.hasDependentMethod[t] {
   263  		return
   264  	}
   265  
   266  	a.hasDependentMethod[t] = true
   267  
   268  	switch t := t.(type) {
   269  	case *types2.Pointer:
   270  		a.markHasMethod(t.Elem())
   271  	case *types2.Alias:
   272  		a.markHasMethod(t.Rhs())
   273  	}
   274  	return
   275  }
   276  
   277  func isBaseSimdType(t *types2.Named) bool {
   278  	return isBaseSimdTypeObj(t.Obj())
   279  }
   280  
   281  func isBaseSimdTypeObj(obj types2.Object) bool {
   282  	if obj == nil || obj.Pkg() == nil {
   283  		return false
   284  	}
   285  	if obj.Pkg().Path() != simdPkg {
   286  		return false
   287  	}
   288  	return isSimdTypeName(obj.Name())
   289  }
   290  
   291  func (a *Analyzer) HasDependentSignature(sig *types2.Signature) bool {
   292  	// TODO what about type parameters?  Need to invent a test that provokes that case.
   293  	return a.isDependentType(sig.Params()) ||
   294  		a.isDependentType(sig.Results()) ||
   295  		(sig.Recv() != nil && a.isDependentType(sig.Recv().Type()))
   296  }
   297
View as plain text