decompose.go

     1  // Copyright 2015 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  import (
     8  	"cmp"
     9  	"slices"
    10  
    11  	"cmd/compile/internal/ssa"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/compile/internal/ssarewrite/rewritedec"
    14  	"cmd/compile/internal/ssarewrite/rewritedec64"
    15  	"cmd/compile/internal/types"
    16  )
    17  
    18  // decompose converts phi ops on compound builtin types into phi
    19  // ops on simple types, then invokes rewrite rules to decompose
    20  // other ops on those types.
    21  func decomposeBuiltin(f *ssa.Func) {
    22  	// Decompose phis
    23  	for _, b := range f.Blocks {
    24  		for _, v := range b.Values {
    25  			if v.Op != ssaop.OpPhi {
    26  				continue
    27  			}
    28  			decomposeBuiltinPhi(v)
    29  		}
    30  	}
    31  
    32  	// Decompose other values
    33  	// Note: Leave dead values because we need to keep the original
    34  	// values around so the name component resolution below can still work.
    35  	applyRewrite(f, rewritedec.RewriteBlock, rewritedec.RewriteValue, ssa.LeaveDeadValues)
    36  	if f.Config.RegSize == 4 {
    37  		applyRewrite(f, rewritedec64.RewriteBlock, rewritedec64.RewriteValue, ssa.LeaveDeadValues)
    38  	}
    39  
    40  	// Split up named values into their components.
    41  	// accumulate old names for aggregates (that are decomposed) in toDelete for efficient bulk deletion,
    42  	// accumulate new LocalSlots in newNames for addition after the iteration.  This decomposition is for
    43  	// builtin types with leaf components, and thus there is no need to reprocess the newly create LocalSlots.
    44  	var toDelete []namedVal
    45  	var newNames []ssa.LocalSlot
    46  	for i, name := range f.Names {
    47  		t := name.Type
    48  		switch {
    49  		case t.IsInteger() && t.Size() > f.Config.RegSize:
    50  			hiName, loName := f.SplitInt64(f.LocalSlotAddr(name))
    51  			newNames = maybeAppend2(f, newNames, hiName, loName)
    52  			for j, v := range f.NamedValues[name] {
    53  				if v.Op != ssaop.OpInt64Make {
    54  					continue
    55  				}
    56  				f.NamedValues[*hiName] = append(f.NamedValues[*hiName], v.Args[0])
    57  				f.NamedValues[*loName] = append(f.NamedValues[*loName], v.Args[1])
    58  				toDelete = append(toDelete, namedVal{i, j})
    59  			}
    60  		case t.IsComplex():
    61  			rName, iName := f.SplitComplex(f.LocalSlotAddr(name))
    62  			newNames = maybeAppend2(f, newNames, rName, iName)
    63  			for j, v := range f.NamedValues[name] {
    64  				if v.Op != ssaop.OpComplexMake {
    65  					continue
    66  				}
    67  				f.NamedValues[*rName] = append(f.NamedValues[*rName], v.Args[0])
    68  				f.NamedValues[*iName] = append(f.NamedValues[*iName], v.Args[1])
    69  				toDelete = append(toDelete, namedVal{i, j})
    70  			}
    71  		case t.IsString():
    72  			ptrName, lenName := f.SplitString(f.LocalSlotAddr(name))
    73  			newNames = maybeAppend2(f, newNames, ptrName, lenName)
    74  			for j, v := range f.NamedValues[name] {
    75  				if v.Op != ssaop.OpStringMake {
    76  					continue
    77  				}
    78  				f.NamedValues[*ptrName] = append(f.NamedValues[*ptrName], v.Args[0])
    79  				f.NamedValues[*lenName] = append(f.NamedValues[*lenName], v.Args[1])
    80  				toDelete = append(toDelete, namedVal{i, j})
    81  			}
    82  		case t.IsSlice():
    83  			ptrName, lenName, capName := f.SplitSlice(f.LocalSlotAddr(name))
    84  			newNames = maybeAppend2(f, newNames, ptrName, lenName)
    85  			newNames = maybeAppend(f, newNames, capName)
    86  			for j, v := range f.NamedValues[name] {
    87  				if v.Op != ssaop.OpSliceMake {
    88  					continue
    89  				}
    90  				f.NamedValues[*ptrName] = append(f.NamedValues[*ptrName], v.Args[0])
    91  				f.NamedValues[*lenName] = append(f.NamedValues[*lenName], v.Args[1])
    92  				f.NamedValues[*capName] = append(f.NamedValues[*capName], v.Args[2])
    93  				toDelete = append(toDelete, namedVal{i, j})
    94  			}
    95  		case t.IsInterface():
    96  			typeName, dataName := f.SplitInterface(f.LocalSlotAddr(name))
    97  			newNames = maybeAppend2(f, newNames, typeName, dataName)
    98  			for j, v := range f.NamedValues[name] {
    99  				if v.Op != ssaop.OpIMake {
   100  					continue
   101  				}
   102  				f.NamedValues[*typeName] = append(f.NamedValues[*typeName], v.Args[0])
   103  				f.NamedValues[*dataName] = append(f.NamedValues[*dataName], v.Args[1])
   104  				toDelete = append(toDelete, namedVal{i, j})
   105  			}
   106  		case t.IsFloat():
   107  			// floats are never decomposed, even ones bigger than RegSize
   108  		case t.Size() > f.Config.RegSize && !t.IsSIMD():
   109  			f.Fatalf("undecomposed named type %s %v", name, t)
   110  		}
   111  	}
   112  
   113  	deleteNamedVals(f, toDelete)
   114  	f.Names = append(f.Names, newNames...)
   115  }
   116  
   117  func maybeAppend(f *ssa.Func, ss []ssa.LocalSlot, s *ssa.LocalSlot) []ssa.LocalSlot {
   118  	if _, ok := f.NamedValues[*s]; !ok {
   119  		f.NamedValues[*s] = nil
   120  		return append(ss, *s)
   121  	}
   122  	return ss
   123  }
   124  
   125  func maybeAppend2(f *ssa.Func, ss []ssa.LocalSlot, s1, s2 *ssa.LocalSlot) []ssa.LocalSlot {
   126  	return maybeAppend(f, maybeAppend(f, ss, s1), s2)
   127  }
   128  
   129  func decomposeBuiltinPhi(v *ssa.Value) {
   130  	switch {
   131  	case v.Type.IsInteger() && v.Type.Size() > v.Block.Func.Config.RegSize:
   132  		decomposeInt64Phi(v)
   133  	case v.Type.IsComplex():
   134  		decomposeComplexPhi(v)
   135  	case v.Type.IsString():
   136  		decomposeStringPhi(v)
   137  	case v.Type.IsSlice():
   138  		decomposeSlicePhi(v)
   139  	case v.Type.IsInterface():
   140  		decomposeInterfacePhi(v)
   141  	case v.Type.IsFloat():
   142  		// floats are never decomposed, even ones bigger than RegSize
   143  	case v.Type.Size() > v.Block.Func.Config.RegSize && !v.Type.IsSIMD():
   144  		v.Fatalf("%v undecomposed type %v", v, v.Type)
   145  	}
   146  }
   147  
   148  func decomposeStringPhi(v *ssa.Value) {
   149  	types := &v.Block.Func.Config.Types
   150  	ptrType := types.BytePtr
   151  	lenType := types.Int
   152  
   153  	ptr := v.Block.NewValue0(v.Pos, ssaop.OpPhi, ptrType)
   154  	len := v.Block.NewValue0(v.Pos, ssaop.OpPhi, lenType)
   155  	for _, a := range v.Args {
   156  		ptr.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpStringPtr, ptrType, a))
   157  		len.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpStringLen, lenType, a))
   158  	}
   159  	v.Reset(ssaop.OpStringMake)
   160  	v.AddArg(ptr)
   161  	v.AddArg(len)
   162  }
   163  
   164  func decomposeSlicePhi(v *ssa.Value) {
   165  	types := &v.Block.Func.Config.Types
   166  	ptrType := v.Type.Elem().PtrTo()
   167  	lenType := types.Int
   168  
   169  	ptr := v.Block.NewValue0(v.Pos, ssaop.OpPhi, ptrType)
   170  	len := v.Block.NewValue0(v.Pos, ssaop.OpPhi, lenType)
   171  	cap := v.Block.NewValue0(v.Pos, ssaop.OpPhi, lenType)
   172  	for _, a := range v.Args {
   173  		ptr.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpSlicePtr, ptrType, a))
   174  		len.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpSliceLen, lenType, a))
   175  		cap.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpSliceCap, lenType, a))
   176  	}
   177  	v.Reset(ssaop.OpSliceMake)
   178  	v.AddArg(ptr)
   179  	v.AddArg(len)
   180  	v.AddArg(cap)
   181  }
   182  
   183  func decomposeInt64Phi(v *ssa.Value) {
   184  	cfgtypes := &v.Block.Func.Config.Types
   185  	var partType *types.Type
   186  	if v.Type.IsSigned() {
   187  		partType = cfgtypes.Int32
   188  	} else {
   189  		partType = cfgtypes.UInt32
   190  	}
   191  
   192  	hi := v.Block.NewValue0(v.Pos, ssaop.OpPhi, partType)
   193  	lo := v.Block.NewValue0(v.Pos, ssaop.OpPhi, cfgtypes.UInt32)
   194  	for _, a := range v.Args {
   195  		hi.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpInt64Hi, partType, a))
   196  		lo.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpInt64Lo, cfgtypes.UInt32, a))
   197  	}
   198  	v.Reset(ssaop.OpInt64Make)
   199  	v.AddArg(hi)
   200  	v.AddArg(lo)
   201  }
   202  
   203  func decomposeComplexPhi(v *ssa.Value) {
   204  	cfgtypes := &v.Block.Func.Config.Types
   205  	var partType *types.Type
   206  	switch z := v.Type.Size(); z {
   207  	case 8:
   208  		partType = cfgtypes.Float32
   209  	case 16:
   210  		partType = cfgtypes.Float64
   211  	default:
   212  		v.Fatalf("decomposeComplexPhi: bad complex size %d", z)
   213  	}
   214  
   215  	real := v.Block.NewValue0(v.Pos, ssaop.OpPhi, partType)
   216  	imag := v.Block.NewValue0(v.Pos, ssaop.OpPhi, partType)
   217  	for _, a := range v.Args {
   218  		real.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpComplexReal, partType, a))
   219  		imag.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpComplexImag, partType, a))
   220  	}
   221  	v.Reset(ssaop.OpComplexMake)
   222  	v.AddArg(real)
   223  	v.AddArg(imag)
   224  }
   225  
   226  func decomposeInterfacePhi(v *ssa.Value) {
   227  	uintptrType := v.Block.Func.Config.Types.Uintptr
   228  	ptrType := v.Block.Func.Config.Types.BytePtr
   229  
   230  	itab := v.Block.NewValue0(v.Pos, ssaop.OpPhi, uintptrType)
   231  	data := v.Block.NewValue0(v.Pos, ssaop.OpPhi, ptrType)
   232  	for _, a := range v.Args {
   233  		itab.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpITab, uintptrType, a))
   234  		data.AddArg(a.Block.NewValue1(v.Pos, ssaop.OpIData, ptrType, a))
   235  	}
   236  	v.Reset(ssaop.OpIMake)
   237  	v.AddArg(itab)
   238  	v.AddArg(data)
   239  }
   240  
   241  func decomposeUser(f *ssa.Func) {
   242  	for _, b := range f.Blocks {
   243  		for _, v := range b.Values {
   244  			if v.Op != ssaop.OpPhi {
   245  				continue
   246  			}
   247  			decomposeUserPhi(v)
   248  		}
   249  	}
   250  	// Split up named values into their components.
   251  	i := 0
   252  	var newNames []ssa.LocalSlot
   253  	for _, name := range f.Names {
   254  		t := name.Type
   255  		switch {
   256  		case isStructNotSIMD(t):
   257  			newNames = decomposeUserStructInto(f, f.LocalSlotAddr(name), newNames)
   258  		case t.IsArray():
   259  			newNames = decomposeUserArrayInto(f, f.LocalSlotAddr(name), newNames)
   260  		default:
   261  			f.Names[i] = name
   262  			i++
   263  		}
   264  	}
   265  	f.Names = f.Names[:i]
   266  	f.Names = append(f.Names, newNames...)
   267  }
   268  
   269  // decomposeUserArrayInto creates names for the element(s) of arrays referenced
   270  // by name where possible, and appends those new names to slots, which is then
   271  // returned.
   272  func decomposeUserArrayInto(f *ssa.Func, name *ssa.LocalSlot, slots []ssa.LocalSlot) []ssa.LocalSlot {
   273  	t := name.Type
   274  	if t.Size() == 0 {
   275  		// TODO(khr): Not sure what to do here.  Probably nothing.
   276  		// Names for empty arrays aren't important.
   277  		return slots
   278  	}
   279  	if t.NumElem() != 1 {
   280  		// shouldn't get here due to CanSSA
   281  		f.Fatalf("array not of size 1")
   282  	}
   283  	elemName := f.SplitArray(name)
   284  	var keep []*ssa.Value
   285  	for _, v := range f.NamedValues[*name] {
   286  		if v.Op != ssaop.OpArrayMake1 {
   287  			keep = append(keep, v)
   288  			continue
   289  		}
   290  		f.NamedValues[*elemName] = append(f.NamedValues[*elemName], v.Args[0])
   291  	}
   292  	if len(keep) == 0 {
   293  		// delete the name for the array as a whole
   294  		delete(f.NamedValues, *name)
   295  	} else {
   296  		f.NamedValues[*name] = keep
   297  	}
   298  
   299  	if t.Elem().IsArray() {
   300  		return decomposeUserArrayInto(f, elemName, slots)
   301  	} else if isStructNotSIMD(t.Elem()) {
   302  		return decomposeUserStructInto(f, elemName, slots)
   303  	}
   304  
   305  	return append(slots, *elemName)
   306  }
   307  
   308  // decomposeUserStructInto creates names for the fields(s) of structs referenced
   309  // by name where possible, and appends those new names to slots, which is then
   310  // returned.
   311  func decomposeUserStructInto(f *ssa.Func, name *ssa.LocalSlot, slots []ssa.LocalSlot) []ssa.LocalSlot {
   312  	fnames := []*ssa.LocalSlot{} // slots for struct in name
   313  	t := name.Type
   314  	n := t.NumFields()
   315  
   316  	for i := 0; i < n; i++ {
   317  		fs := f.SplitStruct(name, i)
   318  		fnames = append(fnames, fs)
   319  		// arrays and structs will be decomposed further, so
   320  		// there's no need to record a name
   321  		if !fs.Type.IsArray() && !isStructNotSIMD(fs.Type) {
   322  			slots = maybeAppend(f, slots, fs)
   323  		}
   324  	}
   325  
   326  	var keep []*ssa.Value
   327  	// create named values for each struct field
   328  	for _, v := range f.NamedValues[*name] {
   329  		if v.Op != ssaop.OpStructMake || len(v.Args) != n {
   330  			keep = append(keep, v)
   331  			continue
   332  		}
   333  		for i := 0; i < len(fnames); i++ {
   334  			f.NamedValues[*fnames[i]] = append(f.NamedValues[*fnames[i]], v.Args[i])
   335  		}
   336  	}
   337  	if len(keep) == 0 {
   338  		// delete the name for the struct as a whole
   339  		delete(f.NamedValues, *name)
   340  	} else {
   341  		f.NamedValues[*name] = keep
   342  	}
   343  
   344  	// now that this f.NamedValues contains values for the struct
   345  	// fields, recurse into nested structs
   346  	for i := 0; i < n; i++ {
   347  		if isStructNotSIMD(name.Type.FieldType(i)) {
   348  			slots = decomposeUserStructInto(f, fnames[i], slots)
   349  			delete(f.NamedValues, *fnames[i])
   350  		} else if name.Type.FieldType(i).IsArray() {
   351  			slots = decomposeUserArrayInto(f, fnames[i], slots)
   352  			delete(f.NamedValues, *fnames[i])
   353  		}
   354  	}
   355  	return slots
   356  }
   357  func decomposeUserPhi(v *ssa.Value) {
   358  	switch {
   359  	case isStructNotSIMD(v.Type):
   360  		decomposeStructPhi(v)
   361  	case v.Type.IsArray():
   362  		decomposeArrayPhi(v)
   363  	}
   364  }
   365  
   366  // decomposeStructPhi replaces phi-of-struct with structmake(phi-for-each-field),
   367  // and then recursively decomposes the phis for each field.
   368  func decomposeStructPhi(v *ssa.Value) {
   369  	t := v.Type
   370  	if t.Size() == 0 {
   371  		v.Reset(ssaop.OpEmpty)
   372  		return
   373  	}
   374  	n := t.NumFields()
   375  	fields := make([]*ssa.Value, 0, ssa.MaxStruct)
   376  	for i := 0; i < n; i++ {
   377  		fields = append(fields, v.Block.NewValue0(v.Pos, ssaop.OpPhi, t.FieldType(i)))
   378  	}
   379  	for _, a := range v.Args {
   380  		for i := 0; i < n; i++ {
   381  			fields[i].AddArg(a.Block.NewValue1I(v.Pos, ssaop.OpStructSelect, t.FieldType(i), int64(i), a))
   382  		}
   383  	}
   384  	v.Reset(ssaop.OpStructMake)
   385  	v.AddArgs(fields...)
   386  
   387  	// Recursively decompose phis for each field.
   388  	for _, f := range fields {
   389  		decomposeUserPhi(f)
   390  	}
   391  }
   392  
   393  // decomposeArrayPhi replaces phi-of-array with arraymake(phi-of-array-element),
   394  // and then recursively decomposes the element phi.
   395  func decomposeArrayPhi(v *ssa.Value) {
   396  	t := v.Type
   397  	if t.Size() == 0 {
   398  		v.Reset(ssaop.OpEmpty)
   399  		return
   400  	}
   401  	if t.NumElem() != 1 {
   402  		v.Fatalf("SSAable array must have no more than 1 element")
   403  	}
   404  	elem := v.Block.NewValue0(v.Pos, ssaop.OpPhi, t.Elem())
   405  	for _, a := range v.Args {
   406  		elem.AddArg(a.Block.NewValue1I(v.Pos, ssaop.OpArraySelect, t.Elem(), 0, a))
   407  	}
   408  	v.Reset(ssaop.OpArrayMake1)
   409  	v.AddArg(elem)
   410  
   411  	// Recursively decompose elem phi.
   412  	decomposeUserPhi(elem)
   413  }
   414  
   415  type namedVal struct {
   416  	locIndex, valIndex int // f.NamedValues[f.Names[locIndex]][valIndex] = key
   417  }
   418  
   419  // deleteNamedVals removes particular values with debugger names from f's naming data structures,
   420  // removes all values with OpInvalid, and re-sorts the list of Names.
   421  func deleteNamedVals(f *ssa.Func, toDelete []namedVal) {
   422  	// Arrange to delete from larger indices to smaller, to ensure swap-with-end deletion does not invalidate pending indices.
   423  	slices.SortFunc(toDelete, func(a, b namedVal) int {
   424  		if a.locIndex != b.locIndex {
   425  			return cmp.Compare(b.locIndex, a.locIndex)
   426  		}
   427  		return cmp.Compare(b.valIndex, a.valIndex)
   428  	})
   429  
   430  	// Get rid of obsolete names
   431  	for _, d := range toDelete {
   432  		loc := f.Names[d.locIndex]
   433  		vals := f.NamedValues[loc]
   434  		l := len(vals) - 1
   435  		if l > 0 {
   436  			vals[d.valIndex] = vals[l]
   437  		}
   438  		vals[l] = nil
   439  		f.NamedValues[loc] = vals[:l]
   440  	}
   441  	// Delete locations with no values attached.
   442  	end := len(f.Names)
   443  	for i := len(f.Names) - 1; i >= 0; i-- {
   444  		loc := f.Names[i]
   445  		vals := f.NamedValues[loc]
   446  		last := len(vals)
   447  		for j := len(vals) - 1; j >= 0; j-- {
   448  			if vals[j].Op == ssaop.OpInvalid {
   449  				last--
   450  				vals[j] = vals[last]
   451  				vals[last] = nil
   452  			}
   453  		}
   454  		if last < len(vals) {
   455  			f.NamedValues[loc] = vals[:last]
   456  		}
   457  		if len(vals) == 0 {
   458  			delete(f.NamedValues, loc)
   459  			end--
   460  			f.Names[i] = f.Names[end]
   461  			f.Names[end] = ssa.LocalSlot{}
   462  		}
   463  	}
   464  	f.Names = f.Names[:end]
   465  }
   466  
   467  func isStructNotSIMD(t *types.Type) bool {
   468  	return t.IsStruct() && !t.IsSIMD()
   469  }
   470
View as plain text