pair.go

     1  // Copyright 2016 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  	"slices"
     9  
    10  	"cmd/compile/internal/ir"
    11  	"cmd/compile/internal/ssa"
    12  	"cmd/compile/internal/ssa/block"
    13  	"cmd/compile/internal/ssa/ssaop"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/obj"
    16  )
    17  
    18  // The pair pass finds memory operations that can be paired up
    19  // into single 2-register memory instructions.
    20  func pair(f *ssa.Func) {
    21  	// Only arm64 for now. This pass is fairly arch-specific.
    22  	switch f.Config.Arch {
    23  	case "arm64":
    24  	default:
    25  		return
    26  	}
    27  	pairLoads(f)
    28  	pairStores(f)
    29  }
    30  
    31  type pairInfo struct {
    32  	width int64 // width of one element in the pair, in bytes
    33  	pair  ssaop.Op
    34  }
    35  
    36  // All pairableLoad ops must take 2 arguments, a pointer and a memory.
    37  // They must also take an offset in Aux/AuxInt.
    38  var pairableLoads = map[ssaop.Op]pairInfo{
    39  	ssaop.OpARM64MOVDload:  {8, ssaop.OpARM64LDP},
    40  	ssaop.OpARM64MOVWUload: {4, ssaop.OpARM64LDPW},
    41  	ssaop.OpARM64MOVWload:  {4, ssaop.OpARM64LDPSW},
    42  	// TODO: conceivably we could pair a signed and unsigned load
    43  	// if we knew the upper bits of one of them weren't being used.
    44  	ssaop.OpARM64FMOVDload: {8, ssaop.OpARM64FLDPD},
    45  	ssaop.OpARM64FMOVSload: {4, ssaop.OpARM64FLDPS},
    46  	// NEON loads
    47  	ssaop.OpARM64FMOVQload: {16, ssaop.OpARM64FLDPQ},
    48  }
    49  
    50  // All pairableStore keys must take 3 arguments, a pointer, a value, and a memory.
    51  // All pairableStore values must take 4 arguments, a pointer, 2 values, and a memory.
    52  // They must also take an offset in Aux/AuxInt.
    53  var pairableStores = map[ssaop.Op]pairInfo{
    54  	ssaop.OpARM64MOVDstore:  {8, ssaop.OpARM64STP},
    55  	ssaop.OpARM64MOVWstore:  {4, ssaop.OpARM64STPW},
    56  	ssaop.OpARM64FMOVDstore: {8, ssaop.OpARM64FSTPD},
    57  	ssaop.OpARM64FMOVSstore: {4, ssaop.OpARM64FSTPS},
    58  	// NEON stores
    59  	ssaop.OpARM64FMOVQstore: {16, ssaop.OpARM64FSTPQ},
    60  }
    61  
    62  // offsetOk returns true if a pair instruction should be used
    63  // for the offset Aux+off, when the data width (of the
    64  // unpaired instructions) is width.
    65  // This function is best-effort. The compiled function must
    66  // still work if offsetOk always returns true.
    67  // TODO: this is currently arm64-specific.
    68  func offsetOk(aux ssa.Aux, off, width int64) bool {
    69  	if true {
    70  		// Seems to generate slightly smaller code if we just
    71  		// always allow this rewrite.
    72  		//
    73  		// Without pairing, we have 2 load instructions, like:
    74  		//   LDR 88(R0), R1
    75  		//   LDR 96(R0), R2
    76  		// with pairing we have, best case:
    77  		//   LDP 88(R0), R1, R2
    78  		// but maybe we need an adjuster if out of range or unaligned:
    79  		//   ADD R0, $88, R27
    80  		//   LDP (R27), R1, R2
    81  		// Even with the adjuster, it is at least no worse.
    82  		//
    83  		// A similar situation occurs when accessing globals.
    84  		// Two loads from globals requires 4 instructions,
    85  		// two ADRP and two LDR. With pairing, we need
    86  		// ADRP+ADD+LDP, three instructions.
    87  		//
    88  		// With pairing, it looks like the critical path might
    89  		// be a little bit longer. But it should never be more
    90  		// instructions.
    91  		// TODO: see if that longer critical path causes any
    92  		// regressions.
    93  		return true
    94  	}
    95  	if aux != nil {
    96  		if _, ok := aux.(*ir.Name); !ok {
    97  			// Offset is probably too big (globals).
    98  			return false
    99  		}
   100  		// We let *ir.Names pass here, as
   101  		// they are probably small offsets from SP.
   102  		// There's no guarantee that we're in range
   103  		// in that case though (we don't know the
   104  		// stack frame size yet), so the assembler
   105  		// might need to issue fixup instructions.
   106  		// Assume some small frame size.
   107  		if off >= 0 {
   108  			off += 128 // This should be multiple of 4, 8 and 16 for later off%width check
   109  		}
   110  		// TODO: figure out how often this helps vs. hurts.
   111  	}
   112  	switch width {
   113  	case 4, 8, 16:
   114  		// Offset is encoded as signed 7 bit imm * width
   115  		const simm7Min = -64
   116  		const simm7Max = 63
   117  
   118  		if off >= simm7Min*width && off <= simm7Max*width && off%width == 0 {
   119  			return true
   120  		}
   121  	}
   122  	return false
   123  }
   124  
   125  func pairLoads(f *ssa.Func) {
   126  	var loads []*ssa.Value
   127  
   128  	// Registry of aux values for sorting.
   129  	auxIDs := map[ssa.Aux]int{}
   130  	auxID := func(aux ssa.Aux) int {
   131  		id, ok := auxIDs[aux]
   132  		if !ok {
   133  			id = len(auxIDs)
   134  			auxIDs[aux] = id
   135  		}
   136  		return id
   137  	}
   138  
   139  	for _, b := range f.Blocks {
   140  		// Find loads.
   141  		loads = loads[:0]
   142  		clear(auxIDs)
   143  		for _, v := range b.Values {
   144  			info := pairableLoads[v.Op]
   145  			if info.width == 0 {
   146  				continue // not pairable
   147  			}
   148  			if !offsetOk(v.Aux, v.AuxInt, info.width) {
   149  				continue // not advisable
   150  			}
   151  			loads = append(loads, v)
   152  		}
   153  		if len(loads) < 2 {
   154  			continue
   155  		}
   156  
   157  		// Sort to put pairable loads together.
   158  		slices.SortFunc(loads, func(x, y *ssa.Value) int {
   159  			// First sort by op, ptr, and memory arg.
   160  			if x.Op != y.Op {
   161  				return int(x.Op - y.Op)
   162  			}
   163  			if x.Args[0].ID != y.Args[0].ID {
   164  				return int(x.Args[0].ID - y.Args[0].ID)
   165  			}
   166  			if x.Args[1].ID != y.Args[1].ID {
   167  				return int(x.Args[1].ID - y.Args[1].ID)
   168  			}
   169  			// Then sort by aux. (nil first, then by aux ID)
   170  			if x.Aux != nil {
   171  				if y.Aux == nil {
   172  					return 1
   173  				}
   174  				a, b := auxID(x.Aux), auxID(y.Aux)
   175  				if a != b {
   176  					return a - b
   177  				}
   178  			} else if y.Aux != nil {
   179  				return -1
   180  			}
   181  			// Then sort by offset, low to high.
   182  			return int(x.AuxInt - y.AuxInt)
   183  		})
   184  
   185  		// Look for pairable loads.
   186  		for i := 0; i < len(loads)-1; i++ {
   187  			x := loads[i]
   188  			y := loads[i+1]
   189  			if x.Op != y.Op || x.Args[0] != y.Args[0] || x.Args[1] != y.Args[1] {
   190  				continue
   191  			}
   192  			if x.Aux != y.Aux {
   193  				continue
   194  			}
   195  			if x.AuxInt+pairableLoads[x.Op].width != y.AuxInt {
   196  				continue
   197  			}
   198  
   199  			// Commit point.
   200  
   201  			// Make the 2-register load.
   202  			load := b.NewValue2IA(x.Pos, pairableLoads[x.Op].pair, types.NewTuple(x.Type, y.Type), x.AuxInt, x.Aux, x.Args[0], x.Args[1])
   203  
   204  			// Modify x to be (Select0 load). Similar for y.
   205  			x.Reset(ssaop.OpSelect0)
   206  			x.SetArgs1(load)
   207  			y.Reset(ssaop.OpSelect1)
   208  			y.SetArgs1(load)
   209  
   210  			i++ // Skip y next time around the loop.
   211  		}
   212  	}
   213  
   214  	// Try to pair a load with a load from a subsequent block.
   215  	// Note that this is always safe to do if the memory arguments match.
   216  	// (But see the memory barrier case below.)
   217  	type nextBlockKey struct {
   218  		op     ssaop.Op
   219  		ptr    ssa.ID
   220  		mem    ssa.ID
   221  		auxInt int64
   222  		aux    any
   223  	}
   224  	nextBlock := map[nextBlockKey]*ssa.Value{}
   225  	for _, b := range f.Blocks {
   226  		if memoryBarrierTest(b) {
   227  			// TODO: Do we really need to skip write barrier test blocks?
   228  			//     type T struct {
   229  			//         a *byte
   230  			//         b int
   231  			//     }
   232  			//     func f(t *T) int {
   233  			//         r := t.b
   234  			//         t.a = nil
   235  			//         return r
   236  			//     }
   237  			// This would issue a single LDP for both the t.a and t.b fields,
   238  			// *before* we check the write barrier flag. (We load the t.a field
   239  			// to put it in the write barrier buffer.) Not sure if that is ok.
   240  			continue
   241  		}
   242  		// Find loads in the next block(s) that we can move to this one.
   243  		// TODO: could maybe look further than just one successor hop.
   244  		clear(nextBlock)
   245  		for _, e := range b.Succs {
   246  			if len(e.B.Preds) > 1 {
   247  				continue
   248  			}
   249  			for _, v := range e.B.Values {
   250  				info := pairableLoads[v.Op]
   251  				if info.width == 0 {
   252  					continue
   253  				}
   254  				if !offsetOk(v.Aux, v.AuxInt, info.width) {
   255  					continue // not advisable
   256  				}
   257  				nextBlock[nextBlockKey{op: v.Op, ptr: v.Args[0].ID, mem: v.Args[1].ID, auxInt: v.AuxInt, aux: v.Aux}] = v
   258  			}
   259  		}
   260  		if len(nextBlock) == 0 {
   261  			continue
   262  		}
   263  		// don't move too many loads. Each requires a register across a basic block boundary.
   264  		const maxMoved = 4
   265  		nMoved := 0
   266  		for i := len(b.Values) - 1; i >= 0 && nMoved < maxMoved; i-- {
   267  			x := b.Values[i]
   268  			info := pairableLoads[x.Op]
   269  			if info.width == 0 {
   270  				continue
   271  			}
   272  			if !offsetOk(x.Aux, x.AuxInt, info.width) {
   273  				continue // not advisable
   274  			}
   275  			key := nextBlockKey{op: x.Op, ptr: x.Args[0].ID, mem: x.Args[1].ID, auxInt: x.AuxInt + info.width, aux: x.Aux}
   276  			if y := nextBlock[key]; y != nil {
   277  				delete(nextBlock, key)
   278  
   279  				// Make the 2-register load.
   280  				load := b.NewValue2IA(x.Pos, info.pair, types.NewTuple(x.Type, y.Type), x.AuxInt, x.Aux, x.Args[0], x.Args[1])
   281  
   282  				// Modify x to be (Select0 load).
   283  				x.Reset(ssaop.OpSelect0)
   284  				x.SetArgs1(load)
   285  				// Modify y to be (Copy (Select1 load)).
   286  				// Note: the Select* needs to live in the load's block, not y's block.
   287  				y.Reset(ssaop.OpCopy)
   288  				y.SetArgs1(b.NewValue1(y.Pos, ssaop.OpSelect1, y.Type, load))
   289  				nMoved++
   290  				continue
   291  			}
   292  			key.auxInt = x.AuxInt - info.width
   293  			if y := nextBlock[key]; y != nil {
   294  				delete(nextBlock, key)
   295  
   296  				// Make the 2-register load.
   297  				load := b.NewValue2IA(x.Pos, info.pair, types.NewTuple(y.Type, x.Type), y.AuxInt, x.Aux, x.Args[0], x.Args[1])
   298  
   299  				// Modify x to be (Select1 load).
   300  				x.Reset(ssaop.OpSelect1)
   301  				x.SetArgs1(load)
   302  				// Modify y to be (Copy (Select0 load)).
   303  				y.Reset(ssaop.OpCopy)
   304  				y.SetArgs1(b.NewValue1(y.Pos, ssaop.OpSelect0, y.Type, load))
   305  				nMoved++
   306  				continue
   307  			}
   308  		}
   309  	}
   310  }
   311  
   312  func memoryBarrierTest(b *ssa.Block) bool {
   313  	if b.Kind != block.BlockARM64NZW {
   314  		return false
   315  	}
   316  	c := b.Controls[0]
   317  	if c.Op != ssaop.OpARM64MOVWUload {
   318  		return false
   319  	}
   320  	if globl, ok := c.Aux.(*obj.LSym); ok {
   321  		return globl.Name == "runtime.writeBarrier"
   322  	}
   323  	return false
   324  }
   325  
   326  // pairStores merges store instructions.
   327  // It collects stores into a buffer where they can be freely reordered.
   328  // When encountering an instruction that cannot be added to the buffer,
   329  // it pairs the accumulated stores, flushes the buffer, and continues processing.
   330  func pairStores(f *ssa.Func) {
   331  	last := f.Cache.AllocBoolSlice(f.NumValues())
   332  	defer f.Cache.FreeBoolSlice(last)
   333  
   334  	// memChain contains a list of stores with the same ptr/aux pair and
   335  	// nonoverlapping write ranges [AuxInt:AuxInt+writeSize]. All of the
   336  	// elements of memChain can be reordered with each other.
   337  	memChain := []*ssa.Value{}
   338  
   339  	// Limit of length of memChain array.
   340  	// This keeps us in O(n) territory.
   341  	limit := 100
   342  
   343  	// flushMemChain sorts the stores in memChain and merges them when possible.
   344  	// Then it flushes memChain.
   345  	flushMemChain := func() {
   346  		if len(memChain) < 2 {
   347  			memChain = memChain[:0]
   348  			return
   349  		}
   350  
   351  		// Sort in increasing AuxInt to put pairable stores together.
   352  		slices.SortFunc(memChain, func(x, y *ssa.Value) int {
   353  			return int(x.AuxInt - y.AuxInt)
   354  		})
   355  
   356  		lastIdx := len(memChain) - 1
   357  		for i := 0; i < lastIdx; i++ {
   358  			v := memChain[i]
   359  			w := memChain[i+1]
   360  			info := pairableStores[v.Op]
   361  
   362  			off := v.AuxInt
   363  			mem := v.MemoryArg()
   364  			aux := v.Aux
   365  			pos := v.Pos
   366  			wmem := w.MemoryArg()
   367  
   368  			if w.Op == v.Op && w.AuxInt == off+info.width {
   369  				// Arguments for the merged store: ptr, val1, val2, mem.
   370  				args := []*ssa.Value{v.Args[0], v.Args[1], w.Args[1], mem}
   371  
   372  				v.Reset(info.pair)
   373  				v.AddArgs(args...)
   374  				v.Aux = aux
   375  				v.AuxInt = off
   376  				v.Pos = pos
   377  
   378  				// Make w just a memory copy.
   379  				w.Reset(ssaop.OpCopy)
   380  				w.SetArgs1(wmem)
   381  
   382  				// Skip merged store (w)
   383  				i++
   384  			}
   385  		}
   386  
   387  		memChain = memChain[:0]
   388  	}
   389  
   390  	// prevStore returns the previous store in the
   391  	// same block, or nil if there are none.
   392  	prevStore := func(v *ssa.Value) *ssa.Value {
   393  		if v.Op == ssaop.OpInitMem || v.Op == ssaop.OpPhi {
   394  			return nil
   395  		}
   396  		m := v.MemoryArg()
   397  		if m.Block != v.Block {
   398  			return nil
   399  		}
   400  		return m
   401  	}
   402  
   403  	// storeWidth returns the width of store,
   404  	// or 0 if it is not a store this pass understands.
   405  	storeWidth := func(op ssaop.Op) int64 {
   406  		if info, ok := pairableStores[op]; ok {
   407  			return info.width
   408  		}
   409  
   410  		// We don't pair these stores, but returning zero here
   411  		// would flush the memory chain.
   412  		var width int64
   413  		switch op {
   414  		case ssaop.OpARM64MOVHstore:
   415  			width = 2
   416  		case ssaop.OpARM64MOVBstore:
   417  			width = 1
   418  		default:
   419  			width = 0
   420  		}
   421  
   422  		return width
   423  	}
   424  
   425  	for _, b := range f.Blocks {
   426  		memChain = memChain[:0]
   427  
   428  		// Find last store in block, so we can
   429  		// walk the stores last to first.
   430  		// Last to first helps ensure that the rewrites we
   431  		// perform do not get in the way of subsequent rewrites.
   432  		for _, v := range b.Values {
   433  			if v.Type.IsMemory() {
   434  				last[v.ID] = true
   435  			}
   436  		}
   437  		for _, v := range b.Values {
   438  			if v.Type.IsMemory() {
   439  				if m := prevStore(v); m != nil {
   440  					last[m.ID] = false
   441  				}
   442  			}
   443  		}
   444  		var lastMem *ssa.Value
   445  		for _, v := range b.Values {
   446  			if last[v.ID] {
   447  				lastMem = v
   448  				break
   449  			}
   450  		}
   451  
   452  		// Iterate over memory stores, accumulating them in memChain for potential merging.
   453  		// Flush the chain when reordering is unsafe or a conflict is detected.
   454  		for v := lastMem; v != nil; v = prevStore(v) {
   455  			writeSize := storeWidth(v.Op)
   456  
   457  			if writeSize == 0 {
   458  				// We can't reorder stores with calls or other instructions
   459  				// with writeSize == 0.
   460  				flushMemChain()
   461  				continue
   462  			}
   463  			if v.Uses != 1 && len(memChain) > 0 ||
   464  				len(memChain) > 0 && (v.Args[0] != memChain[0].Args[0] || v.Aux != memChain[0].Aux) ||
   465  				len(memChain) == limit {
   466  				// 1. If v has multiple uses and it is not the latest store in the chain,
   467  				// we cannot merge it with other store instructions.
   468  				//
   469  				// 2. If v has a different base pointer or Aux value from the current chain,
   470  				// we need to flush memChain and start a new one with v.
   471  				//
   472  				// 3. If memChain length limit is exceeded, we also need to flush the chain
   473  				// and start a new one with v.
   474  				//
   475  				// Only look back so far.
   476  				// This keeps us in O(n) territory, and it
   477  				// also prevents us from keeping values
   478  				// in registers for too long (and thus
   479  				// needing to spill them).
   480  				flushMemChain()
   481  			}
   482  
   483  			for _, w := range memChain {
   484  				wWriteSize := storeWidth(w.Op)
   485  				if ssa.Overlap(w.AuxInt, wWriteSize, v.AuxInt, writeSize) {
   486  					// Aliases with w's location.
   487  					// Flush the chain and start a new one with v.
   488  					flushMemChain()
   489  					break
   490  				}
   491  			}
   492  
   493  			memChain = append(memChain, v)
   494  		}
   495  		flushMemChain()
   496  	}
   497  }
   498
View as plain text