Source file src/cmd/compile/internal/ssa/writebarrier.go

Documentation: cmd/compile/internal/ssa

     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 ssa
     6  
     7  import (
     8  	"cmd/compile/internal/types"
     9  	"cmd/internal/obj"
    10  	"cmd/internal/src"
    11  	"strings"
    12  )
    13  
    14  // A ZeroRegion records a range of an object which is known to be zero.
    15  // A ZeroRegion only applies to a single memory state.
    16  type ZeroRegion struct {
    17  	base *Value
    18  	min  int64
    19  	max  int64
    20  }
    21  
    22  // needwb reports whether we need write barrier for store op v.
    23  // v must be Store/Move/Zero.
    24  // zeroes provides known zero information (keyed by ID of memory-type values).
    25  func needwb(v *Value, zeroes map[ID]ZeroRegion) bool {
    26  	t, ok := v.Aux.(*types.Type)
    27  	if !ok {
    28  		v.Fatalf("store aux is not a type: %s", v.LongString())
    29  	}
    30  	if !t.HasHeapPointer() {
    31  		return false
    32  	}
    33  	if IsStackAddr(v.Args[0]) {
    34  		return false // write on stack doesn't need write barrier
    35  	}
    36  	if v.Op == OpMove && IsReadOnlyGlobalAddr(v.Args[1]) && IsNewObject(v.Args[0], v.MemoryArg()) {
    37  		// Copying data from readonly memory into a fresh object doesn't need a write barrier.
    38  		return false
    39  	}
    40  	if v.Op == OpStore && IsGlobalAddr(v.Args[1]) {
    41  		// Storing pointers to non-heap locations into zeroed memory doesn't need a write barrier.
    42  		ptr := v.Args[0]
    43  		var off int64
    44  		size := v.Aux.(*types.Type).Size()
    45  		for ptr.Op == OpOffPtr {
    46  			off += ptr.AuxInt
    47  			ptr = ptr.Args[0]
    48  		}
    49  		z := zeroes[v.MemoryArg().ID]
    50  		if ptr == z.base && off >= z.min && off+size <= z.max {
    51  			return false
    52  		}
    53  	}
    54  	return true
    55  }
    56  
    57  // writebarrier pass inserts write barriers for store ops (Store, Move, Zero)
    58  // when necessary (the condition above). It rewrites store ops to branches
    59  // and runtime calls, like
    60  //
    61  // if writeBarrier.enabled {
    62  //   gcWriteBarrier(ptr, val)	// Not a regular Go call
    63  // } else {
    64  //   *ptr = val
    65  // }
    66  //
    67  // A sequence of WB stores for many pointer fields of a single type will
    68  // be emitted together, with a single branch.
    69  func writebarrier(f *Func) {
    70  	if !f.fe.UseWriteBarrier() {
    71  		return
    72  	}
    73  
    74  	var sb, sp, wbaddr, const0 *Value
    75  	var typedmemmove, typedmemclr, gcWriteBarrier *obj.LSym
    76  	var stores, after []*Value
    77  	var sset *sparseSet
    78  	var storeNumber []int32
    79  
    80  	zeroes := f.computeZeroMap()
    81  	for _, b := range f.Blocks { // range loop is safe since the blocks we added contain no stores to expand
    82  		// first, identify all the stores that need to insert a write barrier.
    83  		// mark them with WB ops temporarily. record presence of WB ops.
    84  		nWBops := 0 // count of temporarily created WB ops remaining to be rewritten in the current block
    85  		for _, v := range b.Values {
    86  			switch v.Op {
    87  			case OpStore, OpMove, OpZero:
    88  				if needwb(v, zeroes) {
    89  					switch v.Op {
    90  					case OpStore:
    91  						v.Op = OpStoreWB
    92  					case OpMove:
    93  						v.Op = OpMoveWB
    94  					case OpZero:
    95  						v.Op = OpZeroWB
    96  					}
    97  					nWBops++
    98  				}
    99  			}
   100  		}
   101  		if nWBops == 0 {
   102  			continue
   103  		}
   104  
   105  		if wbaddr == nil {
   106  			// lazily initialize global values for write barrier test and calls
   107  			// find SB and SP values in entry block
   108  			initpos := f.Entry.Pos
   109  			for _, v := range f.Entry.Values {
   110  				if v.Op == OpSB {
   111  					sb = v
   112  				}
   113  				if v.Op == OpSP {
   114  					sp = v
   115  				}
   116  				if sb != nil && sp != nil {
   117  					break
   118  				}
   119  			}
   120  			if sb == nil {
   121  				sb = f.Entry.NewValue0(initpos, OpSB, f.Config.Types.Uintptr)
   122  			}
   123  			if sp == nil {
   124  				sp = f.Entry.NewValue0(initpos, OpSP, f.Config.Types.Uintptr)
   125  			}
   126  			wbsym := f.fe.Syslook("writeBarrier")
   127  			wbaddr = f.Entry.NewValue1A(initpos, OpAddr, f.Config.Types.UInt32Ptr, wbsym, sb)
   128  			gcWriteBarrier = f.fe.Syslook("gcWriteBarrier")
   129  			typedmemmove = f.fe.Syslook("typedmemmove")
   130  			typedmemclr = f.fe.Syslook("typedmemclr")
   131  			const0 = f.ConstInt32(f.Config.Types.UInt32, 0)
   132  
   133  			// allocate auxiliary data structures for computing store order
   134  			sset = f.newSparseSet(f.NumValues())
   135  			defer f.retSparseSet(sset)
   136  			storeNumber = make([]int32, f.NumValues())
   137  		}
   138  
   139  		// order values in store order
   140  		b.Values = storeOrder(b.Values, sset, storeNumber)
   141  
   142  		firstSplit := true
   143  	again:
   144  		// find the start and end of the last contiguous WB store sequence.
   145  		// a branch will be inserted there. values after it will be moved
   146  		// to a new block.
   147  		var last *Value
   148  		var start, end int
   149  		values := b.Values
   150  	FindSeq:
   151  		for i := len(values) - 1; i >= 0; i-- {
   152  			w := values[i]
   153  			switch w.Op {
   154  			case OpStoreWB, OpMoveWB, OpZeroWB:
   155  				start = i
   156  				if last == nil {
   157  					last = w
   158  					end = i + 1
   159  				}
   160  			case OpVarDef, OpVarLive, OpVarKill:
   161  				continue
   162  			default:
   163  				if last == nil {
   164  					continue
   165  				}
   166  				break FindSeq
   167  			}
   168  		}
   169  		stores = append(stores[:0], b.Values[start:end]...) // copy to avoid aliasing
   170  		after = append(after[:0], b.Values[end:]...)
   171  		b.Values = b.Values[:start]
   172  
   173  		// find the memory before the WB stores
   174  		mem := stores[0].MemoryArg()
   175  		pos := stores[0].Pos
   176  		bThen := f.NewBlock(BlockPlain)
   177  		bElse := f.NewBlock(BlockPlain)
   178  		bEnd := f.NewBlock(b.Kind)
   179  		bThen.Pos = pos
   180  		bElse.Pos = pos
   181  		bEnd.Pos = b.Pos
   182  		b.Pos = pos
   183  
   184  		// set up control flow for end block
   185  		bEnd.SetControl(b.Control)
   186  		bEnd.Likely = b.Likely
   187  		for _, e := range b.Succs {
   188  			bEnd.Succs = append(bEnd.Succs, e)
   189  			e.b.Preds[e.i].b = bEnd
   190  		}
   191  
   192  		// set up control flow for write barrier test
   193  		// load word, test word, avoiding partial register write from load byte.
   194  		cfgtypes := &f.Config.Types
   195  		flag := b.NewValue2(pos, OpLoad, cfgtypes.UInt32, wbaddr, mem)
   196  		flag = b.NewValue2(pos, OpNeq32, cfgtypes.Bool, flag, const0)
   197  		b.Kind = BlockIf
   198  		b.SetControl(flag)
   199  		b.Likely = BranchUnlikely
   200  		b.Succs = b.Succs[:0]
   201  		b.AddEdgeTo(bThen)
   202  		b.AddEdgeTo(bElse)
   203  		// TODO: For OpStoreWB and the buffered write barrier,
   204  		// we could move the write out of the write barrier,
   205  		// which would lead to fewer branches. We could do
   206  		// something similar to OpZeroWB, since the runtime
   207  		// could provide just the barrier half and then we
   208  		// could unconditionally do an OpZero (which could
   209  		// also generate better zeroing code). OpMoveWB is
   210  		// trickier and would require changing how
   211  		// cgoCheckMemmove works.
   212  		bThen.AddEdgeTo(bEnd)
   213  		bElse.AddEdgeTo(bEnd)
   214  
   215  		// for each write barrier store, append write barrier version to bThen
   216  		// and simple store version to bElse
   217  		memThen := mem
   218  		memElse := mem
   219  
   220  		// If the source of a MoveWB is volatile (will be clobbered by a
   221  		// function call), we need to copy it to a temporary location, as
   222  		// marshaling the args of typedmemmove might clobber the value we're
   223  		// trying to move.
   224  		// Look for volatile source, copy it to temporary before we emit any
   225  		// call.
   226  		// It is unlikely to have more than one of them. Just do a linear
   227  		// search instead of using a map.
   228  		type volatileCopy struct {
   229  			src *Value // address of original volatile value
   230  			tmp *Value // address of temporary we've copied the volatile value into
   231  		}
   232  		var volatiles []volatileCopy
   233  	copyLoop:
   234  		for _, w := range stores {
   235  			if w.Op == OpMoveWB {
   236  				val := w.Args[1]
   237  				if isVolatile(val) {
   238  					for _, c := range volatiles {
   239  						if val == c.src {
   240  							continue copyLoop // already copied
   241  						}
   242  					}
   243  
   244  					t := val.Type.Elem()
   245  					tmp := f.fe.Auto(w.Pos, t)
   246  					memThen = bThen.NewValue1A(w.Pos, OpVarDef, types.TypeMem, tmp, memThen)
   247  					tmpaddr := bThen.NewValue2A(w.Pos, OpLocalAddr, t.PtrTo(), tmp, sp, memThen)
   248  					siz := t.Size()
   249  					memThen = bThen.NewValue3I(w.Pos, OpMove, types.TypeMem, siz, tmpaddr, val, memThen)
   250  					memThen.Aux = t
   251  					volatiles = append(volatiles, volatileCopy{val, tmpaddr})
   252  				}
   253  			}
   254  		}
   255  
   256  		for _, w := range stores {
   257  			ptr := w.Args[0]
   258  			pos := w.Pos
   259  
   260  			var fn *obj.LSym
   261  			var typ *obj.LSym
   262  			var val *Value
   263  			switch w.Op {
   264  			case OpStoreWB:
   265  				val = w.Args[1]
   266  				nWBops--
   267  			case OpMoveWB:
   268  				fn = typedmemmove
   269  				val = w.Args[1]
   270  				typ = w.Aux.(*types.Type).Symbol()
   271  				nWBops--
   272  			case OpZeroWB:
   273  				fn = typedmemclr
   274  				typ = w.Aux.(*types.Type).Symbol()
   275  				nWBops--
   276  			case OpVarDef, OpVarLive, OpVarKill:
   277  			}
   278  
   279  			// then block: emit write barrier call
   280  			switch w.Op {
   281  			case OpStoreWB, OpMoveWB, OpZeroWB:
   282  				if w.Op == OpStoreWB {
   283  					memThen = bThen.NewValue3A(pos, OpWB, types.TypeMem, gcWriteBarrier, ptr, val, memThen)
   284  				} else {
   285  					srcval := val
   286  					if w.Op == OpMoveWB && isVolatile(srcval) {
   287  						for _, c := range volatiles {
   288  							if srcval == c.src {
   289  								srcval = c.tmp
   290  								break
   291  							}
   292  						}
   293  					}
   294  					memThen = wbcall(pos, bThen, fn, typ, ptr, srcval, memThen, sp, sb)
   295  				}
   296  				// Note that we set up a writebarrier function call.
   297  				f.fe.SetWBPos(pos)
   298  			case OpVarDef, OpVarLive, OpVarKill:
   299  				memThen = bThen.NewValue1A(pos, w.Op, types.TypeMem, w.Aux, memThen)
   300  			}
   301  
   302  			// else block: normal store
   303  			switch w.Op {
   304  			case OpStoreWB:
   305  				memElse = bElse.NewValue3A(pos, OpStore, types.TypeMem, w.Aux, ptr, val, memElse)
   306  			case OpMoveWB:
   307  				memElse = bElse.NewValue3I(pos, OpMove, types.TypeMem, w.AuxInt, ptr, val, memElse)
   308  				memElse.Aux = w.Aux
   309  			case OpZeroWB:
   310  				memElse = bElse.NewValue2I(pos, OpZero, types.TypeMem, w.AuxInt, ptr, memElse)
   311  				memElse.Aux = w.Aux
   312  			case OpVarDef, OpVarLive, OpVarKill:
   313  				memElse = bElse.NewValue1A(pos, w.Op, types.TypeMem, w.Aux, memElse)
   314  			}
   315  		}
   316  
   317  		// mark volatile temps dead
   318  		for _, c := range volatiles {
   319  			tmpNode := c.tmp.Aux
   320  			memThen = bThen.NewValue1A(memThen.Pos, OpVarKill, types.TypeMem, tmpNode, memThen)
   321  		}
   322  
   323  		// merge memory
   324  		// Splice memory Phi into the last memory of the original sequence,
   325  		// which may be used in subsequent blocks. Other memories in the
   326  		// sequence must be dead after this block since there can be only
   327  		// one memory live.
   328  		bEnd.Values = append(bEnd.Values, last)
   329  		last.Block = bEnd
   330  		last.reset(OpPhi)
   331  		last.Type = types.TypeMem
   332  		last.AddArg(memThen)
   333  		last.AddArg(memElse)
   334  		for _, w := range stores {
   335  			if w != last {
   336  				w.resetArgs()
   337  			}
   338  		}
   339  		for _, w := range stores {
   340  			if w != last {
   341  				f.freeValue(w)
   342  			}
   343  		}
   344  
   345  		// put values after the store sequence into the end block
   346  		bEnd.Values = append(bEnd.Values, after...)
   347  		for _, w := range after {
   348  			w.Block = bEnd
   349  		}
   350  
   351  		// Preemption is unsafe between loading the write
   352  		// barrier-enabled flag and performing the write
   353  		// because that would allow a GC phase transition,
   354  		// which would invalidate the flag. Remember the
   355  		// conditional block so liveness analysis can disable
   356  		// safe-points. This is somewhat subtle because we're
   357  		// splitting b bottom-up.
   358  		if firstSplit {
   359  			// Add b itself.
   360  			b.Func.WBLoads = append(b.Func.WBLoads, b)
   361  			firstSplit = false
   362  		} else {
   363  			// We've already split b, so we just pushed a
   364  			// write barrier test into bEnd.
   365  			b.Func.WBLoads = append(b.Func.WBLoads, bEnd)
   366  		}
   367  
   368  		// if we have more stores in this block, do this block again
   369  		if nWBops > 0 {
   370  			goto again
   371  		}
   372  	}
   373  }
   374  
   375  // computeZeroMap returns a map from an ID of a memory value to
   376  // a set of locations that are known to be zeroed at that memory value.
   377  func (f *Func) computeZeroMap() map[ID]ZeroRegion {
   378  	// Keep track of which parts of memory are known to be zero.
   379  	// This helps with removing write barriers for various initialization patterns.
   380  	// This analysis is conservative. We only keep track, for each memory state, of
   381  	// a single constant range of a single object which is known to be zero.
   382  	zeroes := map[ID]ZeroRegion{}
   383  	// Find new objects.
   384  	for _, b := range f.Blocks {
   385  		for _, v := range b.Values {
   386  			if v.Op != OpLoad {
   387  				continue
   388  			}
   389  			mem := v.MemoryArg()
   390  			if IsNewObject(v, mem) {
   391  				zeroes[mem.ID] = ZeroRegion{v, 0, v.Type.Elem().Size()}
   392  			}
   393  		}
   394  	}
   395  	// Find stores to those new objects.
   396  	for {
   397  		changed := false
   398  		for _, b := range f.Blocks {
   399  			// Note: iterating forwards helps convergence, as values are
   400  			// typically (but not always!) in store order.
   401  			for _, v := range b.Values {
   402  				if v.Op != OpStore {
   403  					continue
   404  				}
   405  				z, ok := zeroes[v.MemoryArg().ID]
   406  				if !ok {
   407  					continue
   408  				}
   409  				ptr := v.Args[0]
   410  				var off int64
   411  				size := v.Aux.(*types.Type).Size()
   412  				for ptr.Op == OpOffPtr {
   413  					off += ptr.AuxInt
   414  					ptr = ptr.Args[0]
   415  				}
   416  				if ptr != z.base {
   417  					// Different base object - we don't know anything.
   418  					// We could even be writing to the base object we know
   419  					// about, but through an aliased but offset pointer.
   420  					// So we have to throw all the zero information we have away.
   421  					continue
   422  				}
   423  				if off < z.min || off+size > z.max {
   424  					// Writing, at least partially, outside the known zeroes.
   425  					// We could salvage some zero information, but probably
   426  					// not worth it.
   427  					continue
   428  				}
   429  				// We now know we're storing to a zeroed area.
   430  				// We need to make a smaller zero range for the result of this store.
   431  				if off == z.min {
   432  					z.min += size
   433  				} else if off+size == z.max {
   434  					z.max -= size
   435  				} else {
   436  					// The store splits the known zero range in two.
   437  					// Keep track of the upper one, as we tend to initialize
   438  					// things in increasing memory order.
   439  					// TODO: keep track of larger one instead?
   440  					z.min = off + size
   441  				}
   442  				// Save updated zero range.
   443  				if zeroes[v.ID] != z {
   444  					zeroes[v.ID] = z
   445  					changed = true
   446  				}
   447  			}
   448  		}
   449  		if !changed {
   450  			break
   451  		}
   452  	}
   453  	return zeroes
   454  }
   455  
   456  // wbcall emits write barrier runtime call in b, returns memory.
   457  func wbcall(pos src.XPos, b *Block, fn, typ *obj.LSym, ptr, val, mem, sp, sb *Value) *Value {
   458  	config := b.Func.Config
   459  
   460  	// put arguments on stack
   461  	off := config.ctxt.FixedFrameSize()
   462  
   463  	if typ != nil { // for typedmemmove
   464  		taddr := b.NewValue1A(pos, OpAddr, b.Func.Config.Types.Uintptr, typ, sb)
   465  		off = round(off, taddr.Type.Alignment())
   466  		arg := b.NewValue1I(pos, OpOffPtr, taddr.Type.PtrTo(), off, sp)
   467  		mem = b.NewValue3A(pos, OpStore, types.TypeMem, ptr.Type, arg, taddr, mem)
   468  		off += taddr.Type.Size()
   469  	}
   470  
   471  	off = round(off, ptr.Type.Alignment())
   472  	arg := b.NewValue1I(pos, OpOffPtr, ptr.Type.PtrTo(), off, sp)
   473  	mem = b.NewValue3A(pos, OpStore, types.TypeMem, ptr.Type, arg, ptr, mem)
   474  	off += ptr.Type.Size()
   475  
   476  	if val != nil {
   477  		off = round(off, val.Type.Alignment())
   478  		arg = b.NewValue1I(pos, OpOffPtr, val.Type.PtrTo(), off, sp)
   479  		mem = b.NewValue3A(pos, OpStore, types.TypeMem, val.Type, arg, val, mem)
   480  		off += val.Type.Size()
   481  	}
   482  	off = round(off, config.PtrSize)
   483  
   484  	// issue call
   485  	mem = b.NewValue1A(pos, OpStaticCall, types.TypeMem, fn, mem)
   486  	mem.AuxInt = off - config.ctxt.FixedFrameSize()
   487  	return mem
   488  }
   489  
   490  // round to a multiple of r, r is a power of 2
   491  func round(o int64, r int64) int64 {
   492  	return (o + r - 1) &^ (r - 1)
   493  }
   494  
   495  // IsStackAddr reports whether v is known to be an address of a stack slot.
   496  func IsStackAddr(v *Value) bool {
   497  	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
   498  		v = v.Args[0]
   499  	}
   500  	switch v.Op {
   501  	case OpSP, OpLocalAddr:
   502  		return true
   503  	}
   504  	return false
   505  }
   506  
   507  // IsGlobalAddr reports whether v is known to be an address of a global (or nil).
   508  func IsGlobalAddr(v *Value) bool {
   509  	if v.Op == OpAddr && v.Args[0].Op == OpSB {
   510  		return true // address of a global
   511  	}
   512  	if v.Op == OpConst64 || v.Op == OpConst32 {
   513  		return true // nil, the only possible pointer constant
   514  	}
   515  	return false
   516  }
   517  
   518  // IsReadOnlyGlobalAddr reports whether v is known to be an address of a read-only global.
   519  func IsReadOnlyGlobalAddr(v *Value) bool {
   520  	if !IsGlobalAddr(v) {
   521  		return false
   522  	}
   523  	if v.Op == OpConst64 || v.Op == OpConst32 {
   524  		// Nil pointers are read only. See issue 33438.
   525  		return true
   526  	}
   527  	// See TODO in OpAddr case in IsSanitizerSafeAddr below.
   528  	return strings.HasPrefix(v.Aux.(*obj.LSym).Name, `""..stmp_`)
   529  }
   530  
   531  // IsNewObject reports whether v is a pointer to a freshly allocated & zeroed object at memory state mem.
   532  func IsNewObject(v *Value, mem *Value) bool {
   533  	if v.Op != OpLoad {
   534  		return false
   535  	}
   536  	if v.MemoryArg() != mem {
   537  		return false
   538  	}
   539  	if mem.Op != OpStaticCall {
   540  		return false
   541  	}
   542  	if !isSameSym(mem.Aux, "runtime.newobject") {
   543  		return false
   544  	}
   545  	if v.Args[0].Op != OpOffPtr {
   546  		return false
   547  	}
   548  	if v.Args[0].Args[0].Op != OpSP {
   549  		return false
   550  	}
   551  	c := v.Block.Func.Config
   552  	if v.Args[0].AuxInt != c.ctxt.FixedFrameSize()+c.RegSize { // offset of return value
   553  		return false
   554  	}
   555  	return true
   556  }
   557  
   558  // IsSanitizerSafeAddr reports whether v is known to be an address
   559  // that doesn't need instrumentation.
   560  func IsSanitizerSafeAddr(v *Value) bool {
   561  	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
   562  		v = v.Args[0]
   563  	}
   564  	switch v.Op {
   565  	case OpSP, OpLocalAddr:
   566  		// Stack addresses are always safe.
   567  		return true
   568  	case OpITab, OpStringPtr, OpGetClosurePtr:
   569  		// Itabs, string data, and closure fields are
   570  		// read-only once initialized.
   571  		return true
   572  	case OpAddr:
   573  		sym := v.Aux.(*obj.LSym)
   574  		// TODO(mdempsky): Find a cleaner way to
   575  		// detect this. It would be nice if we could
   576  		// test sym.Type==objabi.SRODATA, but we don't
   577  		// initialize sym.Type until after function
   578  		// compilation.
   579  		if strings.HasPrefix(sym.Name, `""..stmp_`) {
   580  			return true
   581  		}
   582  	}
   583  	return false
   584  }
   585  
   586  // isVolatile reports whether v is a pointer to argument region on stack which
   587  // will be clobbered by a function call.
   588  func isVolatile(v *Value) bool {
   589  	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
   590  		v = v.Args[0]
   591  	}
   592  	return v.Op == OpSP
   593  }
   594  

View as plain text