Source file src/pkg/cmd/compile/internal/gc/plive.go

     1	// Copyright 2013 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	// Garbage collector liveness bitmap generation.
     6	
     7	// The command line flag -live causes this code to print debug information.
     8	// The levels are:
     9	//
    10	//	-live (aka -live=1): print liveness lists as code warnings at safe points
    11	//	-live=2: print an assembly listing with liveness annotations
    12	//
    13	// Each level includes the earlier output as well.
    14	
    15	package gc
    16	
    17	import (
    18		"cmd/compile/internal/ssa"
    19		"cmd/compile/internal/types"
    20		"cmd/internal/obj"
    21		"cmd/internal/objabi"
    22		"crypto/md5"
    23		"fmt"
    24		"strings"
    25	)
    26	
    27	// OpVarDef is an annotation for the liveness analysis, marking a place
    28	// where a complete initialization (definition) of a variable begins.
    29	// Since the liveness analysis can see initialization of single-word
    30	// variables quite easy, OpVarDef is only needed for multi-word
    31	// variables satisfying isfat(n.Type). For simplicity though, buildssa
    32	// emits OpVarDef regardless of variable width.
    33	//
    34	// An 'OpVarDef x' annotation in the instruction stream tells the liveness
    35	// analysis to behave as though the variable x is being initialized at that
    36	// point in the instruction stream. The OpVarDef must appear before the
    37	// actual (multi-instruction) initialization, and it must also appear after
    38	// any uses of the previous value, if any. For example, if compiling:
    39	//
    40	//	x = x[1:]
    41	//
    42	// it is important to generate code like:
    43	//
    44	//	base, len, cap = pieces of x[1:]
    45	//	OpVarDef x
    46	//	x = {base, len, cap}
    47	//
    48	// If instead the generated code looked like:
    49	//
    50	//	OpVarDef x
    51	//	base, len, cap = pieces of x[1:]
    52	//	x = {base, len, cap}
    53	//
    54	// then the liveness analysis would decide the previous value of x was
    55	// unnecessary even though it is about to be used by the x[1:] computation.
    56	// Similarly, if the generated code looked like:
    57	//
    58	//	base, len, cap = pieces of x[1:]
    59	//	x = {base, len, cap}
    60	//	OpVarDef x
    61	//
    62	// then the liveness analysis will not preserve the new value of x, because
    63	// the OpVarDef appears to have "overwritten" it.
    64	//
    65	// OpVarDef is a bit of a kludge to work around the fact that the instruction
    66	// stream is working on single-word values but the liveness analysis
    67	// wants to work on individual variables, which might be multi-word
    68	// aggregates. It might make sense at some point to look into letting
    69	// the liveness analysis work on single-word values as well, although
    70	// there are complications around interface values, slices, and strings,
    71	// all of which cannot be treated as individual words.
    72	//
    73	// OpVarKill is the opposite of OpVarDef: it marks a value as no longer needed,
    74	// even if its address has been taken. That is, an OpVarKill annotation asserts
    75	// that its argument is certainly dead, for use when the liveness analysis
    76	// would not otherwise be able to deduce that fact.
    77	
    78	// TODO: get rid of OpVarKill here. It's useful for stack frame allocation
    79	// so the compiler can allocate two temps to the same location. Here it's now
    80	// useless, since the implementation of stack objects.
    81	
    82	// BlockEffects summarizes the liveness effects on an SSA block.
    83	type BlockEffects struct {
    84		// Computed during Liveness.prologue using only the content of
    85		// individual blocks:
    86		//
    87		//	uevar: upward exposed variables (used before set in block)
    88		//	varkill: killed variables (set in block)
    89		uevar   varRegVec
    90		varkill varRegVec
    91	
    92		// Computed during Liveness.solve using control flow information:
    93		//
    94		//	livein: variables live at block entry
    95		//	liveout: variables live at block exit
    96		livein  varRegVec
    97		liveout varRegVec
    98	}
    99	
   100	// A collection of global state used by liveness analysis.
   101	type Liveness struct {
   102		fn         *Node
   103		f          *ssa.Func
   104		vars       []*Node
   105		idx        map[*Node]int32
   106		stkptrsize int64
   107	
   108		be []BlockEffects
   109	
   110		// unsafePoints bit i is set if Value ID i is not a safe point.
   111		unsafePoints bvec
   112	
   113		// An array with a bit vector for each safe point in the
   114		// current Block during Liveness.epilogue. Indexed in Value
   115		// order for that block. Additionally, for the entry block
   116		// livevars[0] is the entry bitmap. Liveness.compact moves
   117		// these to stackMaps and regMaps.
   118		livevars []varRegVec
   119	
   120		// livenessMap maps from safe points (i.e., CALLs) to their
   121		// liveness map indexes.
   122		livenessMap LivenessMap
   123		stackMapSet bvecSet
   124		stackMaps   []bvec
   125		regMapSet   map[liveRegMask]int
   126		regMaps     []liveRegMask
   127	
   128		cache progeffectscache
   129	}
   130	
   131	// LivenessMap maps from *ssa.Value to LivenessIndex.
   132	type LivenessMap struct {
   133		m []LivenessIndex
   134	}
   135	
   136	func (m *LivenessMap) reset(ids int) {
   137		m2 := m.m
   138		if ids > cap(m2) {
   139			m2 = make([]LivenessIndex, ids)
   140		} else {
   141			m2 = m2[:ids]
   142		}
   143		none := LivenessInvalid
   144		for i := range m2 {
   145			m2[i] = none
   146		}
   147		m.m = m2
   148	}
   149	
   150	func (m *LivenessMap) set(v *ssa.Value, i LivenessIndex) {
   151		m.m[v.ID] = i
   152	}
   153	
   154	func (m LivenessMap) Get(v *ssa.Value) LivenessIndex {
   155		if int(v.ID) < len(m.m) {
   156			return m.m[int(v.ID)]
   157		}
   158		// Not a safe point.
   159		return LivenessInvalid
   160	}
   161	
   162	// LivenessIndex stores the liveness map index for a safe-point.
   163	type LivenessIndex struct {
   164		stackMapIndex int
   165		regMapIndex   int
   166	}
   167	
   168	// LivenessInvalid indicates an unsafe point.
   169	//
   170	// We use index -2 because PCDATA tables conventionally start at -1,
   171	// so -1 is used to mean the entry liveness map (which is actually at
   172	// index 0; sigh). TODO(austin): Maybe we should use PCDATA+1 as the
   173	// index into the liveness map so -1 uniquely refers to the entry
   174	// liveness map.
   175	var LivenessInvalid = LivenessIndex{-2, -2}
   176	
   177	func (idx LivenessIndex) Valid() bool {
   178		return idx.stackMapIndex >= 0
   179	}
   180	
   181	type progeffectscache struct {
   182		retuevar    []int32
   183		tailuevar   []int32
   184		initialized bool
   185	}
   186	
   187	// varRegVec contains liveness bitmaps for variables and registers.
   188	type varRegVec struct {
   189		vars bvec
   190		regs liveRegMask
   191	}
   192	
   193	func (v *varRegVec) Eq(v2 varRegVec) bool {
   194		return v.vars.Eq(v2.vars) && v.regs == v2.regs
   195	}
   196	
   197	func (v *varRegVec) Copy(v2 varRegVec) {
   198		v.vars.Copy(v2.vars)
   199		v.regs = v2.regs
   200	}
   201	
   202	func (v *varRegVec) Clear() {
   203		v.vars.Clear()
   204		v.regs = 0
   205	}
   206	
   207	func (v *varRegVec) Or(v1, v2 varRegVec) {
   208		v.vars.Or(v1.vars, v2.vars)
   209		v.regs = v1.regs | v2.regs
   210	}
   211	
   212	func (v *varRegVec) AndNot(v1, v2 varRegVec) {
   213		v.vars.AndNot(v1.vars, v2.vars)
   214		v.regs = v1.regs &^ v2.regs
   215	}
   216	
   217	// livenessShouldTrack reports whether the liveness analysis
   218	// should track the variable n.
   219	// We don't care about variables that have no pointers,
   220	// nor do we care about non-local variables,
   221	// nor do we care about empty structs (handled by the pointer check),
   222	// nor do we care about the fake PAUTOHEAP variables.
   223	func livenessShouldTrack(n *Node) bool {
   224		return n.Op == ONAME && (n.Class() == PAUTO || n.Class() == PPARAM || n.Class() == PPARAMOUT) && types.Haspointers(n.Type)
   225	}
   226	
   227	// getvariables returns the list of on-stack variables that we need to track
   228	// and a map for looking up indices by *Node.
   229	func getvariables(fn *Node) ([]*Node, map[*Node]int32) {
   230		var vars []*Node
   231		for _, n := range fn.Func.Dcl {
   232			if livenessShouldTrack(n) {
   233				vars = append(vars, n)
   234			}
   235		}
   236		idx := make(map[*Node]int32, len(vars))
   237		for i, n := range vars {
   238			idx[n] = int32(i)
   239		}
   240		return vars, idx
   241	}
   242	
   243	func (lv *Liveness) initcache() {
   244		if lv.cache.initialized {
   245			Fatalf("liveness cache initialized twice")
   246			return
   247		}
   248		lv.cache.initialized = true
   249	
   250		for i, node := range lv.vars {
   251			switch node.Class() {
   252			case PPARAM:
   253				// A return instruction with a p.to is a tail return, which brings
   254				// the stack pointer back up (if it ever went down) and then jumps
   255				// to a new function entirely. That form of instruction must read
   256				// all the parameters for correctness, and similarly it must not
   257				// read the out arguments - they won't be set until the new
   258				// function runs.
   259				lv.cache.tailuevar = append(lv.cache.tailuevar, int32(i))
   260	
   261			case PPARAMOUT:
   262				// All results are live at every return point.
   263				// Note that this point is after escaping return values
   264				// are copied back to the stack using their PAUTOHEAP references.
   265				lv.cache.retuevar = append(lv.cache.retuevar, int32(i))
   266			}
   267		}
   268	}
   269	
   270	// A liveEffect is a set of flags that describe an instruction's
   271	// liveness effects on a variable.
   272	//
   273	// The possible flags are:
   274	//	uevar - used by the instruction
   275	//	varkill - killed by the instruction (set)
   276	// A kill happens after the use (for an instruction that updates a value, for example).
   277	type liveEffect int
   278	
   279	const (
   280		uevar liveEffect = 1 << iota
   281		varkill
   282	)
   283	
   284	// valueEffects returns the index of a variable in lv.vars and the
   285	// liveness effects v has on that variable.
   286	// If v does not affect any tracked variables, it returns -1, 0.
   287	func (lv *Liveness) valueEffects(v *ssa.Value) (int32, liveEffect) {
   288		n, e := affectedNode(v)
   289		if e == 0 || n == nil || n.Op != ONAME { // cheapest checks first
   290			return -1, 0
   291		}
   292	
   293		// AllocFrame has dropped unused variables from
   294		// lv.fn.Func.Dcl, but they might still be referenced by
   295		// OpVarFoo pseudo-ops. Ignore them to prevent "lost track of
   296		// variable" ICEs (issue 19632).
   297		switch v.Op {
   298		case ssa.OpVarDef, ssa.OpVarKill, ssa.OpVarLive, ssa.OpKeepAlive:
   299			if !n.Name.Used() {
   300				return -1, 0
   301			}
   302		}
   303	
   304		var effect liveEffect
   305		// Read is a read, obviously.
   306		//
   307		// Addr is a read also, as any subseqent holder of the pointer must be able
   308		// to see all the values (including initialization) written so far.
   309		// This also prevents a variable from "coming back from the dead" and presenting
   310		// stale pointers to the garbage collector. See issue 28445.
   311		if e&(ssa.SymRead|ssa.SymAddr) != 0 {
   312			effect |= uevar
   313		}
   314		if e&ssa.SymWrite != 0 && (!isfat(n.Type) || v.Op == ssa.OpVarDef) {
   315			effect |= varkill
   316		}
   317	
   318		if effect == 0 {
   319			return -1, 0
   320		}
   321	
   322		if pos, ok := lv.idx[n]; ok {
   323			return pos, effect
   324		}
   325		return -1, 0
   326	}
   327	
   328	// affectedNode returns the *Node affected by v
   329	func affectedNode(v *ssa.Value) (*Node, ssa.SymEffect) {
   330		// Special cases.
   331		switch v.Op {
   332		case ssa.OpLoadReg:
   333			n, _ := AutoVar(v.Args[0])
   334			return n, ssa.SymRead
   335		case ssa.OpStoreReg:
   336			n, _ := AutoVar(v)
   337			return n, ssa.SymWrite
   338	
   339		case ssa.OpVarLive:
   340			return v.Aux.(*Node), ssa.SymRead
   341		case ssa.OpVarDef, ssa.OpVarKill:
   342			return v.Aux.(*Node), ssa.SymWrite
   343		case ssa.OpKeepAlive:
   344			n, _ := AutoVar(v.Args[0])
   345			return n, ssa.SymRead
   346		}
   347	
   348		e := v.Op.SymEffect()
   349		if e == 0 {
   350			return nil, 0
   351		}
   352	
   353		switch a := v.Aux.(type) {
   354		case nil, *obj.LSym:
   355			// ok, but no node
   356			return nil, e
   357		case *Node:
   358			return a, e
   359		default:
   360			Fatalf("weird aux: %s", v.LongString())
   361			return nil, e
   362		}
   363	}
   364	
   365	// regEffects returns the registers affected by v.
   366	func (lv *Liveness) regEffects(v *ssa.Value) (uevar, kill liveRegMask) {
   367		if v.Op == ssa.OpPhi {
   368			// All phi node arguments must come from the same
   369			// register and the result must also go to that
   370			// register, so there's no overall effect.
   371			return 0, 0
   372		}
   373		addLocs := func(mask liveRegMask, v *ssa.Value, ptrOnly bool) liveRegMask {
   374			if int(v.ID) >= len(lv.f.RegAlloc) {
   375				// v has no allocated registers.
   376				return mask
   377			}
   378			loc := lv.f.RegAlloc[v.ID]
   379			if loc == nil {
   380				// v has no allocated registers.
   381				return mask
   382			}
   383			if v.Op == ssa.OpGetG {
   384				// GetG represents the G register, which is a
   385				// pointer, but not a valid GC register. The
   386				// current G is always reachable, so it's okay
   387				// to ignore this register.
   388				return mask
   389			}
   390	
   391			// Collect registers and types from v's location.
   392			var regs [2]*ssa.Register
   393			nreg := 0
   394			switch loc := loc.(type) {
   395			case ssa.LocalSlot:
   396				return mask
   397			case *ssa.Register:
   398				if ptrOnly && !v.Type.HasHeapPointer() {
   399					return mask
   400				}
   401				regs[0] = loc
   402				nreg = 1
   403			case ssa.LocPair:
   404				// The value will have TTUPLE type, and the
   405				// children are nil or *ssa.Register.
   406				if v.Type.Etype != types.TTUPLE {
   407					v.Fatalf("location pair %s has non-tuple type %v", loc, v.Type)
   408				}
   409				for i, loc1 := range loc {
   410					if loc1 == nil {
   411						continue
   412					}
   413					if ptrOnly && !v.Type.FieldType(i).HasHeapPointer() {
   414						continue
   415					}
   416					regs[nreg] = loc1.(*ssa.Register)
   417					nreg++
   418				}
   419			default:
   420				v.Fatalf("weird RegAlloc location: %s (%T)", loc, loc)
   421			}
   422	
   423			// Add register locations to vars.
   424			for _, reg := range regs[:nreg] {
   425				if reg.GCNum() == -1 {
   426					if ptrOnly {
   427						v.Fatalf("pointer in non-pointer register %v", reg)
   428					} else {
   429						continue
   430					}
   431				}
   432				mask |= 1 << uint(reg.GCNum())
   433			}
   434			return mask
   435		}
   436	
   437		// v clobbers all registers it writes to (whether or not the
   438		// write is pointer-typed).
   439		kill = addLocs(0, v, false)
   440		for _, arg := range v.Args {
   441			// v uses all registers is reads from, but we only
   442			// care about marking those containing pointers.
   443			uevar = addLocs(uevar, arg, true)
   444		}
   445		return uevar, kill
   446	}
   447	
   448	type liveRegMask uint32
   449	
   450	func (m liveRegMask) niceString(config *ssa.Config) string {
   451		if m == 0 {
   452			return "<none>"
   453		}
   454		str := ""
   455		for i, reg := range config.GCRegMap {
   456			if m&(1<<uint(i)) != 0 {
   457				if str != "" {
   458					str += ","
   459				}
   460				str += reg.String()
   461			}
   462		}
   463		return str
   464	}
   465	
   466	type livenessFuncCache struct {
   467		be          []BlockEffects
   468		livenessMap LivenessMap
   469	}
   470	
   471	// Constructs a new liveness structure used to hold the global state of the
   472	// liveness computation. The cfg argument is a slice of *BasicBlocks and the
   473	// vars argument is a slice of *Nodes.
   474	func newliveness(fn *Node, f *ssa.Func, vars []*Node, idx map[*Node]int32, stkptrsize int64) *Liveness {
   475		lv := &Liveness{
   476			fn:         fn,
   477			f:          f,
   478			vars:       vars,
   479			idx:        idx,
   480			stkptrsize: stkptrsize,
   481	
   482			regMapSet: make(map[liveRegMask]int),
   483		}
   484	
   485		// Significant sources of allocation are kept in the ssa.Cache
   486		// and reused. Surprisingly, the bit vectors themselves aren't
   487		// a major source of allocation, but the slices are.
   488		if lc, _ := f.Cache.Liveness.(*livenessFuncCache); lc == nil {
   489			// Prep the cache so liveness can fill it later.
   490			f.Cache.Liveness = new(livenessFuncCache)
   491		} else {
   492			if cap(lc.be) >= f.NumBlocks() {
   493				lv.be = lc.be[:f.NumBlocks()]
   494			}
   495			lv.livenessMap = LivenessMap{lc.livenessMap.m[:0]}
   496		}
   497		if lv.be == nil {
   498			lv.be = make([]BlockEffects, f.NumBlocks())
   499		}
   500	
   501		nblocks := int32(len(f.Blocks))
   502		nvars := int32(len(vars))
   503		bulk := bvbulkalloc(nvars, nblocks*7)
   504		for _, b := range f.Blocks {
   505			be := lv.blockEffects(b)
   506	
   507			be.uevar = varRegVec{vars: bulk.next()}
   508			be.varkill = varRegVec{vars: bulk.next()}
   509			be.livein = varRegVec{vars: bulk.next()}
   510			be.liveout = varRegVec{vars: bulk.next()}
   511		}
   512		lv.livenessMap.reset(lv.f.NumValues())
   513	
   514		lv.markUnsafePoints()
   515		return lv
   516	}
   517	
   518	func (lv *Liveness) blockEffects(b *ssa.Block) *BlockEffects {
   519		return &lv.be[b.ID]
   520	}
   521	
   522	// NOTE: The bitmap for a specific type t could be cached in t after
   523	// the first run and then simply copied into bv at the correct offset
   524	// on future calls with the same type t.
   525	func onebitwalktype1(t *types.Type, off int64, bv bvec) {
   526		if t.Align > 0 && off&int64(t.Align-1) != 0 {
   527			Fatalf("onebitwalktype1: invalid initial alignment: type %v has alignment %d, but offset is %v", t, t.Align, off)
   528		}
   529	
   530		switch t.Etype {
   531		case TINT8, TUINT8, TINT16, TUINT16,
   532			TINT32, TUINT32, TINT64, TUINT64,
   533			TINT, TUINT, TUINTPTR, TBOOL,
   534			TFLOAT32, TFLOAT64, TCOMPLEX64, TCOMPLEX128:
   535	
   536		case TPTR, TUNSAFEPTR, TFUNC, TCHAN, TMAP:
   537			if off&int64(Widthptr-1) != 0 {
   538				Fatalf("onebitwalktype1: invalid alignment, %v", t)
   539			}
   540			bv.Set(int32(off / int64(Widthptr))) // pointer
   541	
   542		case TSTRING:
   543			// struct { byte *str; intgo len; }
   544			if off&int64(Widthptr-1) != 0 {
   545				Fatalf("onebitwalktype1: invalid alignment, %v", t)
   546			}
   547			bv.Set(int32(off / int64(Widthptr))) //pointer in first slot
   548	
   549		case TINTER:
   550			// struct { Itab *tab;	void *data; }
   551			// or, when isnilinter(t)==true:
   552			// struct { Type *type; void *data; }
   553			if off&int64(Widthptr-1) != 0 {
   554				Fatalf("onebitwalktype1: invalid alignment, %v", t)
   555			}
   556			// The first word of an interface is a pointer, but we don't
   557			// treat it as such.
   558			// 1. If it is a non-empty interface, the pointer points to an itab
   559			//    which is always in persistentalloc space.
   560			// 2. If it is an empty interface, the pointer points to a _type.
   561			//   a. If it is a compile-time-allocated type, it points into
   562			//      the read-only data section.
   563			//   b. If it is a reflect-allocated type, it points into the Go heap.
   564			//      Reflect is responsible for keeping a reference to
   565			//      the underlying type so it won't be GCd.
   566			// If we ever have a moving GC, we need to change this for 2b (as
   567			// well as scan itabs to update their itab._type fields).
   568			bv.Set(int32(off/int64(Widthptr) + 1)) // pointer in second slot
   569	
   570		case TSLICE:
   571			// struct { byte *array; uintgo len; uintgo cap; }
   572			if off&int64(Widthptr-1) != 0 {
   573				Fatalf("onebitwalktype1: invalid TARRAY alignment, %v", t)
   574			}
   575			bv.Set(int32(off / int64(Widthptr))) // pointer in first slot (BitsPointer)
   576	
   577		case TARRAY:
   578			elt := t.Elem()
   579			if elt.Width == 0 {
   580				// Short-circuit for #20739.
   581				break
   582			}
   583			for i := int64(0); i < t.NumElem(); i++ {
   584				onebitwalktype1(elt, off, bv)
   585				off += elt.Width
   586			}
   587	
   588		case TSTRUCT:
   589			for _, f := range t.Fields().Slice() {
   590				onebitwalktype1(f.Type, off+f.Offset, bv)
   591			}
   592	
   593		default:
   594			Fatalf("onebitwalktype1: unexpected type, %v", t)
   595		}
   596	}
   597	
   598	// usedRegs returns the maximum width of the live register map.
   599	func (lv *Liveness) usedRegs() int32 {
   600		var any liveRegMask
   601		for _, live := range lv.regMaps {
   602			any |= live
   603		}
   604		i := int32(0)
   605		for any != 0 {
   606			any >>= 1
   607			i++
   608		}
   609		return i
   610	}
   611	
   612	// Generates live pointer value maps for arguments and local variables. The
   613	// this argument and the in arguments are always assumed live. The vars
   614	// argument is a slice of *Nodes.
   615	func (lv *Liveness) pointerMap(liveout bvec, vars []*Node, args, locals bvec) {
   616		for i := int32(0); ; i++ {
   617			i = liveout.Next(i)
   618			if i < 0 {
   619				break
   620			}
   621			node := vars[i]
   622			switch node.Class() {
   623			case PAUTO:
   624				onebitwalktype1(node.Type, node.Xoffset+lv.stkptrsize, locals)
   625	
   626			case PPARAM, PPARAMOUT:
   627				onebitwalktype1(node.Type, node.Xoffset, args)
   628			}
   629		}
   630	}
   631	
   632	// markUnsafePoints finds unsafe points and computes lv.unsafePoints.
   633	func (lv *Liveness) markUnsafePoints() {
   634		if compiling_runtime || lv.f.NoSplit {
   635			// No complex analysis necessary. Do this on the fly
   636			// in issafepoint.
   637			return
   638		}
   639	
   640		lv.unsafePoints = bvalloc(int32(lv.f.NumValues()))
   641	
   642		// Mark write barrier unsafe points.
   643		for _, wbBlock := range lv.f.WBLoads {
   644			if wbBlock.Kind == ssa.BlockPlain && len(wbBlock.Values) == 0 {
   645				// The write barrier block was optimized away
   646				// but we haven't done dead block elimination.
   647				// (This can happen in -N mode.)
   648				continue
   649			}
   650			// Check that we have the expected diamond shape.
   651			if len(wbBlock.Succs) != 2 {
   652				lv.f.Fatalf("expected branch at write barrier block %v", wbBlock)
   653			}
   654			s0, s1 := wbBlock.Succs[0].Block(), wbBlock.Succs[1].Block()
   655			if s0 == s1 {
   656				// There's no difference between write barrier on and off.
   657				// Thus there's no unsafe locations. See issue 26024.
   658				continue
   659			}
   660			if s0.Kind != ssa.BlockPlain || s1.Kind != ssa.BlockPlain {
   661				lv.f.Fatalf("expected successors of write barrier block %v to be plain", wbBlock)
   662			}
   663			if s0.Succs[0].Block() != s1.Succs[0].Block() {
   664				lv.f.Fatalf("expected successors of write barrier block %v to converge", wbBlock)
   665			}
   666	
   667			// Flow backwards from the control value to find the
   668			// flag load. We don't know what lowered ops we're
   669			// looking for, but all current arches produce a
   670			// single op that does the memory load from the flag
   671			// address, so we look for that.
   672			var load *ssa.Value
   673			v := wbBlock.Control
   674			for {
   675				if sym, ok := v.Aux.(*obj.LSym); ok && sym == writeBarrier {
   676					load = v
   677					break
   678				}
   679				switch v.Op {
   680				case ssa.Op386TESTL:
   681					// 386 lowers Neq32 to (TESTL cond cond),
   682					if v.Args[0] == v.Args[1] {
   683						v = v.Args[0]
   684						continue
   685					}
   686				case ssa.Op386MOVLload, ssa.OpARM64MOVWUload, ssa.OpPPC64MOVWZload, ssa.OpWasmI64Load32U:
   687					// Args[0] is the address of the write
   688					// barrier control. Ignore Args[1],
   689					// which is the mem operand.
   690					// TODO: Just ignore mem operands?
   691					v = v.Args[0]
   692					continue
   693				}
   694				// Common case: just flow backwards.
   695				if len(v.Args) != 1 {
   696					v.Fatalf("write barrier control value has more than one argument: %s", v.LongString())
   697				}
   698				v = v.Args[0]
   699			}
   700	
   701			// Mark everything after the load unsafe.
   702			found := false
   703			for _, v := range wbBlock.Values {
   704				found = found || v == load
   705				if found {
   706					lv.unsafePoints.Set(int32(v.ID))
   707				}
   708			}
   709	
   710			// Mark the two successor blocks unsafe. These come
   711			// back together immediately after the direct write in
   712			// one successor and the last write barrier call in
   713			// the other, so there's no need to be more precise.
   714			for _, succ := range wbBlock.Succs {
   715				for _, v := range succ.Block().Values {
   716					lv.unsafePoints.Set(int32(v.ID))
   717				}
   718			}
   719		}
   720	
   721		// Find uintptr -> unsafe.Pointer conversions and flood
   722		// unsafeness back to a call (which is always a safe point).
   723		//
   724		// Looking for the uintptr -> unsafe.Pointer conversion has a
   725		// few advantages over looking for unsafe.Pointer -> uintptr
   726		// conversions:
   727		//
   728		// 1. We avoid needlessly blocking safe-points for
   729		// unsafe.Pointer -> uintptr conversions that never go back to
   730		// a Pointer.
   731		//
   732		// 2. We don't have to detect calls to reflect.Value.Pointer,
   733		// reflect.Value.UnsafeAddr, and reflect.Value.InterfaceData,
   734		// which are implicit unsafe.Pointer -> uintptr conversions.
   735		// We can't even reliably detect this if there's an indirect
   736		// call to one of these methods.
   737		//
   738		// TODO: For trivial unsafe.Pointer arithmetic, it would be
   739		// nice to only flood as far as the unsafe.Pointer -> uintptr
   740		// conversion, but it's hard to know which argument of an Add
   741		// or Sub to follow.
   742		var flooded bvec
   743		var flood func(b *ssa.Block, vi int)
   744		flood = func(b *ssa.Block, vi int) {
   745			if flooded.n == 0 {
   746				flooded = bvalloc(int32(lv.f.NumBlocks()))
   747			}
   748			if flooded.Get(int32(b.ID)) {
   749				return
   750			}
   751			for i := vi - 1; i >= 0; i-- {
   752				v := b.Values[i]
   753				if v.Op.IsCall() {
   754					// Uintptrs must not contain live
   755					// pointers across calls, so stop
   756					// flooding.
   757					return
   758				}
   759				lv.unsafePoints.Set(int32(v.ID))
   760			}
   761			if vi == len(b.Values) {
   762				// We marked all values in this block, so no
   763				// need to flood this block again.
   764				flooded.Set(int32(b.ID))
   765			}
   766			for _, pred := range b.Preds {
   767				flood(pred.Block(), len(pred.Block().Values))
   768			}
   769		}
   770		for _, b := range lv.f.Blocks {
   771			for i, v := range b.Values {
   772				if !(v.Op == ssa.OpConvert && v.Type.IsPtrShaped()) {
   773					continue
   774				}
   775				// Flood the unsafe-ness of this backwards
   776				// until we hit a call.
   777				flood(b, i+1)
   778			}
   779		}
   780	}
   781	
   782	// Returns true for instructions that are safe points that must be annotated
   783	// with liveness information.
   784	func (lv *Liveness) issafepoint(v *ssa.Value) bool {
   785		// The runtime was written with the assumption that
   786		// safe-points only appear at call sites (because that's how
   787		// it used to be). We could and should improve that, but for
   788		// now keep the old safe-point rules in the runtime.
   789		//
   790		// go:nosplit functions are similar. Since safe points used to
   791		// be coupled with stack checks, go:nosplit often actually
   792		// means "no safe points in this function".
   793		if compiling_runtime || lv.f.NoSplit {
   794			return v.Op.IsCall()
   795		}
   796		switch v.Op {
   797		case ssa.OpInitMem, ssa.OpArg, ssa.OpSP, ssa.OpSB,
   798			ssa.OpSelect0, ssa.OpSelect1, ssa.OpGetG,
   799			ssa.OpVarDef, ssa.OpVarLive, ssa.OpKeepAlive,
   800			ssa.OpPhi:
   801			// These don't produce code (see genssa).
   802			return false
   803		}
   804		return !lv.unsafePoints.Get(int32(v.ID))
   805	}
   806	
   807	// Initializes the sets for solving the live variables. Visits all the
   808	// instructions in each basic block to summarizes the information at each basic
   809	// block
   810	func (lv *Liveness) prologue() {
   811		lv.initcache()
   812	
   813		for _, b := range lv.f.Blocks {
   814			be := lv.blockEffects(b)
   815	
   816			// Walk the block instructions backward and update the block
   817			// effects with the each prog effects.
   818			for j := len(b.Values) - 1; j >= 0; j-- {
   819				pos, e := lv.valueEffects(b.Values[j])
   820				regUevar, regKill := lv.regEffects(b.Values[j])
   821				if e&varkill != 0 {
   822					be.varkill.vars.Set(pos)
   823					be.uevar.vars.Unset(pos)
   824				}
   825				be.varkill.regs |= regKill
   826				be.uevar.regs &^= regKill
   827				if e&uevar != 0 {
   828					be.uevar.vars.Set(pos)
   829				}
   830				be.uevar.regs |= regUevar
   831			}
   832		}
   833	}
   834	
   835	// Solve the liveness dataflow equations.
   836	func (lv *Liveness) solve() {
   837		// These temporary bitvectors exist to avoid successive allocations and
   838		// frees within the loop.
   839		nvars := int32(len(lv.vars))
   840		newlivein := varRegVec{vars: bvalloc(nvars)}
   841		newliveout := varRegVec{vars: bvalloc(nvars)}
   842	
   843		// Walk blocks in postorder ordering. This improves convergence.
   844		po := lv.f.Postorder()
   845	
   846		// Iterate through the blocks in reverse round-robin fashion. A work
   847		// queue might be slightly faster. As is, the number of iterations is
   848		// so low that it hardly seems to be worth the complexity.
   849	
   850		for change := true; change; {
   851			change = false
   852			for _, b := range po {
   853				be := lv.blockEffects(b)
   854	
   855				newliveout.Clear()
   856				switch b.Kind {
   857				case ssa.BlockRet:
   858					for _, pos := range lv.cache.retuevar {
   859						newliveout.vars.Set(pos)
   860					}
   861				case ssa.BlockRetJmp:
   862					for _, pos := range lv.cache.tailuevar {
   863						newliveout.vars.Set(pos)
   864					}
   865				case ssa.BlockExit:
   866					// panic exit - nothing to do
   867				default:
   868					// A variable is live on output from this block
   869					// if it is live on input to some successor.
   870					//
   871					// out[b] = \bigcup_{s \in succ[b]} in[s]
   872					newliveout.Copy(lv.blockEffects(b.Succs[0].Block()).livein)
   873					for _, succ := range b.Succs[1:] {
   874						newliveout.Or(newliveout, lv.blockEffects(succ.Block()).livein)
   875					}
   876				}
   877	
   878				if !be.liveout.Eq(newliveout) {
   879					change = true
   880					be.liveout.Copy(newliveout)
   881				}
   882	
   883				// A variable is live on input to this block
   884				// if it is used by this block, or live on output from this block and
   885				// not set by the code in this block.
   886				//
   887				// in[b] = uevar[b] \cup (out[b] \setminus varkill[b])
   888				newlivein.AndNot(be.liveout, be.varkill)
   889				be.livein.Or(newlivein, be.uevar)
   890			}
   891		}
   892	}
   893	
   894	// Visits all instructions in a basic block and computes a bit vector of live
   895	// variables at each safe point locations.
   896	func (lv *Liveness) epilogue() {
   897		nvars := int32(len(lv.vars))
   898		liveout := varRegVec{vars: bvalloc(nvars)}
   899		livedefer := bvalloc(nvars) // always-live variables
   900	
   901		// If there is a defer (that could recover), then all output
   902		// parameters are live all the time.  In addition, any locals
   903		// that are pointers to heap-allocated output parameters are
   904		// also always live (post-deferreturn code needs these
   905		// pointers to copy values back to the stack).
   906		// TODO: if the output parameter is heap-allocated, then we
   907		// don't need to keep the stack copy live?
   908		if lv.fn.Func.HasDefer() {
   909			for i, n := range lv.vars {
   910				if n.Class() == PPARAMOUT {
   911					if n.IsOutputParamHeapAddr() {
   912						// Just to be paranoid.  Heap addresses are PAUTOs.
   913						Fatalf("variable %v both output param and heap output param", n)
   914					}
   915					if n.Name.Param.Heapaddr != nil {
   916						// If this variable moved to the heap, then
   917						// its stack copy is not live.
   918						continue
   919					}
   920					// Note: zeroing is handled by zeroResults in walk.go.
   921					livedefer.Set(int32(i))
   922				}
   923				if n.IsOutputParamHeapAddr() {
   924					// This variable will be overwritten early in the function
   925					// prologue (from the result of a mallocgc) but we need to
   926					// zero it in case that malloc causes a stack scan.
   927					n.Name.SetNeedzero(true)
   928					livedefer.Set(int32(i))
   929				}
   930			}
   931		}
   932	
   933		// We must analyze the entry block first. The runtime assumes
   934		// the function entry map is index 0. Conveniently, layout
   935		// already ensured that the entry block is first.
   936		if lv.f.Entry != lv.f.Blocks[0] {
   937			lv.f.Fatalf("entry block must be first")
   938		}
   939	
   940		{
   941			// Reserve an entry for function entry.
   942			live := bvalloc(nvars)
   943			lv.livevars = append(lv.livevars, varRegVec{vars: live})
   944		}
   945	
   946		for _, b := range lv.f.Blocks {
   947			be := lv.blockEffects(b)
   948			firstBitmapIndex := len(lv.livevars)
   949	
   950			// Walk forward through the basic block instructions and
   951			// allocate liveness maps for those instructions that need them.
   952			for _, v := range b.Values {
   953				if !lv.issafepoint(v) {
   954					continue
   955				}
   956	
   957				live := bvalloc(nvars)
   958				lv.livevars = append(lv.livevars, varRegVec{vars: live})
   959			}
   960	
   961			// walk backward, construct maps at each safe point
   962			index := int32(len(lv.livevars) - 1)
   963	
   964			liveout.Copy(be.liveout)
   965			for i := len(b.Values) - 1; i >= 0; i-- {
   966				v := b.Values[i]
   967	
   968				if lv.issafepoint(v) {
   969					// Found an interesting instruction, record the
   970					// corresponding liveness information.
   971	
   972					live := &lv.livevars[index]
   973					live.Or(*live, liveout)
   974					live.vars.Or(live.vars, livedefer) // only for non-entry safe points
   975					index--
   976				}
   977	
   978				// Update liveness information.
   979				pos, e := lv.valueEffects(v)
   980				regUevar, regKill := lv.regEffects(v)
   981				if e&varkill != 0 {
   982					liveout.vars.Unset(pos)
   983				}
   984				liveout.regs &^= regKill
   985				if e&uevar != 0 {
   986					liveout.vars.Set(pos)
   987				}
   988				liveout.regs |= regUevar
   989			}
   990	
   991			if b == lv.f.Entry {
   992				if index != 0 {
   993					Fatalf("bad index for entry point: %v", index)
   994				}
   995	
   996				// Check to make sure only input variables are live.
   997				for i, n := range lv.vars {
   998					if !liveout.vars.Get(int32(i)) {
   999						continue
  1000					}
  1001					if n.Class() == PPARAM {
  1002						continue // ok
  1003					}
  1004					Fatalf("bad live variable at entry of %v: %L", lv.fn.Func.Nname, n)
  1005				}
  1006	
  1007				// Record live variables.
  1008				live := &lv.livevars[index]
  1009				live.Or(*live, liveout)
  1010			}
  1011	
  1012			// Check that no registers are live across calls.
  1013			// For closure calls, the CALLclosure is the last use
  1014			// of the context register, so it's dead after the call.
  1015			index = int32(firstBitmapIndex)
  1016			for _, v := range b.Values {
  1017				if lv.issafepoint(v) {
  1018					live := lv.livevars[index]
  1019					if v.Op.IsCall() && live.regs != 0 {
  1020						lv.printDebug()
  1021						v.Fatalf("%v register %s recorded as live at call", lv.fn.Func.Nname, live.regs.niceString(lv.f.Config))
  1022					}
  1023					index++
  1024				}
  1025			}
  1026	
  1027			// The liveness maps for this block are now complete. Compact them.
  1028			lv.compact(b)
  1029		}
  1030	
  1031		// Done compacting. Throw out the stack map set.
  1032		lv.stackMaps = lv.stackMapSet.extractUniqe()
  1033		lv.stackMapSet = bvecSet{}
  1034	
  1035		// Useful sanity check: on entry to the function,
  1036		// the only things that can possibly be live are the
  1037		// input parameters.
  1038		for j, n := range lv.vars {
  1039			if n.Class() != PPARAM && lv.stackMaps[0].Get(int32(j)) {
  1040				lv.f.Fatalf("%v %L recorded as live on entry", lv.fn.Func.Nname, n)
  1041			}
  1042		}
  1043		// Check that no registers are live at function entry.
  1044		// The context register, if any, comes from a
  1045		// LoweredGetClosurePtr operation first thing in the function,
  1046		// so it doesn't appear live at entry.
  1047		if regs := lv.regMaps[0]; regs != 0 {
  1048			lv.printDebug()
  1049			lv.f.Fatalf("%v register %s recorded as live on entry", lv.fn.Func.Nname, regs.niceString(lv.f.Config))
  1050		}
  1051	}
  1052	
  1053	// Compact coalesces identical bitmaps from lv.livevars into the sets
  1054	// lv.stackMapSet and lv.regMaps.
  1055	//
  1056	// Compact clears lv.livevars.
  1057	//
  1058	// There are actually two lists of bitmaps, one list for the local variables and one
  1059	// list for the function arguments. Both lists are indexed by the same PCDATA
  1060	// index, so the corresponding pairs must be considered together when
  1061	// merging duplicates. The argument bitmaps change much less often during
  1062	// function execution than the local variable bitmaps, so it is possible that
  1063	// we could introduce a separate PCDATA index for arguments vs locals and
  1064	// then compact the set of argument bitmaps separately from the set of
  1065	// local variable bitmaps. As of 2014-04-02, doing this to the godoc binary
  1066	// is actually a net loss: we save about 50k of argument bitmaps but the new
  1067	// PCDATA tables cost about 100k. So for now we keep using a single index for
  1068	// both bitmap lists.
  1069	func (lv *Liveness) compact(b *ssa.Block) {
  1070		add := func(live varRegVec) LivenessIndex {
  1071			// Deduplicate the stack map.
  1072			stackIndex := lv.stackMapSet.add(live.vars)
  1073			// Deduplicate the register map.
  1074			regIndex, ok := lv.regMapSet[live.regs]
  1075			if !ok {
  1076				regIndex = len(lv.regMapSet)
  1077				lv.regMapSet[live.regs] = regIndex
  1078				lv.regMaps = append(lv.regMaps, live.regs)
  1079			}
  1080			return LivenessIndex{stackIndex, regIndex}
  1081		}
  1082		pos := 0
  1083		if b == lv.f.Entry {
  1084			// Handle entry stack map.
  1085			add(lv.livevars[0])
  1086			pos++
  1087		}
  1088		for _, v := range b.Values {
  1089			if lv.issafepoint(v) {
  1090				lv.livenessMap.set(v, add(lv.livevars[pos]))
  1091				pos++
  1092			}
  1093		}
  1094	
  1095		// Reset livevars.
  1096		lv.livevars = lv.livevars[:0]
  1097	}
  1098	
  1099	func (lv *Liveness) showlive(v *ssa.Value, live bvec) {
  1100		if debuglive == 0 || lv.fn.funcname() == "init" || strings.HasPrefix(lv.fn.funcname(), ".") {
  1101			return
  1102		}
  1103		if !(v == nil || v.Op.IsCall()) {
  1104			// Historically we only printed this information at
  1105			// calls. Keep doing so.
  1106			return
  1107		}
  1108		if live.IsEmpty() {
  1109			return
  1110		}
  1111	
  1112		pos := lv.fn.Func.Nname.Pos
  1113		if v != nil {
  1114			pos = v.Pos
  1115		}
  1116	
  1117		s := "live at "
  1118		if v == nil {
  1119			s += fmt.Sprintf("entry to %s:", lv.fn.funcname())
  1120		} else if sym, ok := v.Aux.(*obj.LSym); ok {
  1121			fn := sym.Name
  1122			if pos := strings.Index(fn, "."); pos >= 0 {
  1123				fn = fn[pos+1:]
  1124			}
  1125			s += fmt.Sprintf("call to %s:", fn)
  1126		} else {
  1127			s += "indirect call:"
  1128		}
  1129	
  1130		for j, n := range lv.vars {
  1131			if live.Get(int32(j)) {
  1132				s += fmt.Sprintf(" %v", n)
  1133			}
  1134		}
  1135	
  1136		Warnl(pos, s)
  1137	}
  1138	
  1139	func (lv *Liveness) printbvec(printed bool, name string, live varRegVec) bool {
  1140		if live.vars.IsEmpty() && live.regs == 0 {
  1141			return printed
  1142		}
  1143	
  1144		if !printed {
  1145			fmt.Printf("\t")
  1146		} else {
  1147			fmt.Printf(" ")
  1148		}
  1149		fmt.Printf("%s=", name)
  1150	
  1151		comma := ""
  1152		for i, n := range lv.vars {
  1153			if !live.vars.Get(int32(i)) {
  1154				continue
  1155			}
  1156			fmt.Printf("%s%s", comma, n.Sym.Name)
  1157			comma = ","
  1158		}
  1159		fmt.Printf("%s%s", comma, live.regs.niceString(lv.f.Config))
  1160		return true
  1161	}
  1162	
  1163	// printeffect is like printbvec, but for valueEffects and regEffects.
  1164	func (lv *Liveness) printeffect(printed bool, name string, pos int32, x bool, regMask liveRegMask) bool {
  1165		if !x && regMask == 0 {
  1166			return printed
  1167		}
  1168		if !printed {
  1169			fmt.Printf("\t")
  1170		} else {
  1171			fmt.Printf(" ")
  1172		}
  1173		fmt.Printf("%s=", name)
  1174		if x {
  1175			fmt.Printf("%s", lv.vars[pos].Sym.Name)
  1176		}
  1177		for j, reg := range lv.f.Config.GCRegMap {
  1178			if regMask&(1<<uint(j)) != 0 {
  1179				if x {
  1180					fmt.Printf(",")
  1181				}
  1182				x = true
  1183				fmt.Printf("%v", reg)
  1184			}
  1185		}
  1186		return true
  1187	}
  1188	
  1189	// Prints the computed liveness information and inputs, for debugging.
  1190	// This format synthesizes the information used during the multiple passes
  1191	// into a single presentation.
  1192	func (lv *Liveness) printDebug() {
  1193		fmt.Printf("liveness: %s\n", lv.fn.funcname())
  1194	
  1195		pcdata := 0
  1196		for i, b := range lv.f.Blocks {
  1197			if i > 0 {
  1198				fmt.Printf("\n")
  1199			}
  1200	
  1201			// bb#0 pred=1,2 succ=3,4
  1202			fmt.Printf("bb#%d pred=", b.ID)
  1203			for j, pred := range b.Preds {
  1204				if j > 0 {
  1205					fmt.Printf(",")
  1206				}
  1207				fmt.Printf("%d", pred.Block().ID)
  1208			}
  1209			fmt.Printf(" succ=")
  1210			for j, succ := range b.Succs {
  1211				if j > 0 {
  1212					fmt.Printf(",")
  1213				}
  1214				fmt.Printf("%d", succ.Block().ID)
  1215			}
  1216			fmt.Printf("\n")
  1217	
  1218			be := lv.blockEffects(b)
  1219	
  1220			// initial settings
  1221			printed := false
  1222			printed = lv.printbvec(printed, "uevar", be.uevar)
  1223			printed = lv.printbvec(printed, "livein", be.livein)
  1224			if printed {
  1225				fmt.Printf("\n")
  1226			}
  1227	
  1228			// program listing, with individual effects listed
  1229	
  1230			if b == lv.f.Entry {
  1231				live := lv.stackMaps[pcdata]
  1232				fmt.Printf("(%s) function entry\n", linestr(lv.fn.Func.Nname.Pos))
  1233				fmt.Printf("\tlive=")
  1234				printed = false
  1235				for j, n := range lv.vars {
  1236					if !live.Get(int32(j)) {
  1237						continue
  1238					}
  1239					if printed {
  1240						fmt.Printf(",")
  1241					}
  1242					fmt.Printf("%v", n)
  1243					printed = true
  1244				}
  1245				fmt.Printf("\n")
  1246			}
  1247	
  1248			for _, v := range b.Values {
  1249				fmt.Printf("(%s) %v\n", linestr(v.Pos), v.LongString())
  1250	
  1251				if pos := lv.livenessMap.Get(v); pos.Valid() {
  1252					pcdata = pos.stackMapIndex
  1253				}
  1254	
  1255				pos, effect := lv.valueEffects(v)
  1256				regUevar, regKill := lv.regEffects(v)
  1257				printed = false
  1258				printed = lv.printeffect(printed, "uevar", pos, effect&uevar != 0, regUevar)
  1259				printed = lv.printeffect(printed, "varkill", pos, effect&varkill != 0, regKill)
  1260				if printed {
  1261					fmt.Printf("\n")
  1262				}
  1263	
  1264				if !lv.issafepoint(v) {
  1265					continue
  1266				}
  1267	
  1268				live := lv.stackMaps[pcdata]
  1269				fmt.Printf("\tlive=")
  1270				printed = false
  1271				for j, n := range lv.vars {
  1272					if !live.Get(int32(j)) {
  1273						continue
  1274					}
  1275					if printed {
  1276						fmt.Printf(",")
  1277					}
  1278					fmt.Printf("%v", n)
  1279					printed = true
  1280				}
  1281				regLive := lv.regMaps[lv.livenessMap.Get(v).regMapIndex]
  1282				if regLive != 0 {
  1283					if printed {
  1284						fmt.Printf(",")
  1285					}
  1286					fmt.Printf("%s", regLive.niceString(lv.f.Config))
  1287				}
  1288				fmt.Printf("\n")
  1289			}
  1290	
  1291			// bb bitsets
  1292			fmt.Printf("end\n")
  1293			printed = false
  1294			printed = lv.printbvec(printed, "varkill", be.varkill)
  1295			printed = lv.printbvec(printed, "liveout", be.liveout)
  1296			if printed {
  1297				fmt.Printf("\n")
  1298			}
  1299		}
  1300	
  1301		fmt.Printf("\n")
  1302	}
  1303	
  1304	// Dumps a slice of bitmaps to a symbol as a sequence of uint32 values. The
  1305	// first word dumped is the total number of bitmaps. The second word is the
  1306	// length of the bitmaps. All bitmaps are assumed to be of equal length. The
  1307	// remaining bytes are the raw bitmaps.
  1308	func (lv *Liveness) emit() (argsSym, liveSym, regsSym *obj.LSym) {
  1309		// Size args bitmaps to be just large enough to hold the largest pointer.
  1310		// First, find the largest Xoffset node we care about.
  1311		// (Nodes without pointers aren't in lv.vars; see livenessShouldTrack.)
  1312		var maxArgNode *Node
  1313		for _, n := range lv.vars {
  1314			switch n.Class() {
  1315			case PPARAM, PPARAMOUT:
  1316				if maxArgNode == nil || n.Xoffset > maxArgNode.Xoffset {
  1317					maxArgNode = n
  1318				}
  1319			}
  1320		}
  1321		// Next, find the offset of the largest pointer in the largest node.
  1322		var maxArgs int64
  1323		if maxArgNode != nil {
  1324			maxArgs = maxArgNode.Xoffset + typeptrdata(maxArgNode.Type)
  1325		}
  1326	
  1327		// Size locals bitmaps to be stkptrsize sized.
  1328		// We cannot shrink them to only hold the largest pointer,
  1329		// because their size is used to calculate the beginning
  1330		// of the local variables frame.
  1331		// Further discussion in https://golang.org/cl/104175.
  1332		// TODO: consider trimming leading zeros.
  1333		// This would require shifting all bitmaps.
  1334		maxLocals := lv.stkptrsize
  1335	
  1336		// Temporary symbols for encoding bitmaps.
  1337		var argsSymTmp, liveSymTmp, regsSymTmp obj.LSym
  1338	
  1339		args := bvalloc(int32(maxArgs / int64(Widthptr)))
  1340		aoff := duint32(&argsSymTmp, 0, uint32(len(lv.stackMaps))) // number of bitmaps
  1341		aoff = duint32(&argsSymTmp, aoff, uint32(args.n))          // number of bits in each bitmap
  1342	
  1343		locals := bvalloc(int32(maxLocals / int64(Widthptr)))
  1344		loff := duint32(&liveSymTmp, 0, uint32(len(lv.stackMaps))) // number of bitmaps
  1345		loff = duint32(&liveSymTmp, loff, uint32(locals.n))        // number of bits in each bitmap
  1346	
  1347		for _, live := range lv.stackMaps {
  1348			args.Clear()
  1349			locals.Clear()
  1350	
  1351			lv.pointerMap(live, lv.vars, args, locals)
  1352	
  1353			aoff = dbvec(&argsSymTmp, aoff, args)
  1354			loff = dbvec(&liveSymTmp, loff, locals)
  1355		}
  1356	
  1357		regs := bvalloc(lv.usedRegs())
  1358		roff := duint32(&regsSymTmp, 0, uint32(len(lv.regMaps))) // number of bitmaps
  1359		roff = duint32(&regsSymTmp, roff, uint32(regs.n))        // number of bits in each bitmap
  1360		if regs.n > 32 {
  1361			// Our uint32 conversion below won't work.
  1362			Fatalf("GP registers overflow uint32")
  1363		}
  1364	
  1365		if regs.n > 0 {
  1366			for _, live := range lv.regMaps {
  1367				regs.Clear()
  1368				regs.b[0] = uint32(live)
  1369				roff = dbvec(&regsSymTmp, roff, regs)
  1370			}
  1371		}
  1372	
  1373		// Give these LSyms content-addressable names,
  1374		// so that they can be de-duplicated.
  1375		// This provides significant binary size savings.
  1376		//
  1377		// These symbols will be added to Ctxt.Data by addGCLocals
  1378		// after parallel compilation is done.
  1379		makeSym := func(tmpSym *obj.LSym) *obj.LSym {
  1380			return Ctxt.LookupInit(fmt.Sprintf("gclocals·%x", md5.Sum(tmpSym.P)), func(lsym *obj.LSym) {
  1381				lsym.P = tmpSym.P
  1382			})
  1383		}
  1384		return makeSym(&argsSymTmp), makeSym(&liveSymTmp), makeSym(&regsSymTmp)
  1385	}
  1386	
  1387	// Entry pointer for liveness analysis. Solves for the liveness of
  1388	// pointer variables in the function and emits a runtime data
  1389	// structure read by the garbage collector.
  1390	// Returns a map from GC safe points to their corresponding stack map index.
  1391	func liveness(e *ssafn, f *ssa.Func, pp *Progs) LivenessMap {
  1392		// Construct the global liveness state.
  1393		vars, idx := getvariables(e.curfn)
  1394		lv := newliveness(e.curfn, f, vars, idx, e.stkptrsize)
  1395	
  1396		// Run the dataflow framework.
  1397		lv.prologue()
  1398		lv.solve()
  1399		lv.epilogue()
  1400		if debuglive > 0 {
  1401			lv.showlive(nil, lv.stackMaps[0])
  1402			for _, b := range f.Blocks {
  1403				for _, val := range b.Values {
  1404					if idx := lv.livenessMap.Get(val); idx.Valid() {
  1405						lv.showlive(val, lv.stackMaps[idx.stackMapIndex])
  1406					}
  1407				}
  1408			}
  1409		}
  1410		if debuglive >= 2 {
  1411			lv.printDebug()
  1412		}
  1413	
  1414		// Update the function cache.
  1415		{
  1416			cache := f.Cache.Liveness.(*livenessFuncCache)
  1417			if cap(lv.be) < 2000 { // Threshold from ssa.Cache slices.
  1418				for i := range lv.be {
  1419					lv.be[i] = BlockEffects{}
  1420				}
  1421				cache.be = lv.be
  1422			}
  1423			if cap(lv.livenessMap.m) < 2000 {
  1424				cache.livenessMap = lv.livenessMap
  1425			}
  1426		}
  1427	
  1428		// Emit the live pointer map data structures
  1429		ls := e.curfn.Func.lsym
  1430		ls.Func.GCArgs, ls.Func.GCLocals, ls.Func.GCRegs = lv.emit()
  1431	
  1432		p := pp.Prog(obj.AFUNCDATA)
  1433		Addrconst(&p.From, objabi.FUNCDATA_ArgsPointerMaps)
  1434		p.To.Type = obj.TYPE_MEM
  1435		p.To.Name = obj.NAME_EXTERN
  1436		p.To.Sym = ls.Func.GCArgs
  1437	
  1438		p = pp.Prog(obj.AFUNCDATA)
  1439		Addrconst(&p.From, objabi.FUNCDATA_LocalsPointerMaps)
  1440		p.To.Type = obj.TYPE_MEM
  1441		p.To.Name = obj.NAME_EXTERN
  1442		p.To.Sym = ls.Func.GCLocals
  1443	
  1444		p = pp.Prog(obj.AFUNCDATA)
  1445		Addrconst(&p.From, objabi.FUNCDATA_RegPointerMaps)
  1446		p.To.Type = obj.TYPE_MEM
  1447		p.To.Name = obj.NAME_EXTERN
  1448		p.To.Sym = ls.Func.GCRegs
  1449	
  1450		return lv.livenessMap
  1451	}
  1452	

View as plain text