Source file src/pkg/cmd/compile/internal/ssa/writebarrier.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 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