Source file src/cmd/compile/internal/ssacompile/decomposeaddr.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 ssacompile
     6  
     7  // This file contains the decomposeAddr pass.
     8  // decomposeAddr decomposes aggregate variables
     9  // (structs and arrays) into separate scalar variables. This allows the subsequent
    10  // mem2reg pass to promote these scalars to ssa values, improving
    11  // performance by reducing memory traffic. This is assuming the regalloc
    12  // can make good decisions under the increased pressure of more ssa values.
    13  //
    14  // This pass is also known as SROA (scalar replacement of aggregates) in other compilers.
    15  //
    16  // Overview:
    17  // 1. Candidate identification: find local variables that don't qualify for mem2reg and
    18  //    are not special. Special variables are NonMergeable or OpenDeferSlot.
    19  // 2. Partitioning: determine if the aggregate's fields are accessed in a way that
    20  //    permits decomposition (e.g., aligned with leaf field boundaries).
    21  // 3. Breakdown of block operations: replace OpZero and OpMove on aggregates with
    22  //    field-by-field scalar operations.
    23  // 4. Rewriting: create new individual local variables for each leaf field and
    24  //    rewrite all loads, stores, and VarDefs to use the new variables.
    25  //
    26  // Stability constraints:
    27  // - OpVarDef is only emitted for new scalars if they:
    28  //		- have pointers: the GC needs to know the live ranges of these variables.
    29  //		- are merge candidates: mergelocals need to know the live ranges of these variables.
    30  // - Aggregates that are too large are skipped to prevent compiler hangs or excessive
    31  //   memory usage.
    32  
    33  import (
    34  	"cmd/compile/internal/ir"
    35  	"cmd/compile/internal/ssa"
    36  	"cmd/compile/internal/ssa/ssaop"
    37  	"cmd/compile/internal/types"
    38  	"fmt"
    39  	"slices"
    40  )
    41  
    42  type leafField struct {
    43  	off int64
    44  	typ *types.Type
    45  }
    46  
    47  type decomposeCandidate struct {
    48  	n              *ir.Name
    49  	leaves         []leafField
    50  	leavesByOff    map[int64]leafField
    51  	localAddrs     []*ssa.Value // all the LocalAddrs of this candidate.
    52  	unDecomposable bool
    53  }
    54  
    55  var decomposeAddrDummyValue = &ssa.Value{}
    56  
    57  // zeroValueForType returns a zero-valued SSA constant for the given type.
    58  // Returns nil for unsupported types.
    59  //
    60  // f may be nil, in which case no constant is materialized: the function
    61  // returns the non-nil decomposeAddrDummyValue for supported types (and nil,
    62  // as usual, for unsupported ones). This mode is used during candidate
    63  // selection to ask "could we build a zero value for this type?" without
    64  // mutating the function; the dummy value itself must never be used as an
    65  // SSA value.
    66  func zeroValueForType(f *ssa.Func, t *types.Type) *ssa.Value {
    67  	switch {
    68  	case t.IsBoolean():
    69  		if f == nil {
    70  			return decomposeAddrDummyValue
    71  		}
    72  		return f.ConstBool(t, false)
    73  	case t.IsInteger():
    74  		if f == nil {
    75  			return decomposeAddrDummyValue
    76  		}
    77  		switch t.Size() {
    78  		case 1:
    79  			return f.ConstInt8(t, 0)
    80  		case 2:
    81  			return f.ConstInt16(t, 0)
    82  		case 4:
    83  			return f.ConstInt32(t, 0)
    84  		default:
    85  			return f.ConstInt64(t, 0)
    86  		}
    87  	case t.IsFloat():
    88  		if f == nil {
    89  			return decomposeAddrDummyValue
    90  		}
    91  		switch t.Size() {
    92  		case 4:
    93  			return f.ConstFloat32(t, 0)
    94  		default:
    95  			return f.ConstFloat64(t, 0)
    96  		}
    97  	case t.IsPtrShaped():
    98  		if f == nil {
    99  			return decomposeAddrDummyValue
   100  		}
   101  		return f.ConstNil(t)
   102  	case t.IsString():
   103  		if f == nil {
   104  			return decomposeAddrDummyValue
   105  		}
   106  		return f.ConstEmptyString(t)
   107  	case t.IsSlice():
   108  		if f == nil {
   109  			return decomposeAddrDummyValue
   110  		}
   111  		return f.ConstSlice(t)
   112  	case t.IsInterface():
   113  		if f == nil {
   114  			return decomposeAddrDummyValue
   115  		}
   116  		return f.ConstInterface(t)
   117  	case t.IsSIMD():
   118  		if f == nil {
   119  			return decomposeAddrDummyValue
   120  		}
   121  		return f.ConstSIMD(t)
   122  	default:
   123  		// Unsupported types.
   124  		// TODO: sometimes composite types like [1]uint64
   125  		// can also get passed down here, maybe make this function aware of them as well?
   126  		return nil
   127  	}
   128  }
   129  
   130  // decomposeAddr decomposes aggregate variables
   131  // (structs and arrays) accessed via OffPtr
   132  // into separate scalar variables, allowing mem2reg to promote them.
   133  func decomposeAddr(f *ssa.Func) {
   134  	// Get demographics up front: for a function with no candidate
   135  	// LocalAddr (the common case) this allocates nothing and the pass
   136  	// exits before setting up any of its machinery below.
   137  	demographics, localAddrs, uses := variableDemographics(f)
   138  	if uses == nil {
   139  		return
   140  	}
   141  	defer func() { uses.free(f) }()
   142  
   143  	st := f.NewStats("decomposeAddr")
   144  
   145  	// maxPartitions limits the number of fields an aggregate can be decomposed into.
   146  	// This prevents OOM and hangs on extremely large arrays or deeply nested structs.
   147  	// Tunable for experiments via -d=ssa/decompose_addr/@maxpartitions=<n>.
   148  	maxPartitions := f.Pass.Val("maxpartitions", 64)
   149  
   150  	// maxActivePartitions limits the number of *active* fields an aggregate
   151  	// can be decomposed into. While maxPartitions bounds how many leaf fields
   152  	// an aggregate may have at all (limiting the work this pass does per
   153  	// variable), maxActivePartitions bounds how many of those leaves are
   154  	// actually read (limiting the register pressure the promotion creates):
   155  	// a leaf is "active" if some Load reads it, and only active leaves become
   156  	// live SSA values after the follow-up mem2reg promotion. For example, for
   157  	//
   158  	//	var a [8]int
   159  	//	a[1] = x
   160  	//	a[2] = y
   161  	//	use(a[1])
   162  	//
   163  	// the aggregate has 8 leaves (all within maxPartitions), but only a[1] is
   164  	// active. Leaves that are only stored to die immediately after promotion,
   165  	// so they add no register pressure.
   166  	// This is a parameter that controls the trade-off of less memory accesses
   167  	// and higher register pressure for mem2reg.
   168  	// If we set this number too high, the register allocation might behave suboptimally
   169  	// and the performance might even regress.
   170  	// Tunable for experiments via -d=ssa/decompose_addr/@maxactivepartitions=<n>.
   171  	maxActivePartitions := f.Pass.Val("maxactivepartitions", 4)
   172  
   173  	type partitionStatus int
   174  	const (
   175  		partSuccess partitionStatus = iota
   176  		partTooMany                 // too many partitions, above maxPartitions limit
   177  		partLarge                   // leaf field too large to be stored in one register
   178  	)
   179  
   180  	// getLeafFields recursively finds all scalar fields of a type with their given offsets.
   181  	var getLeafFields func(t *types.Type, base int64) (leaves []leafField, status partitionStatus)
   182  	getLeafFields = func(t *types.Type, base int64) (leaves []leafField, status partitionStatus) {
   183  		// checkField updates leaves by looking into a composite type field (or element) of
   184  		// type t2 at offset. It returns the status code.
   185  		checkField := func(t2 *types.Type, offset int64) partitionStatus {
   186  			ls, s := getLeafFields(t2, offset)
   187  			if s != partSuccess {
   188  				return s
   189  			}
   190  			if int64(len(leaves)+len(ls)) > maxPartitions {
   191  				return partTooMany
   192  			}
   193  			leaves = append(leaves, ls...)
   194  			return partSuccess
   195  		}
   196  		if t.IsStruct() && !t.IsSIMD() {
   197  			for i := range t.NumFields() {
   198  				fld := t.Field(i)
   199  				if s := checkField(fld.Type, base+fld.Offset); s != partSuccess {
   200  					return nil, s
   201  				}
   202  			}
   203  		} else if t.IsArray() {
   204  			// Limit decomposition of large arrays.
   205  			if t.NumElem() > maxPartitions {
   206  				return nil, partTooMany
   207  			}
   208  			for i := range t.NumElem() {
   209  				if s := checkField(t.Elem(), base+int64(i)*t.Elem().Size()); s != partSuccess {
   210  					return nil, s
   211  				}
   212  			}
   213  		} else if t.IsString() {
   214  			// Strings split into a pointer and a length word, mirroring
   215  			// (*Func).SplitString. By the time this pass runs, decompose
   216  			// builtin has already rewritten string-typed accesses into
   217  			// word-level ones, so accesses line up with these leaves.
   218  			ptrType := f.Config.Types.BytePtr
   219  			lenType := types.Types[types.TINT]
   220  			if s := checkField(ptrType, base); s != partSuccess {
   221  				return nil, s
   222  			}
   223  			if s := checkField(lenType, base+ptrType.Size()); s != partSuccess {
   224  				return nil, s
   225  			}
   226  		} else if t.IsSlice() {
   227  			// Mirrors (*Func).SplitSlice.
   228  			ptrType := types.NewPtr(t.Elem())
   229  			lenType := types.Types[types.TINT]
   230  			if s := checkField(ptrType, base); s != partSuccess {
   231  				return nil, s
   232  			}
   233  			if s := checkField(lenType, base+ptrType.Size()); s != partSuccess {
   234  				return nil, s
   235  			}
   236  			if s := checkField(lenType, base+ptrType.Size()+lenType.Size()); s != partSuccess {
   237  				return nil, s
   238  			}
   239  		} else if t.IsInterface() {
   240  			// Mirrors (*Func).SplitInterface: the itab/type word is a
   241  			// uintptr (see the comment in typebits.Set), the data word is
   242  			// a scannable pointer.
   243  			itabType := types.Types[types.TUINTPTR]
   244  			dataType := f.Config.Types.BytePtr
   245  			if s := checkField(itabType, base); s != partSuccess {
   246  				return nil, s
   247  			}
   248  			if s := checkField(dataType, base+itabType.Size()); s != partSuccess {
   249  				return nil, s
   250  			}
   251  		} else if t.IsComplex() {
   252  			// Mirrors (*Func).SplitComplex.
   253  			elemType := types.Types[types.TFLOAT32]
   254  			if t.Size() == 16 {
   255  				elemType = types.Types[types.TFLOAT64]
   256  			}
   257  			if s := checkField(elemType, base); s != partSuccess {
   258  				return nil, s
   259  			}
   260  			if s := checkField(elemType, base+elemType.Size()); s != partSuccess {
   261  				return nil, s
   262  			}
   263  		} else {
   264  			// Leaf field
   265  			if !t.IsSIMD() && t.Size() > f.Config.RegSize {
   266  				// This leaf field is too large to be stored in one register.
   267  				// This can still trigger for e.g. 8-byte scalars on 32-bit
   268  				// platforms; wide builtin composites (strings, slices,
   269  				// interfaces, complexes) are split into words above.
   270  				return nil, partLarge
   271  			}
   272  			if t.Size() == 0 {
   273  				// The only zero-sized types are (arrays of) empty structs
   274  				// and zero-length arrays, which are both handled by the
   275  				// composite cases above, so a zero-sized leaf is impossible.
   276  				f.Fatalf("zero-sized leaf field of type %v in decomposeAddr", t)
   277  			}
   278  			return []leafField{{base, t}}, partSuccess
   279  		}
   280  		return leaves, partSuccess
   281  	}
   282  
   283  	// 1. Collect initial candidates.
   284  	candidates := make(map[*ir.Name]*decomposeCandidate)
   285  	// Different ir.Name can have the same name string.
   286  	// We need to give them different split names to distinguish them.
   287  	stringToNames := make(map[string][]*ir.Name)
   288  	localAddrsByName := make(map[*ir.Name][]*ssa.Value)
   289  	seenNames := make(map[*ir.Name]bool)
   290  	for _, v := range localAddrs {
   291  		n := v.Aux.(*ir.Name)
   292  		if !seenNames[n] {
   293  			stringToNames[n.Sym().Name] = append(stringToNames[n.Sym().Name], n)
   294  			seenNames[n] = true
   295  		}
   296  		localAddrsByName[n] = append(localAddrsByName[n], v)
   297  	}
   298  
   299  	namesOrdered := []*ir.Name{}
   300  	for n, las := range localAddrsByName {
   301  		namesOrdered = append(namesOrdered, n)
   302  		slices.SortFunc(las, func(a, b *ssa.Value) int { return int(a.ID - b.ID) })
   303  	}
   304  	slices.SortFunc(namesOrdered, func(a, b *ir.Name) int {
   305  		return int(localAddrsByName[a][0].ID - localAddrsByName[b][0].ID)
   306  	})
   307  NameLoop:
   308  	for _, n := range namesOrdered {
   309  		if dg, ok := demographics[n]; !ok || !dg.lszmco {
   310  			st.Record("non qualifying variable", 1)
   311  			continue
   312  		}
   313  		// Skip special variables
   314  		if n.Class != ir.PAUTO {
   315  			st.Record("params", 1)
   316  			continue
   317  		}
   318  		t := n.Type()
   319  		splittable := (t.IsStruct() && !t.IsSIMD()) || t.IsArray() ||
   320  			t.IsString() || t.IsSlice() || t.IsInterface() || t.IsComplex()
   321  		if !splittable {
   322  			// Bare multi-word builtin composites (strings, slices,
   323  			// interfaces, complexes) split into word leaves just like
   324  			// aggregate fields of those types do; everything else that
   325  			// is not a struct or array stays with mem2reg alone.
   326  			st.Record("non composite", 1)
   327  			continue
   328  		}
   329  		if n.NonMergeable() || n.OpenDeferSlot() {
   330  			// Non mergeable variables and open defer slot are special,
   331  			// the compiler and the runtime expects them to be in the memory.
   332  			// Keep them in memory.
   333  			st.Record("non mergeable or open defer slot", 1)
   334  			continue
   335  		}
   336  		leaves, status := getLeafFields(n.Type(), 0)
   337  		if status != partSuccess {
   338  			switch status {
   339  			case partTooMany:
   340  				st.Record("too many partitions", 1)
   341  			case partLarge:
   342  				st.Record("large leaf field", 1)
   343  			default:
   344  				f.Fatalf("unknown leaf status in decomposeAddr")
   345  			}
   346  			continue
   347  		}
   348  		if len(leaves) == 0 {
   349  			st.Record("no partition", 1)
   350  			continue
   351  		}
   352  		leavesByOff := make(map[int64]leafField, len(leaves))
   353  		for _, lf := range leaves {
   354  			if _, ok := leavesByOff[lf.off]; ok {
   355  				// Go does not have union types, is this possible?
   356  				// Should we fatal out here instead?
   357  				st.Record("duplicate leaf field offset", 1)
   358  				continue NameLoop
   359  			}
   360  			leavesByOff[lf.off] = lf
   361  		}
   362  
   363  		ok := true
   364  		for _, lf := range leaves {
   365  			if zeroValueForType(nil, lf.typ) == nil {
   366  				ok = false
   367  				break
   368  			}
   369  		}
   370  		if !ok {
   371  			continue
   372  		}
   373  
   374  		candidates[n] = &decomposeCandidate{n: n, leaves: leaves, localAddrs: localAddrsByName[n], leavesByOff: leavesByOff}
   375  	}
   376  
   377  	if len(candidates) == 0 {
   378  		return
   379  	}
   380  
   381  	// Find entry memory and SP.
   382  	var entryMem, entrySP *ssa.Value
   383  	for _, v := range f.Entry.Values {
   384  		if v.Op == ssaop.OpSP {
   385  			entrySP = v
   386  		}
   387  		if v.Op == ssaop.OpInitMem {
   388  			entryMem = v
   389  		}
   390  		if entryMem != nil && entrySP != nil {
   391  			break
   392  		}
   393  	}
   394  	if entryMem == nil || entrySP == nil {
   395  		// A function only reaches this point with a candidate variable, whose loads,
   396  		// stores and LocalAddrs all take a memory operand, and every memory chain
   397  		// roots at InitMem through the entry block.
   398  		f.Fatalf("entry mem or sp is not found but there are local variables")
   399  	}
   400  
   401  	// isDerivedFrom checks if v is an address that's some offset from n.
   402  	isDerivedFrom := func(v *ssa.Value, n *ir.Name) bool {
   403  		for {
   404  			if v.Op == ssaop.OpLocalAddr && v.Aux == n {
   405  				return true
   406  			}
   407  			if v.Op != ssaop.OpOffPtr && v.Op != ssaop.OpCopy {
   408  				return false
   409  			}
   410  			v = v.Args[0]
   411  		}
   412  	}
   413  
   414  	// localAddrBase returns the LocalAddr that v is derived from through
   415  	// OffPtrs and Copies, or nil if v is not derived from one.
   416  	localAddrBase := func(v *ssa.Value) *ssa.Value {
   417  		for {
   418  			switch v.Op {
   419  			case ssaop.OpLocalAddr:
   420  				return v
   421  			case ssaop.OpOffPtr, ssaop.OpCopy:
   422  				v = v.Args[0]
   423  			default:
   424  				return nil
   425  			}
   426  		}
   427  	}
   428  
   429  	// findOffset returns the offset of v from its LocalAddr base.
   430  	findOffset := func(ptr *ssa.Value) int64 {
   431  		var offset int64
   432  		for {
   433  			switch ptr.Op {
   434  			case ssaop.OpLocalAddr:
   435  				return offset
   436  			case ssaop.OpOffPtr:
   437  				offset += ptr.AuxInt
   438  				ptr = ptr.Args[0]
   439  			case ssaop.OpCopy:
   440  				ptr = ptr.Args[0]
   441  			default:
   442  				// Should not happen.
   443  				f.Fatalf("not derived from local address: %v", ptr)
   444  				return -1
   445  			}
   446  		}
   447  	}
   448  
   449  	matchToLeaf := func(c *decomposeCandidate, v *ssa.Value, offset int64) (leafField, bool) {
   450  		var sz int64
   451  		if v.Op == ssaop.OpLoad {
   452  			sz = v.Type.Size()
   453  		} else if v.Op == ssaop.OpStore {
   454  			sz = ssa.AuxToType(v.Aux).Size()
   455  		} else {
   456  			return leafField{}, false
   457  		}
   458  		if lf, ok := c.leavesByOff[offset]; ok {
   459  			// Access must exactly match a leaf field's offset and size.
   460  			if lf.typ.Size() == sz {
   461  				// found a match
   462  				return lf, true
   463  			}
   464  		}
   465  		return leafField{}, false
   466  	}
   467  
   468  	// movedLeaves returns the leaves of c fully covered by the byte range
   469  	// [off, off+size), with offsets relative to off, in increasing offset
   470  	// order. ok is false if the range partially covers some leaf of c.
   471  	movedLeaves := func(c *decomposeCandidate, off, size int64) (leaves []leafField, ok bool) {
   472  		end := off + size
   473  		for _, lf := range c.leaves {
   474  			lend := lf.off + lf.typ.Size()
   475  			if lf.off >= end || lend <= off {
   476  				continue // not touched
   477  			}
   478  			if lf.off < off || lend > end {
   479  				return nil, false // partially covered
   480  			}
   481  			leaves = append(leaves, leafField{lf.off - off, lf.typ})
   482  		}
   483  		return leaves, true
   484  	}
   485  
   486  	// 2. Check partition access alignment, and
   487  	// 3. Breakdown OpZero and OpMove if check pass.
   488  	// We convert aggregate-level zeros and moves into field-level stores and loads/stores.
   489  	// This exposes the underlying scalar access patterns to the promotion logic.
   490  	// We need to keep track of them to not process them twice, i.e. a Move could be traversed
   491  	// twice from source and destination.
   492  	brokenDown := make(map[*ssa.Value]bool)
   493  	// Note: the values created while breaking down a Zero/Move are not added
   494  	// to the uses map, so when a later candidate reaches the same (already
   495  	// brokenDown) Zero/Move it does not see the replacement scalar accesses
   496  	// either. That is fine for correctness: the replacements are constructed
   497  	// leaf-aligned for both operands, and the recomputation of the uses map
   498  	// after this loop lets the final promotion pick them up.
   499  	// usedLeaf records the leaves that scalar Loads read, it's use to abort decomposition when it's
   500  	// larger than maxActivePartitions.
   501  	changed := false
   502  	var mutations []func()
   503  NamesLoop:
   504  	for _, n := range namesOrdered {
   505  		usedLeaf := make(map[int64]struct{})
   506  		c, ok := candidates[n]
   507  		if !ok || c.unDecomposable {
   508  			// Already ruled out (possibly by an earlier candidate that
   509  			// shares a Move with n): nothing to break down for it, and
   510  			// it must not rule out further partners on its own account.
   511  			continue
   512  		}
   513  		mutations = mutations[:0]
   514  		// Partners of n's Moves whose leaves would be straddled by n's
   515  		// breakdown. They are ruled out together with the mutations, so
   516  		// that if n gives up later in this iteration its partners are
   517  		// left alone; one of them may then break the Move down by its
   518  		// own leaves instead.
   519  		var partnerDisq []*decomposeCandidate
   520  		// This is to keep track of the values that are ready to be processed in a
   521  		// batched way, it will be commited to brokenDown entirely or not at all.
   522  		localBrokenDown := make(map[*ssa.Value]bool)
   523  		derived := []*ssa.Value{} // all the addresses that are derived from the current name.
   524  		var collectDerived func(v *ssa.Value)
   525  		collectDerived = func(v *ssa.Value) {
   526  			derived = append(derived, v)
   527  			for _, use := range uses.of(v) {
   528  				// OffPtr and Copy can both be used to derive a new address
   529  				// from a name. The uses table predates this loop, so a
   530  				// Zero or Move that an earlier candidate already broke down
   531  				// still shows up here, reset to a Copy of memory; only a
   532  				// pointer-shaped Copy is an address.
   533  				if use.Op == ssaop.OpOffPtr || (use.Op == ssaop.OpCopy && use.Type.IsPtrShaped()) {
   534  					collectDerived(use)
   535  				}
   536  			}
   537  		}
   538  		for _, vAddr := range c.localAddrs {
   539  			collectDerived(vAddr)
   540  		}
   541  		slices.SortFunc(derived, func(a, b *ssa.Value) int { return int(a.ID - b.ID) })
   542  
   543  		for _, d := range derived {
   544  			for _, use := range uses.of(d) {
   545  				if brokenDown[use] || localBrokenDown[use] {
   546  					continue
   547  				}
   548  				switch use.Op {
   549  				case ssaop.OpOffPtr, ssaop.OpCopy:
   550  					// Handled by derived.
   551  				case ssaop.OpLoad, ssaop.OpStore:
   552  					leaf, ok := matchToLeaf(c, use, findOffset(use.Args[0]))
   553  					if !ok {
   554  						// we can't find a leaf node that matches
   555  						if f.Pass.Debug > 1 {
   556  							f.Warnl(n.Pos(), "decomposeAddr: %v has a load or store not on leaf level", n)
   557  						}
   558  						st.Record("load or store not on leaf level", 1)
   559  						c.unDecomposable = true
   560  						continue NamesLoop
   561  					}
   562  					if use.Op == ssaop.OpLoad {
   563  						// Only a scalar Load marks a leaf active.
   564  						if _, ok := usedLeaf[leaf.off]; !ok {
   565  							usedLeaf[leaf.off] = struct{}{}
   566  							if int64(len(usedLeaf)) > maxActivePartitions {
   567  								st.Record("too many active partitions", 1)
   568  								c.unDecomposable = true
   569  								continue NamesLoop
   570  							}
   571  						}
   572  					}
   573  				case ssaop.OpZero:
   574  					off := findOffset(use.Args[0])
   575  					size := use.AuxInt
   576  					end := off + size
   577  
   578  					if off < 0 || end > n.Type().Size() {
   579  						st.Record("zero range out of bounds", 1)
   580  						c.unDecomposable = true
   581  						continue NamesLoop
   582  					}
   583  
   584  					// Check if all fields within the zero are fully covered.
   585  					// Partial zeros (where a leaf field is only partly zeroed)
   586  					// are not currently supported.
   587  					for _, lf := range c.leaves {
   588  						lend := lf.off + lf.typ.Size()
   589  						if lf.off < end && lend > off { // touches
   590  							if lf.off < off || lend > end {
   591  								st.Record("partially zeroed", 1)
   592  								c.unDecomposable = true
   593  								continue NamesLoop
   594  							}
   595  						}
   596  					}
   597  
   598  					memIn := use.MemoryArg()
   599  					curM := memIn
   600  					for _, lf := range c.leaves {
   601  						if lf.off >= off && lf.off+lf.typ.Size() <= end {
   602  							mutations = append(mutations, func() {
   603  								newPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), lf.off-off, use.Args[0])
   604  								curM = use.Block.NewValue3A(use.Pos, ssaop.OpStore, types.TypeMem, lf.typ, newPtr, zeroValueForType(f, lf.typ), curM)
   605  							})
   606  						}
   607  					}
   608  					mutations = append(mutations, func() {
   609  						use.Reset(ssaop.OpCopy)
   610  						use.Aux = nil
   611  						use.SetArgs1(curM)
   612  					})
   613  					localBrokenDown[use] = true
   614  				case ssaop.OpMove:
   615  					isDst := isDerivedFrom(use.Args[0], n)
   616  					isSrc := isDerivedFrom(use.Args[1], n)
   617  					if !isDst && !isSrc {
   618  						f.Fatalf("non of move's operands is derived from local address: %v", use)
   619  					}
   620  					// If the Move's other operand is derived from a candidate (either another
   621  					// candidate, or n itself in a self-move), breaking this Move down by
   622  					// n's leaves creates accesses on that operand at n-shaped offsets.
   623  					// That is fine when the covered leaf shapes agree (the common same-type copy),
   624  					// but via an unsafe.Pointer cast the two sides can be shaped differently,
   625  					// and the emitted accesses would straddle the partner's or n's own leaves.
   626  					nSide := use.Args[0]
   627  					oSide := use.Args[1]
   628  					if !isDst {
   629  						nSide = use.Args[1]
   630  						oSide = use.Args[0]
   631  					}
   632  					if base := localAddrBase(oSide); base != nil {
   633  						on := base.Aux.(*ir.Name)
   634  						if oc, ok := candidates[on]; ok && !oc.unDecomposable {
   635  							// The breakdown is only correct for both sides if the
   636  							// Move covers exactly the same set of leaves (same
   637  							// relative offsets and sizes) on both of them, and
   638  							// straddles no leaf on either side. Otherwise, e.g. if
   639  							// one side has padding where the other has a leaf, a
   640  							// breakdown by one side's leaves skips some leaves of
   641  							// the other side.
   642  							nLeaves, nOk := movedLeaves(c, findOffset(nSide), use.AuxInt)
   643  							oLeaves, oOk := movedLeaves(oc, findOffset(oSide), use.AuxInt)
   644  							compatible := nOk && oOk && len(nLeaves) == len(oLeaves)
   645  							for i := 0; compatible && i < len(nLeaves); i++ {
   646  								if nLeaves[i].off != oLeaves[i].off || nLeaves[i].typ.Size() != oLeaves[i].typ.Size() {
   647  									compatible = false
   648  								}
   649  							}
   650  							if !compatible {
   651  								if oc == c {
   652  									st.Record("self move with straddled leaves", 1)
   653  									c.unDecomposable = true
   654  									continue NamesLoop
   655  								}
   656  								partnerDisq = append(partnerDisq, oc)
   657  							}
   658  						}
   659  					}
   660  
   661  					moved := []int64{}
   662  					if isDst {
   663  						moved = append(moved, findOffset(use.Args[0]))
   664  					}
   665  					if isSrc {
   666  						moved = append(moved, findOffset(use.Args[1]))
   667  					}
   668  					if len(moved) == 2 {
   669  						// Overlapping moves are still possible at this point,
   670  						// if below the threshold specified in IsInlinableMemmove.
   671  						// Bailout them here too.
   672  						if moved[1] < moved[0]+use.AuxInt && moved[0] < moved[1]+use.AuxInt {
   673  							st.Record("overlapping move", 1)
   674  							c.unDecomposable = true
   675  							continue NamesLoop
   676  						}
   677  					}
   678  					size := use.AuxInt
   679  
   680  					// Check bounds and partial moves for all operands derived from n.
   681  					for _, m := range moved {
   682  						end := m + size
   683  						if m < 0 || end > n.Type().Size() {
   684  							st.Record("move range out of bounds", 1)
   685  							c.unDecomposable = true
   686  							continue NamesLoop
   687  						}
   688  						for _, lf := range c.leaves {
   689  							lend := lf.off + lf.typ.Size()
   690  							if lf.off < end && lend > m { // touches
   691  								if lf.off < m || lend > end {
   692  									st.Record("partially moved", 1)
   693  									c.unDecomposable = true
   694  									continue NamesLoop
   695  								}
   696  							}
   697  						}
   698  					}
   699  					// The breakdown below emits a Load of every leaf the
   700  					// Move covers, but each of those Loads is consumed at
   701  					// once by the paired Store into the destination: after
   702  					// promotion the value is a register briefly on its
   703  					// way to memory, not a live leaf. So a Move does not
   704  					// mark leaves active; only scalar Loads do (see the
   705  					// OpLoad case). Counting them would rule out every
   706  					// whole-aggregate copy of a variable with more leaves
   707  					// than maxActivePartitions, which is most of the
   708  					// candidates in practice.
   709  
   710  					memIn := use.MemoryArg()
   711  					curM := memIn
   712  					for _, lf := range c.leaves {
   713  						// Take the leader offset from the moved slice.
   714  						offInMove := lf.off - moved[0]
   715  						if offInMove >= 0 && offInMove+lf.typ.Size() <= size {
   716  							mutations = append(mutations, func() {
   717  								// Emit scalar load/store for each field.
   718  								newSrcPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), offInMove, use.Args[1])
   719  								newDstPtr := use.Block.NewValue1I(use.Pos, ssaop.OpOffPtr, lf.typ.PtrTo(), offInMove, use.Args[0])
   720  								val := use.Block.NewValue2(use.Pos, ssaop.OpLoad, lf.typ, newSrcPtr, memIn)
   721  								curM = use.Block.NewValue3A(use.Pos, ssaop.OpStore, types.TypeMem, lf.typ, newDstPtr, val, curM)
   722  							})
   723  						}
   724  					}
   725  					mutations = append(mutations, func() {
   726  						use.Reset(ssaop.OpCopy)
   727  						use.Aux = nil
   728  						use.SetArgs1(curM)
   729  					})
   730  					localBrokenDown[use] = true
   731  				}
   732  			}
   733  		}
   734  		for _, m := range mutations {
   735  			m()
   736  		}
   737  		for _, oc := range partnerDisq {
   738  			if oc.unDecomposable {
   739  				continue
   740  			}
   741  			if f.Pass.Debug > 1 {
   742  				f.Warnl(oc.n.Pos(), "decomposeAddr: %v has leaves straddled by a move of %v; disqualified", oc.n, n)
   743  			}
   744  			st.Record("move partner with straddled leaves", 1)
   745  			oc.unDecomposable = true
   746  		}
   747  		for u := range localBrokenDown {
   748  			brokenDown[u] = true
   749  		}
   750  		if len(mutations) > 0 {
   751  			changed = true
   752  		}
   753  	}
   754  
   755  	if changed {
   756  		// The Zero/Move breakdown above introduced new values (OffPtrs off
   757  		// the candidates' LocalAddrs, and scalar Loads/Stores through them)
   758  		// that are not in the demographics/uses computed at the top of this
   759  		// pass. Recompute them so that the final promotion below sees, and
   760  		// rewrites, those new accesses too.
   761  		uses.free(f)
   762  		demographics, localAddrs, uses = variableDemographics(f)
   763  		if uses == nil {
   764  			// Cannot happen (the candidates' LocalAddrs still exist), but
   765  			// keep the invariant that a nil table means nothing to do.
   766  			return
   767  		}
   768  	}
   769  
   770  	// 4. Final Promotion.
   771  	// For each valid candidate, create new individual variables for each field
   772  	// and update all usages.
   773  	for _, n := range namesOrdered {
   774  		c, ok := candidates[n]
   775  		if !ok || c.unDecomposable {
   776  			continue
   777  		}
   778  		if dg, ok := demographics[n]; !ok || !dg.lszmco {
   779  			// The transformation should not have caused the variable
   780  			// unknown uses.
   781  			f.Fatalf("zero and move breakdown disqualify %v from decomposeAddr", n)
   782  		}
   783  
   784  		type pAccess struct {
   785  			a   *ssa.Value
   786  			off int64
   787  		}
   788  		var accesses []pAccess
   789  		var collectSimpleUses func(v *ssa.Value, offset int64)
   790  		collectSimpleUses = func(v *ssa.Value, offset int64) {
   791  			for _, use := range uses.of(v) {
   792  				switch use.Op {
   793  				case ssaop.OpOffPtr:
   794  					collectSimpleUses(use, offset+use.AuxInt)
   795  				case ssaop.OpLoad, ssaop.OpStore:
   796  					accesses = append(accesses, pAccess{use, offset})
   797  				case ssaop.OpCopy:
   798  					collectSimpleUses(use, offset)
   799  				default:
   800  					f.Fatalf("unhandled uses: %s", use.Op.String())
   801  				}
   802  			}
   803  		}
   804  		for _, vAddr := range c.localAddrs {
   805  			collectSimpleUses(vAddr, 0)
   806  		}
   807  		if len(accesses) == 0 {
   808  			st.Record("no accesses", 1)
   809  			continue
   810  		}
   811  
   812  		type partition struct {
   813  			offset  int64
   814  			typ     *types.Type
   815  			newAddr *ssa.Value
   816  			newName *ir.Name
   817  		}
   818  		partitions := make(map[int64]*partition)
   819  		partitionsValid := true
   820  		for _, a := range accesses {
   821  			if lf, ok := matchToLeaf(c, a.a, a.off); ok {
   822  				partitions[a.off] = &partition{offset: a.off, typ: lf.typ}
   823  				continue
   824  			}
   825  			// If we didn't find a matching leaf field, we cannot promote this variable.
   826  			partitionsValid = false
   827  			break
   828  		}
   829  		if !partitionsValid || len(partitions) == 0 {
   830  			f.Fatalf("not all accesses are on leaf level")
   831  		}
   832  
   833  		if f.Pass.Debug > 0 {
   834  			f.Warnl(n.Pos(), "promoted %v", n)
   835  		}
   836  		st.Record("promoted variable", 1)
   837  
   838  		// Deterministically create new variables for each used partition.
   839  		var partOffsets []int64
   840  		for off := range partitions {
   841  			partOffsets = append(partOffsets, off)
   842  		}
   843  		slices.Sort(partOffsets)
   844  
   845  		// Different variables can have the same names, we need to distinguish them
   846  		// if that's the case.
   847  		nameIdx := -1
   848  		ns := stringToNames[n.Sym().Name]
   849  		if len(ns) > 1 {
   850  			for i, nn := range ns {
   851  				if nn == n {
   852  					nameIdx = i
   853  					break
   854  				}
   855  			}
   856  		}
   857  
   858  		for _, off := range partOffsets {
   859  			p := partitions[off]
   860  			// TODO: Ideally the names should be the name you would use in Go for that part,
   861  			// to the extent that we can do that. Like myVariable.window.menu[3].text, or something.
   862  			// Just using offsets to distinguish is fine for now.
   863  			var newSymName string
   864  			if nameIdx >= 0 {
   865  				newSymName = fmt.Sprintf("%s#%d.part.%d", n.Sym().Name, nameIdx, p.offset)
   866  			} else {
   867  				newSymName = fmt.Sprintf("%s.part.%d", n.Sym().Name, p.offset)
   868  			}
   869  			newSym := &types.Sym{Name: newSymName, Pkg: n.Sym().Pkg}
   870  			// TODO: should we use the existing stack slot for the old variable instead?
   871  			// That might be more work.
   872  			newName := n.Curfn.NewLocal(n.Pos(), newSym, p.typ)
   873  			newName.SetUsed(true)
   874  			// Parts of a compiler-generated temporary are temporaries too.
   875  			newName.SetAutoTemp(n.AutoTemp())
   876  			p.newName = newName
   877  			// New LocalAddr at the entry block for the new scalar variable.
   878  			p.newAddr = f.Entry.NewValue2A(n.Pos(), ssaop.OpLocalAddr, types.NewPtr(p.typ), newName, entrySP, entryMem)
   879  		}
   880  
   881  		// Rewrite loads and stores to use the new scalar addresses.
   882  		for _, a := range accesses {
   883  			p := partitions[a.off]
   884  			a.a.SetArg(0, p.newAddr)
   885  		}
   886  
   887  		// Rewrite VarDef annotations to def the new names.
   888  		// Note: We only emit VarDef if the new variable contains pointers
   889  		// or is large enough to be a merge candidate, satisfying SSA checker.
   890  		dg, ok := demographics[n]
   891  		if !ok {
   892  			f.Fatalf("decomposeAddr candidate variable unseen: %v", dg)
   893  		}
   894  		for _, v := range dg.varDefs {
   895  			curM := v.MemoryArg()
   896  			for _, off := range partOffsets {
   897  				p := partitions[off]
   898  				if p.newName.Type().HasPointers() || ssa.IsMergeCandidate(p.newName) {
   899  					curM = v.Block.NewValue1A(v.Pos, ssaop.OpVarDef, types.TypeMem, p.newName, curM)
   900  				}
   901  			}
   902  			v.Reset(ssaop.OpCopy)
   903  			v.Aux = nil
   904  			v.SetArgs1(curM)
   905  		}
   906  		changed = true
   907  	}
   908  
   909  	if changed {
   910  		deadcode(f)
   911  	}
   912  }
   913  

View as plain text