memcombine.go

     1  // Copyright 2023 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/base"
    12  	"cmd/compile/internal/ssa"
    13  	"cmd/compile/internal/ssa/ssaop"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/src"
    16  )
    17  
    18  // memcombine combines smaller loads and stores into larger ones.
    19  // This produces good code for encoding/binary operations and may help other
    20  // cases too. On architectures that do not allow unaligned accesses, the pass
    21  // uses pointer alignment facts to avoid introducing unaligned wider operations.
    22  func memcombine(f *ssa.Func) {
    23  	var ptrAlignments []int8
    24  	if !f.Config.UnalignedOK {
    25  		ptrAlignments = f.Cache.AllocInt8Slice(f.NumValues())
    26  		defer f.Cache.FreeInt8Slice(ptrAlignments)
    27  		computePtrAlignments(f, ptrAlignments)
    28  	}
    29  	memcombineLoads(f, ptrAlignments)
    30  	memcombineStores(f, ptrAlignments)
    31  }
    32  
    33  func memcombineLoads(f *ssa.Func, ptrAlignments []int8) {
    34  	// Find "OR trees" to start with.
    35  	mark := f.NewSparseSet(f.NumValues())
    36  	defer f.RetSparseSet(mark)
    37  	var order []*ssa.Value
    38  
    39  	// Mark all values that are the argument of an OR.
    40  	for _, b := range f.Blocks {
    41  		for _, v := range b.Values {
    42  			if v.Op == ssaop.OpOr16 || v.Op == ssaop.OpOr32 || v.Op == ssaop.OpOr64 {
    43  				mark.Add(v.Args[0].ID)
    44  				mark.Add(v.Args[1].ID)
    45  			}
    46  		}
    47  	}
    48  	for _, b := range f.Blocks {
    49  		order = order[:0]
    50  		for _, v := range b.Values {
    51  			if v.Op != ssaop.OpOr16 && v.Op != ssaop.OpOr32 && v.Op != ssaop.OpOr64 {
    52  				continue
    53  			}
    54  			if mark.Contains(v.ID) {
    55  				// marked - means it is not the root of an OR tree
    56  				continue
    57  			}
    58  			// Add the OR tree rooted at v to the order.
    59  			// We use BFS here, but any walk that puts roots before leaves would work.
    60  			i := len(order)
    61  			order = append(order, v)
    62  			for ; i < len(order); i++ {
    63  				x := order[i]
    64  				for j := 0; j < 2; j++ {
    65  					a := x.Args[j]
    66  					if a.Op == ssaop.OpOr16 || a.Op == ssaop.OpOr32 || a.Op == ssaop.OpOr64 {
    67  						order = append(order, a)
    68  					}
    69  				}
    70  			}
    71  		}
    72  		for _, v := range order {
    73  			max := f.Config.RegSize
    74  			switch v.Op {
    75  			case ssaop.OpOr64:
    76  			case ssaop.OpOr32:
    77  				max = 4
    78  			case ssaop.OpOr16:
    79  				max = 2
    80  			default:
    81  				continue
    82  			}
    83  			for n := max; n > 1; n /= 2 {
    84  				if combineLoads(v, n, ptrAlignments) {
    85  					break
    86  				}
    87  			}
    88  		}
    89  	}
    90  }
    91  
    92  // A BaseAddress represents the address ptr+idx, where
    93  // ptr is a pointer type and idx is an integer type.
    94  // idx may be nil, in which case it is treated as 0.
    95  type BaseAddress struct {
    96  	ptr *ssa.Value
    97  	idx Index
    98  }
    99  
   100  // Index represents an address index in the form exp<<shift.
   101  //
   102  // The shift is typically introduced by slice indexing (log2(element size)),
   103  // but may also originate from shifts in the source expression.
   104  type Index struct {
   105  	exp   *ssa.Value
   106  	shift int64
   107  }
   108  
   109  func getConst(v *ssa.Value) (int64, bool) {
   110  	if v.Op == ssaop.OpConst32 || v.Op == ssaop.OpConst64 {
   111  		return v.AuxInt, true
   112  	}
   113  	return 0, false
   114  }
   115  
   116  func peelAdd(v *ssa.Value) (exp *ssa.Value, imm int64) {
   117  	if v == nil {
   118  		return nil, 0
   119  	}
   120  
   121  	if v.Op == ssaop.OpAdd32 || v.Op == ssaop.OpAdd64 {
   122  		if imm, ok := getConst(v.Args[0]); ok {
   123  			return v.Args[1], imm
   124  		}
   125  
   126  		if imm, ok := getConst(v.Args[1]); ok {
   127  			return v.Args[0], imm
   128  		}
   129  	}
   130  
   131  	return v, 0
   132  }
   133  
   134  func peelShift(v *ssa.Value) (exp *ssa.Value, shift int64) {
   135  	if v == nil {
   136  		return nil, 0
   137  	}
   138  
   139  	if v.Op == ssaop.OpLsh64x64 || v.Op == ssaop.OpLsh32x64 || v.Op == ssaop.OpLsh16x64 {
   140  		if imm, ok := getConst(v.Args[1]); ok {
   141  			return v.Args[0], imm
   142  		}
   143  	}
   144  	return v, 0
   145  }
   146  
   147  // splitPtr returns the base address of ptr and any
   148  // constant offset from that base.
   149  // BaseAddress{ptr,nil},0 is always a valid result, but splitPtr
   150  // tries to peel away as many constants into off as possible.
   151  func splitPtr(ptr *ssa.Value) (BaseAddress, int64) {
   152  	var idx Index
   153  	var off int64
   154  	for {
   155  		if ptr.Op == ssaop.OpOffPtr {
   156  			off += ptr.AuxInt
   157  			ptr = ptr.Args[0]
   158  			continue
   159  		}
   160  
   161  		if ptr.Op == ssaop.OpAddPtr {
   162  			if idx.exp != nil {
   163  				// We have two or more indexing values.
   164  				// Pick the first one we found.
   165  				break
   166  			}
   167  
   168  			// Common slice indexing patterns:
   169  			//
   170  			// exp
   171  			// exp + offset
   172  			// (exp << shift) + offset
   173  			// (exp+imm)<<shift + offset
   174  			//
   175  			// where shift is typically log2(element size).
   176  
   177  			idx.exp = ptr.Args[1]
   178  			ptr = ptr.Args[0]
   179  
   180  			// Peel offset
   181  			var offset int64
   182  			idx.exp, offset = peelAdd(idx.exp)
   183  			off += offset
   184  
   185  			// Peel shift
   186  			idx.exp, idx.shift = peelShift(idx.exp)
   187  
   188  			// Peel imm
   189  			var imm int64
   190  			idx.exp, imm = peelAdd(idx.exp)
   191  
   192  			off += imm << idx.shift
   193  			continue
   194  		}
   195  
   196  		break
   197  	}
   198  
   199  	return BaseAddress{ptr: ptr, idx: idx}, off
   200  }
   201  
   202  // computePtrAlignments computes pointer alignment facts from typed base pointers
   203  // and constant offsets.
   204  func computePtrAlignments(f *ssa.Func, ptrAlignments []int8) {
   205  	for _, b := range slices.Backward(f.Postorder()) {
   206  		for _, v := range b.Values {
   207  			ptrAlignments[v.ID] = int8(valuePtrAlignment(v, ptrAlignments))
   208  		}
   209  	}
   210  }
   211  
   212  // ptrAlignment only reads already-computed facts. Zero/not-yet-known means
   213  // alignment 1, avoiding recursive Phi/cycle walks.
   214  func ptrAlignment(ptr *ssa.Value, ptrAlignments []int8) int64 {
   215  	if align := ptrAlignments[ptr.ID]; align > 0 {
   216  		return int64(align)
   217  	}
   218  	return 1
   219  }
   220  
   221  // valuePtrAlignment computes one entry in ptrAlignments.
   222  func valuePtrAlignment(v *ssa.Value, ptrAlignments []int8) int64 {
   223  	// computePtrAlignments visits every SSA value, not just pointer values.
   224  	if !v.Type.IsPtr() {
   225  		return 1
   226  	}
   227  
   228  	switch v.Op {
   229  	case ssaop.OpOffPtr:
   230  		return offsetAlignment(ptrAlignment(v.Args[0], ptrAlignments), v.AuxInt)
   231  	case ssaop.OpCopy, ssaop.OpNilCheck:
   232  		return ptrAlignment(v.Args[0], ptrAlignments)
   233  	case ssaop.OpAddr, ssaop.OpLocalAddr, ssaop.OpArg, ssaop.OpArgIntReg:
   234  		return typeAlignment(v.Type.Elem())
   235  	case ssaop.OpPhi:
   236  		align := ptrAlignment(v.Args[0], ptrAlignments)
   237  		for _, arg := range v.Args[1:] {
   238  			if argAlign := ptrAlignment(arg, ptrAlignments); argAlign < align {
   239  				align = argAlign
   240  			}
   241  		}
   242  		return align
   243  	}
   244  	return 1
   245  }
   246  
   247  // typeAlignment returns a conservative alignment for t without calling
   248  // Type.Alignment, which may try to calculate type sizes while the compiler
   249  // back end is running concurrently.
   250  func typeAlignment(t *types.Type) int64 {
   251  	switch t.Kind() {
   252  	case types.TBOOL, types.TINT8, types.TUINT8:
   253  		return 1
   254  	case types.TINT16, types.TUINT16:
   255  		return 2
   256  	case types.TINT32, types.TUINT32, types.TFLOAT32, types.TCOMPLEX64:
   257  		return 4
   258  	case types.TINT64, types.TUINT64, types.TFLOAT64, types.TCOMPLEX128:
   259  		return 8
   260  	case types.TINT, types.TUINT, types.TUINTPTR, types.TPTR, types.TUNSAFEPTR, types.TSTRING, types.TSLICE, types.TFUNC, types.TMAP, types.TCHAN:
   261  		return int64(types.PtrSize)
   262  	case types.TARRAY:
   263  		return typeAlignment(t.Elem())
   264  	case types.TSTRUCT:
   265  		align := int64(1)
   266  		for _, f := range t.Fields() {
   267  			fieldAlign := typeAlignment(f.Type)
   268  			if fieldAlign > align {
   269  				align = fieldAlign
   270  			}
   271  		}
   272  		return align
   273  	}
   274  	return 1
   275  }
   276  
   277  func offsetAlignment(align, off int64) int64 {
   278  	off &= align - 1
   279  	if off == 0 {
   280  		return align
   281  	}
   282  	return off & -off
   283  }
   284  
   285  func combineLoads(root *ssa.Value, n int64, ptrAlignments []int8) bool {
   286  	orOp := root.Op
   287  	var shiftOp ssaop.Op
   288  	switch orOp {
   289  	case ssaop.OpOr64:
   290  		shiftOp = ssaop.OpLsh64x64
   291  	case ssaop.OpOr32:
   292  		shiftOp = ssaop.OpLsh32x64
   293  	case ssaop.OpOr16:
   294  		shiftOp = ssaop.OpLsh16x64
   295  	default:
   296  		return false
   297  	}
   298  
   299  	// Find n values that are ORed together with the above op.
   300  	a := make([]*ssa.Value, 0, 8)
   301  	a = append(a, root)
   302  	for i := 0; i < len(a) && int64(len(a)) < n; i++ {
   303  		v := a[i]
   304  		if v.Uses != 1 && v != root {
   305  			// Something in this subtree is used somewhere else.
   306  			return false
   307  		}
   308  		if v.Op == orOp {
   309  			a[i] = v.Args[0]
   310  			a = append(a, v.Args[1])
   311  			i--
   312  		}
   313  	}
   314  	if int64(len(a)) != n {
   315  		return false
   316  	}
   317  
   318  	// Check that the first entry to see what ops we're looking for.
   319  	// All the entries should be of the form shift(extend(load)), maybe with no shift.
   320  	v := a[0]
   321  	if v.Op == shiftOp {
   322  		v = v.Args[0]
   323  	}
   324  	var extOp ssaop.Op
   325  	if orOp == ssaop.OpOr64 && (v.Op == ssaop.OpZeroExt8to64 || v.Op == ssaop.OpZeroExt16to64 || v.Op == ssaop.OpZeroExt32to64) ||
   326  		orOp == ssaop.OpOr32 && (v.Op == ssaop.OpZeroExt8to32 || v.Op == ssaop.OpZeroExt16to32) ||
   327  		orOp == ssaop.OpOr16 && v.Op == ssaop.OpZeroExt8to16 {
   328  		extOp = v.Op
   329  		v = v.Args[0]
   330  	} else {
   331  		return false
   332  	}
   333  	if v.Op != ssaop.OpLoad {
   334  		return false
   335  	}
   336  	base, _ := splitPtr(v.Args[0])
   337  	mem := v.Args[1]
   338  	size := v.Type.Size()
   339  
   340  	if root.Block.Func.Config.Arch == "S390X" {
   341  		// s390x can't handle unaligned accesses to global variables.
   342  		if base.ptr.Op == ssaop.OpAddr {
   343  			return false
   344  		}
   345  	}
   346  
   347  	// Check all the entries, extract useful info.
   348  	type LoadRecord struct {
   349  		load   *ssa.Value
   350  		offset int64 // offset of load address from base
   351  		shift  int64
   352  	}
   353  	r := make([]LoadRecord, n, 8)
   354  	for i := int64(0); i < n; i++ {
   355  		v := a[i]
   356  		if v.Uses != 1 {
   357  			return false
   358  		}
   359  		shift := int64(0)
   360  		if v.Op == shiftOp {
   361  			v, shift = peelShift(v)
   362  			if v.Uses != 1 {
   363  				return false
   364  			}
   365  		}
   366  		if v.Op != extOp {
   367  			return false
   368  		}
   369  		load := v.Args[0]
   370  		if load.Op != ssaop.OpLoad {
   371  			return false
   372  		}
   373  		if load.Uses != 1 {
   374  			return false
   375  		}
   376  		if load.Args[1] != mem {
   377  			return false
   378  		}
   379  		p, off := splitPtr(load.Args[0])
   380  		if p != base {
   381  			return false
   382  		}
   383  		r[i] = LoadRecord{load: load, offset: off, shift: shift}
   384  	}
   385  
   386  	// Sort in memory address order.
   387  	slices.SortFunc(r, func(a, b LoadRecord) int {
   388  		return cmp.Compare(a.offset, b.offset)
   389  	})
   390  
   391  	// Check that we have contiguous offsets.
   392  	for i := int64(0); i < n; i++ {
   393  		if r[i].offset != r[0].offset+i*size {
   394  			return false
   395  		}
   396  	}
   397  	if !root.Block.Func.Config.UnalignedOK && ptrAlignment(r[0].load.Args[0], ptrAlignments) < n*size {
   398  		return false
   399  	}
   400  
   401  	// Check for reads in little-endian or big-endian order.
   402  	shift0 := r[0].shift
   403  	isLittleEndian := true
   404  	for i := int64(0); i < n; i++ {
   405  		if r[i].shift != shift0+i*size*8 {
   406  			isLittleEndian = false
   407  			break
   408  		}
   409  	}
   410  	isBigEndian := true
   411  	for i := int64(0); i < n; i++ {
   412  		if r[i].shift != shift0-i*size*8 {
   413  			isBigEndian = false
   414  			break
   415  		}
   416  	}
   417  	if !isLittleEndian && !isBigEndian {
   418  		return false
   419  	}
   420  
   421  	// Find a place to put the new load.
   422  	// This is tricky, because it has to be at a point where
   423  	// its memory argument is live. We can't just put it in root.Block.
   424  	// We use the block of the latest load.
   425  	loads := make([]*ssa.Value, n, 8)
   426  	for i := int64(0); i < n; i++ {
   427  		loads[i] = r[i].load
   428  	}
   429  	loadBlock := mergePoint(root.Block, loads...)
   430  	if loadBlock == nil {
   431  		return false
   432  	}
   433  	// Find a source position to use.
   434  	pos := src.NoXPos
   435  	for _, load := range loads {
   436  		if load.Block == loadBlock {
   437  			pos = load.Pos
   438  			break
   439  		}
   440  	}
   441  	if pos == src.NoXPos {
   442  		return false
   443  	}
   444  
   445  	// Check to see if we need byte swap before storing.
   446  	needSwap := isLittleEndian && root.Block.Func.Config.BigEndian ||
   447  		isBigEndian && !root.Block.Func.Config.BigEndian
   448  	if needSwap && (size != 1 || !root.Block.Func.Config.HaveByteSwap(n)) {
   449  		return false
   450  	}
   451  
   452  	// This is the commit point.
   453  
   454  	// First, issue load at lowest address.
   455  	v = loadBlock.NewValue2(pos, ssaop.OpLoad, sizeType(n*size), r[0].load.Args[0], mem)
   456  
   457  	// Byte swap if needed,
   458  	if needSwap {
   459  		v = byteSwap(loadBlock, pos, v)
   460  	}
   461  
   462  	// Extend if needed.
   463  	if n*size < root.Type.Size() {
   464  		v = zeroExtend(loadBlock, pos, v, n*size, root.Type.Size())
   465  	}
   466  
   467  	// Shift if needed.
   468  	if isLittleEndian && shift0 != 0 {
   469  		v = leftShift(loadBlock, pos, v, shift0)
   470  	}
   471  	if isBigEndian && shift0-(n-1)*size*8 != 0 {
   472  		v = leftShift(loadBlock, pos, v, shift0-(n-1)*size*8)
   473  	}
   474  
   475  	// Install with (Copy v).
   476  	root.Reset(ssaop.OpCopy)
   477  	root.AddArg(v)
   478  
   479  	// Clobber the loads, just to prevent additional work being done on
   480  	// subtrees (which are now unreachable).
   481  	for i := int64(0); i < n; i++ {
   482  		ssa.Clobber(r[i].load)
   483  	}
   484  	return true
   485  }
   486  
   487  func memcombineStores(f *ssa.Func, ptrAlignments []int8) {
   488  	mark := f.NewSparseSet(f.NumValues())
   489  	defer f.RetSparseSet(mark)
   490  	var order []*ssa.Value
   491  
   492  	for _, b := range f.Blocks {
   493  		// Mark all stores which are not last in a store sequence.
   494  		mark.Clear()
   495  		for _, v := range b.Values {
   496  			if v.Op == ssaop.OpStore {
   497  				mark.Add(v.MemoryArg().ID)
   498  			}
   499  		}
   500  
   501  		// pick an order for visiting stores such that
   502  		// later stores come earlier in the ordering.
   503  		order = order[:0]
   504  		for _, v := range b.Values {
   505  			if v.Op != ssaop.OpStore {
   506  				continue
   507  			}
   508  			if mark.Contains(v.ID) {
   509  				continue // not last in a chain of stores
   510  			}
   511  			for {
   512  				order = append(order, v)
   513  				v = v.Args[2]
   514  				if v.Block != b || v.Op != ssaop.OpStore {
   515  					break
   516  				}
   517  			}
   518  		}
   519  
   520  		// Look for combining opportunities at each store in queue order.
   521  		for _, v := range order {
   522  			if v.Op != ssaop.OpStore { // already rewritten
   523  				continue
   524  			}
   525  
   526  			size := v.Aux.(*types.Type).Size()
   527  			if size >= f.Config.RegSize || size == 0 {
   528  				continue
   529  			}
   530  
   531  			combineStores(v, ptrAlignments)
   532  		}
   533  	}
   534  }
   535  
   536  // combineStores tries to combine the stores ending in root.
   537  func combineStores(root *ssa.Value, ptrAlignments []int8) {
   538  	// Helper functions.
   539  	maxRegSize := root.Block.Func.Config.RegSize
   540  	type StoreRecord struct {
   541  		store  *ssa.Value
   542  		offset int64
   543  		size   int64
   544  	}
   545  	getShiftBase := func(a []StoreRecord) *ssa.Value {
   546  		x := a[0].store.Args[1]
   547  		y := a[1].store.Args[1]
   548  		switch x.Op {
   549  		case ssaop.OpTrunc64to8, ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc16to8:
   550  			x = x.Args[0]
   551  		default:
   552  			return nil
   553  		}
   554  		switch y.Op {
   555  		case ssaop.OpTrunc64to8, ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc16to8:
   556  			y = y.Args[0]
   557  		default:
   558  			return nil
   559  		}
   560  		var x2 *ssa.Value
   561  		switch x.Op {
   562  		case ssaop.OpRsh64Ux64, ssaop.OpRsh32Ux64, ssaop.OpRsh16Ux64:
   563  			x2 = x.Args[0]
   564  		default:
   565  		}
   566  		var y2 *ssa.Value
   567  		switch y.Op {
   568  		case ssaop.OpRsh64Ux64, ssaop.OpRsh32Ux64, ssaop.OpRsh16Ux64:
   569  			y2 = y.Args[0]
   570  		default:
   571  		}
   572  		if y2 == x {
   573  			// a shift of x and x itself.
   574  			return x
   575  		}
   576  		if x2 == y {
   577  			// a shift of y and y itself.
   578  			return y
   579  		}
   580  		if x2 == y2 {
   581  			// 2 shifts both of the same argument.
   582  			return x2
   583  		}
   584  		return nil
   585  	}
   586  	isShiftBase := func(v, base *ssa.Value) bool {
   587  		val := v.Args[1]
   588  		switch val.Op {
   589  		case ssaop.OpTrunc64to8, ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc16to8:
   590  			val = val.Args[0]
   591  		default:
   592  			return false
   593  		}
   594  		if val == base {
   595  			return true
   596  		}
   597  		switch val.Op {
   598  		case ssaop.OpRsh64Ux64, ssaop.OpRsh32Ux64, ssaop.OpRsh16Ux64:
   599  			val = val.Args[0]
   600  		default:
   601  			return false
   602  		}
   603  		return val == base
   604  	}
   605  	shift := func(v, base *ssa.Value) int64 {
   606  		val := v.Args[1]
   607  		switch val.Op {
   608  		case ssaop.OpTrunc64to8, ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc16to8:
   609  			val = val.Args[0]
   610  		default:
   611  			return -1
   612  		}
   613  		if val == base {
   614  			return 0
   615  		}
   616  		switch val.Op {
   617  		case ssaop.OpRsh64Ux64, ssaop.OpRsh32Ux64, ssaop.OpRsh16Ux64:
   618  			val = val.Args[1]
   619  		default:
   620  			return -1
   621  		}
   622  		if val.Op != ssaop.OpConst64 {
   623  			return -1
   624  		}
   625  		return val.AuxInt
   626  	}
   627  
   628  	// Gather n stores to look at. Check easy conditions we require.
   629  	allMergeable := make([]StoreRecord, 0, 8)
   630  	rbase, roff := splitPtr(root.Args[0])
   631  	if root.Block.Func.Config.Arch == "S390X" {
   632  		// s390x can't handle unaligned accesses to global variables.
   633  		if rbase.ptr.Op == ssaop.OpAddr {
   634  			return
   635  		}
   636  	}
   637  	allMergeable = append(allMergeable, StoreRecord{root, roff, root.Aux.(*types.Type).Size()})
   638  	allMergeableSize := root.Aux.(*types.Type).Size()
   639  	// TODO: this loop strictly requires stores to chain together in memory.
   640  	// maybe we can break this constraint and match more patterns.
   641  	for i, x := 1, root.Args[2]; i < 8; i, x = i+1, x.Args[2] {
   642  		if x.Op != ssaop.OpStore {
   643  			break
   644  		}
   645  		if x.Block != root.Block {
   646  			break
   647  		}
   648  		if x.Uses != 1 { // Note: root can have more than one use.
   649  			break
   650  		}
   651  		xSize := x.Aux.(*types.Type).Size()
   652  		if xSize == 0 {
   653  			break
   654  		}
   655  		if xSize > maxRegSize-allMergeableSize {
   656  			break
   657  		}
   658  		base, off := splitPtr(x.Args[0])
   659  		if base != rbase {
   660  			break
   661  		}
   662  		allMergeable = append(allMergeable, StoreRecord{x, off, xSize})
   663  		allMergeableSize += xSize
   664  	}
   665  	if len(allMergeable) <= 1 {
   666  		return
   667  	}
   668  	// Fit the combined total size to be one of the register size.
   669  	mergeableSet := map[int64][]StoreRecord{}
   670  	for i, size := 0, int64(0); i < len(allMergeable); i++ {
   671  		size += allMergeable[i].size
   672  		for _, bucketSize := range []int64{8, 4, 2} {
   673  			if size == bucketSize {
   674  				mergeableSet[size] = slices.Clone(allMergeable[:i+1])
   675  				break
   676  			}
   677  		}
   678  	}
   679  	var a []StoreRecord
   680  	var aTotalSize int64
   681  	var mem *ssa.Value
   682  	var pos src.XPos
   683  	// Pick the largest mergeable set.
   684  	for _, s := range []int64{8, 4, 2} {
   685  		candidate := mergeableSet[s]
   686  		// TODO: a refactoring might be more efficient:
   687  		// Find a bunch of stores that are all adjacent and then decide how big a chunk of
   688  		// those sequential stores to combine.
   689  		if len(candidate) >= 2 {
   690  			// Before we sort, grab the memory arg the result should have.
   691  			mem = candidate[len(candidate)-1].store.Args[2]
   692  			// Also grab position of first store (last in array = first in memory order).
   693  			pos = candidate[len(candidate)-1].store.Pos
   694  			// Sort stores in increasing address order.
   695  			slices.SortFunc(candidate, func(sr1, sr2 StoreRecord) int {
   696  				return cmp.Compare(sr1.offset, sr2.offset)
   697  			})
   698  			// Check that everything is written to sequential locations.
   699  			sequential := true
   700  			for i := 1; i < len(candidate); i++ {
   701  				if candidate[i].offset != candidate[i-1].offset+candidate[i-1].size {
   702  					sequential = false
   703  					break
   704  				}
   705  			}
   706  			if sequential {
   707  				a = candidate
   708  				aTotalSize = s
   709  				break
   710  			}
   711  		}
   712  	}
   713  	if len(a) <= 1 {
   714  		return
   715  	}
   716  	// Memory location we're going to write at (the lowest one).
   717  	ptr := a[0].store.Args[0]
   718  	if !root.Block.Func.Config.UnalignedOK && ptrAlignment(ptr, ptrAlignments) < aTotalSize {
   719  		return
   720  	}
   721  
   722  	// Check for constant stores
   723  	isConst := true
   724  	for i := range a {
   725  		switch a[i].store.Args[1].Op {
   726  		case ssaop.OpConst32, ssaop.OpConst16, ssaop.OpConst8, ssaop.OpConstBool:
   727  		default:
   728  			isConst = false
   729  		}
   730  		if !isConst {
   731  			break
   732  		}
   733  	}
   734  	if isConst {
   735  		// Modify root to do all the stores.
   736  		var c int64
   737  		for i := range a {
   738  			mask := int64(1)<<(8*a[i].size) - 1
   739  			s := 8 * (a[i].offset - a[0].offset)
   740  			if root.Block.Func.Config.BigEndian {
   741  				s = (aTotalSize-a[i].size)*8 - s
   742  			}
   743  			c |= (a[i].store.Args[1].AuxInt & mask) << s
   744  		}
   745  		var cv *ssa.Value
   746  		switch aTotalSize {
   747  		case 2:
   748  			cv = root.Block.Func.ConstInt16(types.Types[types.TUINT16], int16(c))
   749  		case 4:
   750  			cv = root.Block.Func.ConstInt32(types.Types[types.TUINT32], int32(c))
   751  		case 8:
   752  			cv = root.Block.Func.ConstInt64(types.Types[types.TUINT64], c)
   753  		}
   754  
   755  		// Move all the stores to the root.
   756  		for i := range a {
   757  			v := a[i].store
   758  			if v == root {
   759  				v.Aux = cv.Type // widen store type
   760  				v.Pos = pos
   761  				v.SetArg(0, ptr)
   762  				v.SetArg(1, cv)
   763  				v.SetArg(2, mem)
   764  			} else {
   765  				ssa.Clobber(v)
   766  				v.Type = types.Types[types.TBOOL] // erase memory type
   767  			}
   768  		}
   769  		return
   770  	}
   771  
   772  	// Check for consecutive loads as the source of the stores.
   773  	var loadMem *ssa.Value
   774  	var loadBase BaseAddress
   775  	var loadIdx int64
   776  	for i := range a {
   777  		load := a[i].store.Args[1]
   778  		if load.Op != ssaop.OpLoad {
   779  			loadMem = nil
   780  			break
   781  		}
   782  		if load.Uses != 1 {
   783  			loadMem = nil
   784  			break
   785  		}
   786  		if load.Type.HasPointers() {
   787  			// Don't combine stores containing a pointer, as we need
   788  			// a write barrier for those. This can happen on an
   789  			// 8-byte-reg/4-byte-ptr architecture like wasm32.
   790  			loadMem = nil
   791  			break
   792  		}
   793  		mem := load.Args[1]
   794  		base, idx := splitPtr(load.Args[0])
   795  		if loadMem == nil {
   796  			// First one we found
   797  			loadMem = mem
   798  			loadBase = base
   799  			loadIdx = idx
   800  			continue
   801  		}
   802  		if base != loadBase || mem != loadMem {
   803  			loadMem = nil
   804  			break
   805  		}
   806  		if idx != loadIdx+(a[i].offset-a[0].offset) {
   807  			loadMem = nil
   808  			break
   809  		}
   810  	}
   811  	if loadMem != nil {
   812  		// Modify the first load to do a larger load instead.
   813  		load := a[0].store.Args[1]
   814  		if !root.Block.Func.Config.UnalignedOK && ptrAlignment(load.Args[0], ptrAlignments) < aTotalSize {
   815  			return
   816  		}
   817  		switch aTotalSize {
   818  		case 2:
   819  			load.Type = types.Types[types.TUINT16]
   820  		case 4:
   821  			load.Type = types.Types[types.TUINT32]
   822  		case 8:
   823  			load.Type = types.Types[types.TUINT64]
   824  		}
   825  
   826  		// Modify root to do the store.
   827  		for i := range a {
   828  			v := a[i].store
   829  			if v == root {
   830  				v.Aux = load.Type // widen store type
   831  				v.Pos = pos
   832  				v.SetArg(0, ptr)
   833  				v.SetArg(1, load)
   834  				v.SetArg(2, mem)
   835  			} else {
   836  				ssa.Clobber(v)
   837  				v.Type = types.Types[types.TBOOL] // erase memory type
   838  			}
   839  		}
   840  		return
   841  	}
   842  
   843  	// Check that all the shift/trunc are of the same base value.
   844  	shiftBase := getShiftBase(a)
   845  	if shiftBase == nil {
   846  		return
   847  	}
   848  	for i := range a {
   849  		if !isShiftBase(a[i].store, shiftBase) {
   850  			return
   851  		}
   852  	}
   853  
   854  	// Check for writes in little-endian or big-endian order.
   855  	isLittleEndian := true
   856  	shift0 := shift(a[0].store, shiftBase)
   857  	for i := 1; i < len(a); i++ {
   858  		if shift(a[i].store, shiftBase) != shift0+(a[i].offset-a[0].offset)*8 {
   859  			isLittleEndian = false
   860  			break
   861  		}
   862  	}
   863  	isBigEndian := true
   864  	shiftedSize := int64(0)
   865  	for i := 1; i < len(a); i++ {
   866  		shiftedSize += a[i].size
   867  		if shift(a[i].store, shiftBase) != shift0-shiftedSize*8 {
   868  			isBigEndian = false
   869  			break
   870  		}
   871  	}
   872  	if !isLittleEndian && !isBigEndian {
   873  		return
   874  	}
   875  
   876  	// Check to see if we need byte swap before storing.
   877  	needSwap := isLittleEndian && root.Block.Func.Config.BigEndian ||
   878  		isBigEndian && !root.Block.Func.Config.BigEndian
   879  	if needSwap && (int64(len(a)) != aTotalSize || !root.Block.Func.Config.HaveByteSwap(aTotalSize)) {
   880  		return
   881  	}
   882  
   883  	// This is the commit point.
   884  
   885  	// Modify root to do all the stores.
   886  	sv := shiftBase
   887  	if isLittleEndian && shift0 != 0 {
   888  		sv = rightShift(root.Block, root.Pos, sv, shift0)
   889  	}
   890  	shiftedSize = aTotalSize - a[0].size
   891  	if isBigEndian && shift0-shiftedSize*8 != 0 {
   892  		sv = rightShift(root.Block, root.Pos, sv, shift0-shiftedSize*8)
   893  	}
   894  	if sv.Type.Size() > aTotalSize {
   895  		sv = truncate(root.Block, root.Pos, sv, sv.Type.Size(), aTotalSize)
   896  	}
   897  	if needSwap {
   898  		sv = byteSwap(root.Block, root.Pos, sv)
   899  	}
   900  
   901  	// Move all the stores to the root.
   902  	for i := range a {
   903  		v := a[i].store
   904  		if v == root {
   905  			v.Aux = sv.Type // widen store type
   906  			v.Pos = pos
   907  			v.SetArg(0, ptr)
   908  			v.SetArg(1, sv)
   909  			v.SetArg(2, mem)
   910  		} else {
   911  			ssa.Clobber(v)
   912  			v.Type = types.Types[types.TBOOL] // erase memory type
   913  		}
   914  	}
   915  }
   916  
   917  func sizeType(size int64) *types.Type {
   918  	switch size {
   919  	case 8:
   920  		return types.Types[types.TUINT64]
   921  	case 4:
   922  		return types.Types[types.TUINT32]
   923  	case 2:
   924  		return types.Types[types.TUINT16]
   925  	default:
   926  		base.Fatalf("bad size %d\n", size)
   927  		return nil
   928  	}
   929  }
   930  
   931  func truncate(b *ssa.Block, pos src.XPos, v *ssa.Value, from, to int64) *ssa.Value {
   932  	switch from*10 + to {
   933  	case 82:
   934  		return b.NewValue1(pos, ssaop.OpTrunc64to16, types.Types[types.TUINT16], v)
   935  	case 84:
   936  		return b.NewValue1(pos, ssaop.OpTrunc64to32, types.Types[types.TUINT32], v)
   937  	case 42:
   938  		return b.NewValue1(pos, ssaop.OpTrunc32to16, types.Types[types.TUINT16], v)
   939  	default:
   940  		base.Fatalf("bad sizes %d %d\n", from, to)
   941  		return nil
   942  	}
   943  }
   944  func zeroExtend(b *ssa.Block, pos src.XPos, v *ssa.Value, from, to int64) *ssa.Value {
   945  	switch from*10 + to {
   946  	case 24:
   947  		return b.NewValue1(pos, ssaop.OpZeroExt16to32, types.Types[types.TUINT32], v)
   948  	case 28:
   949  		return b.NewValue1(pos, ssaop.OpZeroExt16to64, types.Types[types.TUINT64], v)
   950  	case 48:
   951  		return b.NewValue1(pos, ssaop.OpZeroExt32to64, types.Types[types.TUINT64], v)
   952  	default:
   953  		base.Fatalf("bad sizes %d %d\n", from, to)
   954  		return nil
   955  	}
   956  }
   957  
   958  func leftShift(b *ssa.Block, pos src.XPos, v *ssa.Value, shift int64) *ssa.Value {
   959  	s := b.Func.ConstInt64(types.Types[types.TUINT64], shift)
   960  	size := v.Type.Size()
   961  	switch size {
   962  	case 8:
   963  		return b.NewValue2(pos, ssaop.OpLsh64x64, v.Type, v, s)
   964  	case 4:
   965  		return b.NewValue2(pos, ssaop.OpLsh32x64, v.Type, v, s)
   966  	case 2:
   967  		return b.NewValue2(pos, ssaop.OpLsh16x64, v.Type, v, s)
   968  	default:
   969  		base.Fatalf("bad size %d\n", size)
   970  		return nil
   971  	}
   972  }
   973  func rightShift(b *ssa.Block, pos src.XPos, v *ssa.Value, shift int64) *ssa.Value {
   974  	s := b.Func.ConstInt64(types.Types[types.TUINT64], shift)
   975  	size := v.Type.Size()
   976  	switch size {
   977  	case 8:
   978  		return b.NewValue2(pos, ssaop.OpRsh64Ux64, v.Type, v, s)
   979  	case 4:
   980  		return b.NewValue2(pos, ssaop.OpRsh32Ux64, v.Type, v, s)
   981  	case 2:
   982  		return b.NewValue2(pos, ssaop.OpRsh16Ux64, v.Type, v, s)
   983  	default:
   984  		base.Fatalf("bad size %d\n", size)
   985  		return nil
   986  	}
   987  }
   988  func byteSwap(b *ssa.Block, pos src.XPos, v *ssa.Value) *ssa.Value {
   989  	switch v.Type.Size() {
   990  	case 8:
   991  		return b.NewValue1(pos, ssaop.OpBswap64, v.Type, v)
   992  	case 4:
   993  		return b.NewValue1(pos, ssaop.OpBswap32, v.Type, v)
   994  	case 2:
   995  		return b.NewValue1(pos, ssaop.OpBswap16, v.Type, v)
   996  
   997  	default:
   998  		v.Fatalf("bad size %d\n", v.Type.Size())
   999  		return nil
  1000  	}
  1001  }
  1002
View as plain text