Source file src/cmd/compile/internal/liveness/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 liveness
    16  
    17  import (
    18  	"cmp"
    19  	"fmt"
    20  	"os"
    21  	"slices"
    22  	"sort"
    23  	"strings"
    24  
    25  	"cmd/compile/internal/abi"
    26  	"cmd/compile/internal/base"
    27  	"cmd/compile/internal/bitvec"
    28  	"cmd/compile/internal/ir"
    29  	"cmd/compile/internal/objw"
    30  	"cmd/compile/internal/reflectdata"
    31  	"cmd/compile/internal/ssa"
    32  	"cmd/compile/internal/typebits"
    33  	"cmd/compile/internal/types"
    34  	"cmd/internal/hash"
    35  	"cmd/internal/obj"
    36  	"cmd/internal/src"
    37  
    38  	rtabi "internal/abi"
    39  )
    40  
    41  // OpVarDef is an annotation for the liveness analysis, marking a place
    42  // where a complete initialization (definition) of a variable begins.
    43  // Since the liveness analysis can see initialization of single-word
    44  // variables quite easy, OpVarDef is only needed for multi-word
    45  // variables satisfying isfat(n.Type). For simplicity though, buildssa
    46  // emits OpVarDef regardless of variable width.
    47  //
    48  // An 'OpVarDef x' annotation in the instruction stream tells the liveness
    49  // analysis to behave as though the variable x is being initialized at that
    50  // point in the instruction stream. The OpVarDef must appear before the
    51  // actual (multi-instruction) initialization, and it must also appear after
    52  // any uses of the previous value, if any. For example, if compiling:
    53  //
    54  //	x = x[1:]
    55  //
    56  // it is important to generate code like:
    57  //
    58  //	base, len, cap = pieces of x[1:]
    59  //	OpVarDef x
    60  //	x = {base, len, cap}
    61  //
    62  // If instead the generated code looked like:
    63  //
    64  //	OpVarDef x
    65  //	base, len, cap = pieces of x[1:]
    66  //	x = {base, len, cap}
    67  //
    68  // then the liveness analysis would decide the previous value of x was
    69  // unnecessary even though it is about to be used by the x[1:] computation.
    70  // Similarly, if the generated code looked like:
    71  //
    72  //	base, len, cap = pieces of x[1:]
    73  //	x = {base, len, cap}
    74  //	OpVarDef x
    75  //
    76  // then the liveness analysis will not preserve the new value of x, because
    77  // the OpVarDef appears to have "overwritten" it.
    78  //
    79  // OpVarDef is a bit of a kludge to work around the fact that the instruction
    80  // stream is working on single-word values but the liveness analysis
    81  // wants to work on individual variables, which might be multi-word
    82  // aggregates. It might make sense at some point to look into letting
    83  // the liveness analysis work on single-word values as well, although
    84  // there are complications around interface values, slices, and strings,
    85  // all of which cannot be treated as individual words.
    86  
    87  // blockEffects summarizes the liveness effects on an SSA block.
    88  type blockEffects struct {
    89  	// Computed during Liveness.prologue using only the content of
    90  	// individual blocks:
    91  	//
    92  	//	uevar: upward exposed variables (used before set in block)
    93  	//	varkill: killed variables (set in block)
    94  	uevar   bitvec.BitVec
    95  	varkill bitvec.BitVec
    96  
    97  	// Computed during Liveness.solve using control flow information:
    98  	//
    99  	//	livein: variables live at block entry
   100  	//	liveout: variables live at block exit
   101  	livein  bitvec.BitVec
   102  	liveout bitvec.BitVec
   103  }
   104  
   105  // A collection of global state used by Liveness analysis.
   106  type Liveness struct {
   107  	fn         *ir.Func
   108  	f          *ssa.Func
   109  	vars       []*ir.Name
   110  	idx        map[*ir.Name]int32
   111  	stkptrsize int64
   112  
   113  	be []blockEffects
   114  
   115  	// allUnsafe indicates that all points in this function are
   116  	// unsafe-points.
   117  	allUnsafe bool
   118  	// unsafePoints bit i is set if Value ID i is an unsafe-point
   119  	// (preemption is not allowed). Only valid if !allUnsafe.
   120  	unsafePoints bitvec.BitVec
   121  	// unsafeBlocks bit i is set if Block ID i is an unsafe-point
   122  	// (preemption is not allowed on any end-of-block
   123  	// instructions). Only valid if !allUnsafe.
   124  	unsafeBlocks bitvec.BitVec
   125  
   126  	// An array with a bit vector for each safe point in the
   127  	// current Block during liveness.epilogue. Indexed in Value
   128  	// order for that block. Additionally, for the entry block
   129  	// livevars[0] is the entry bitmap. liveness.compact moves
   130  	// these to stackMaps.
   131  	livevars []bitvec.BitVec
   132  
   133  	// livenessMap maps from safe points (i.e., CALLs) to their
   134  	// liveness map indexes.
   135  	livenessMap Map
   136  	stackMapSet bvecSet
   137  	stackMaps   []bitvec.BitVec
   138  
   139  	cache progeffectscache
   140  
   141  	// partLiveArgs includes input arguments (PPARAM) that may
   142  	// be partially live. That is, it is considered live because
   143  	// a part of it is used, but we may not initialize all parts.
   144  	partLiveArgs map[*ir.Name]bool
   145  
   146  	doClobber     bool // Whether to clobber dead stack slots in this function.
   147  	noClobberArgs bool // Do not clobber function arguments
   148  
   149  	// treat "dead" writes as equivalent to reads during the analysis;
   150  	// used only during liveness analysis for stack slot merging (doesn't
   151  	// make sense for stackmap analysis).
   152  	conservativeWrites bool
   153  }
   154  
   155  // Map maps from *ssa.Value to StackMapIndex.
   156  // Also keeps track of unsafe ssa.Values and ssa.Blocks.
   157  // (unsafe = can't be interrupted during GC.)
   158  type Map struct {
   159  	Vals         map[ssa.ID]objw.StackMapIndex
   160  	UnsafeVals   map[ssa.ID]bool
   161  	UnsafeBlocks map[ssa.ID]bool
   162  	// The set of live, pointer-containing variables at the DeferReturn
   163  	// call (only set when open-coded defers are used).
   164  	DeferReturn objw.StackMapIndex
   165  }
   166  
   167  func (m *Map) reset() {
   168  	if m.Vals == nil {
   169  		m.Vals = make(map[ssa.ID]objw.StackMapIndex)
   170  		m.UnsafeVals = make(map[ssa.ID]bool)
   171  		m.UnsafeBlocks = make(map[ssa.ID]bool)
   172  	} else {
   173  		clear(m.Vals)
   174  		clear(m.UnsafeVals)
   175  		clear(m.UnsafeBlocks)
   176  	}
   177  	m.DeferReturn = objw.StackMapDontCare
   178  }
   179  
   180  func (m *Map) set(v *ssa.Value, i objw.StackMapIndex) {
   181  	m.Vals[v.ID] = i
   182  }
   183  func (m *Map) setUnsafeVal(v *ssa.Value) {
   184  	m.UnsafeVals[v.ID] = true
   185  }
   186  func (m *Map) setUnsafeBlock(b *ssa.Block) {
   187  	m.UnsafeBlocks[b.ID] = true
   188  }
   189  
   190  func (m Map) Get(v *ssa.Value) objw.StackMapIndex {
   191  	// If v isn't in the map, then it's a "don't care".
   192  	if idx, ok := m.Vals[v.ID]; ok {
   193  		return idx
   194  	}
   195  	return objw.StackMapDontCare
   196  }
   197  func (m Map) GetUnsafe(v *ssa.Value) bool {
   198  	// default is safe
   199  	return m.UnsafeVals[v.ID]
   200  }
   201  func (m Map) GetUnsafeBlock(b *ssa.Block) bool {
   202  	// default is safe
   203  	return m.UnsafeBlocks[b.ID]
   204  }
   205  
   206  type progeffectscache struct {
   207  	retuevar    []int32
   208  	tailuevar   []int32
   209  	initialized bool
   210  }
   211  
   212  // shouldTrack reports whether the liveness analysis
   213  // should track the variable n.
   214  // We don't care about variables that have no pointers,
   215  // nor do we care about non-local variables,
   216  // nor do we care about empty structs (handled by the pointer check),
   217  // nor do we care about the fake PAUTOHEAP variables.
   218  func shouldTrack(n *ir.Name) bool {
   219  	return (n.Class == ir.PAUTO && n.Esc() != ir.EscHeap || n.Class == ir.PPARAM || n.Class == ir.PPARAMOUT) && n.Type().HasPointers()
   220  }
   221  
   222  // getvariables returns the list of on-stack variables that we need to track
   223  // and a map for looking up indices by *Node.
   224  func getvariables(fn *ir.Func) ([]*ir.Name, map[*ir.Name]int32) {
   225  	var vars []*ir.Name
   226  	for _, n := range fn.Dcl {
   227  		if shouldTrack(n) {
   228  			vars = append(vars, n)
   229  		}
   230  	}
   231  	idx := make(map[*ir.Name]int32, len(vars))
   232  	for i, n := range vars {
   233  		idx[n] = int32(i)
   234  	}
   235  	return vars, idx
   236  }
   237  
   238  func (lv *Liveness) initcache() {
   239  	if lv.cache.initialized {
   240  		base.Fatalf("liveness cache initialized twice")
   241  		return
   242  	}
   243  	lv.cache.initialized = true
   244  
   245  	for i, node := range lv.vars {
   246  		switch node.Class {
   247  		case ir.PPARAM:
   248  			// A return instruction with a p.to is a tail return, which brings
   249  			// the stack pointer back up (if it ever went down) and then jumps
   250  			// to a new function entirely. That form of instruction must read
   251  			// all the parameters for correctness, and similarly it must not
   252  			// read the out arguments - they won't be set until the new
   253  			// function runs.
   254  			lv.cache.tailuevar = append(lv.cache.tailuevar, int32(i))
   255  
   256  		case ir.PPARAMOUT:
   257  			// All results are live at every return point.
   258  			// Note that this point is after escaping return values
   259  			// are copied back to the stack using their PAUTOHEAP references.
   260  			lv.cache.retuevar = append(lv.cache.retuevar, int32(i))
   261  		}
   262  	}
   263  }
   264  
   265  // A liveEffect is a set of flags that describe an instruction's
   266  // liveness effects on a variable.
   267  //
   268  // The possible flags are:
   269  //
   270  //	uevar - used by the instruction
   271  //	varkill - killed by the instruction (set)
   272  //
   273  // A kill happens after the use (for an instruction that updates a value, for example).
   274  type liveEffect int
   275  
   276  const (
   277  	uevar liveEffect = 1 << iota
   278  	varkill
   279  )
   280  
   281  // valueEffects returns the index of a variable in lv.vars and the
   282  // liveness effects v has on that variable.
   283  // If v does not affect any tracked variables, it returns -1, 0.
   284  func (lv *Liveness) valueEffects(v *ssa.Value) (int32, liveEffect) {
   285  	n, e := affectedVar(v)
   286  	if e == 0 || n == nil { // cheapest checks first
   287  		return -1, 0
   288  	}
   289  	// AllocFrame has dropped unused variables from
   290  	// lv.fn.Func.Dcl, but they might still be referenced by
   291  	// OpVarFoo pseudo-ops. Ignore them to prevent "lost track of
   292  	// variable" ICEs (issue 19632).
   293  	switch v.Op {
   294  	case ssa.OpVarDef, ssa.OpVarLive, ssa.OpKeepAlive:
   295  		if !n.Used() {
   296  			return -1, 0
   297  		}
   298  	}
   299  
   300  	if n.Class == ir.PPARAM && !n.Addrtaken() && n.Type().Size() > int64(types.PtrSize) {
   301  		// Only aggregate-typed arguments that are not address-taken can be
   302  		// partially live.
   303  		lv.partLiveArgs[n] = true
   304  	}
   305  
   306  	var effect liveEffect
   307  	// Read is a read, obviously.
   308  	//
   309  	// Addr is a read also, as any subsequent holder of the pointer must be able
   310  	// to see all the values (including initialization) written so far.
   311  	// This also prevents a variable from "coming back from the dead" and presenting
   312  	// stale pointers to the garbage collector. See issue 28445.
   313  	if e&(ssa.SymRead|ssa.SymAddr) != 0 {
   314  		effect |= uevar
   315  	}
   316  	if e&ssa.SymWrite != 0 {
   317  		if !isfat(n.Type()) || v.Op == ssa.OpVarDef {
   318  			effect |= varkill
   319  		} else if lv.conservativeWrites {
   320  			effect |= uevar
   321  		}
   322  	}
   323  
   324  	if effect == 0 {
   325  		return -1, 0
   326  	}
   327  
   328  	if pos, ok := lv.idx[n]; ok {
   329  		return pos, effect
   330  	}
   331  	return -1, 0
   332  }
   333  
   334  // affectedVar returns the *ir.Name node affected by v.
   335  func affectedVar(v *ssa.Value) (*ir.Name, ssa.SymEffect) {
   336  	// Special cases.
   337  	switch v.Op {
   338  	case ssa.OpLoadReg:
   339  		n, _ := ssa.AutoVar(v.Args[0])
   340  		return n, ssa.SymRead
   341  	case ssa.OpStoreReg:
   342  		n, _ := ssa.AutoVar(v)
   343  		return n, ssa.SymWrite
   344  
   345  	case ssa.OpArgIntReg:
   346  		// This forces the spill slot for the register to be live at function entry.
   347  		// one of the following holds for a function F with pointer-valued register arg X:
   348  		//  0. No GC (so an uninitialized spill slot is okay)
   349  		//  1. GC at entry of F.  GC is precise, but the spills around morestack initialize X's spill slot
   350  		//  2. Stack growth at entry of F.  Same as GC.
   351  		//  3. GC occurs within F itself.  This has to be from preemption, and thus GC is conservative.
   352  		//     a. X is in a register -- then X is seen, and the spill slot is also scanned conservatively.
   353  		//     b. X is spilled -- the spill slot is initialized, and scanned conservatively
   354  		//     c. X is not live -- the spill slot is scanned conservatively, and it may contain X from an earlier spill.
   355  		//  4. GC within G, transitively called from F
   356  		//    a. X is live at call site, therefore is spilled, to its spill slot (which is live because of subsequent LoadReg).
   357  		//    b. X is not live at call site -- but neither is its spill slot.
   358  		n, _ := ssa.AutoVar(v)
   359  		return n, ssa.SymRead
   360  
   361  	case ssa.OpVarLive:
   362  		return v.Aux.(*ir.Name), ssa.SymRead
   363  	case ssa.OpVarDef:
   364  		return v.Aux.(*ir.Name), ssa.SymWrite
   365  	case ssa.OpKeepAlive:
   366  		n, _ := ssa.AutoVar(v.Args[0])
   367  		return n, ssa.SymRead
   368  	}
   369  
   370  	e := v.Op.SymEffect()
   371  	if e == 0 {
   372  		return nil, 0
   373  	}
   374  
   375  	switch a := v.Aux.(type) {
   376  	case nil, *obj.LSym:
   377  		// ok, but no node
   378  		return nil, e
   379  	case *ir.Name:
   380  		return a, e
   381  	default:
   382  		base.Fatalf("weird aux: %s", v.LongString())
   383  		return nil, e
   384  	}
   385  }
   386  
   387  type livenessFuncCache struct {
   388  	be          []blockEffects
   389  	livenessMap Map
   390  }
   391  
   392  // Constructs a new liveness structure used to hold the global state of the
   393  // liveness computation. The cfg argument is a slice of *BasicBlocks and the
   394  // vars argument is a slice of *Nodes.
   395  func newliveness(fn *ir.Func, f *ssa.Func, vars []*ir.Name, idx map[*ir.Name]int32, stkptrsize int64) *Liveness {
   396  	lv := &Liveness{
   397  		fn:         fn,
   398  		f:          f,
   399  		vars:       vars,
   400  		idx:        idx,
   401  		stkptrsize: stkptrsize,
   402  	}
   403  
   404  	// Significant sources of allocation are kept in the ssa.Cache
   405  	// and reused. Surprisingly, the bit vectors themselves aren't
   406  	// a major source of allocation, but the liveness maps are.
   407  	if lc, _ := f.Cache.Liveness.(*livenessFuncCache); lc == nil {
   408  		// Prep the cache so liveness can fill it later.
   409  		f.Cache.Liveness = new(livenessFuncCache)
   410  	} else {
   411  		if cap(lc.be) >= f.NumBlocks() {
   412  			lv.be = lc.be[:f.NumBlocks()]
   413  		}
   414  		lv.livenessMap = Map{
   415  			Vals:         lc.livenessMap.Vals,
   416  			UnsafeVals:   lc.livenessMap.UnsafeVals,
   417  			UnsafeBlocks: lc.livenessMap.UnsafeBlocks,
   418  			DeferReturn:  objw.StackMapDontCare,
   419  		}
   420  		lc.livenessMap.Vals = nil
   421  		lc.livenessMap.UnsafeVals = nil
   422  		lc.livenessMap.UnsafeBlocks = nil
   423  	}
   424  	if lv.be == nil {
   425  		lv.be = make([]blockEffects, f.NumBlocks())
   426  	}
   427  
   428  	nblocks := int32(len(f.Blocks))
   429  	nvars := int32(len(vars))
   430  	bulk := bitvec.NewBulk(nvars, nblocks*7, fn.Pos())
   431  	for _, b := range f.Blocks {
   432  		be := lv.blockEffects(b)
   433  
   434  		be.uevar = bulk.Next()
   435  		be.varkill = bulk.Next()
   436  		be.livein = bulk.Next()
   437  		be.liveout = bulk.Next()
   438  	}
   439  	lv.livenessMap.reset()
   440  
   441  	lv.markUnsafePoints()
   442  
   443  	lv.partLiveArgs = make(map[*ir.Name]bool)
   444  
   445  	lv.enableClobber()
   446  
   447  	return lv
   448  }
   449  
   450  func (lv *Liveness) blockEffects(b *ssa.Block) *blockEffects {
   451  	return &lv.be[b.ID]
   452  }
   453  
   454  // Generates live pointer value maps for arguments and local variables. The
   455  // this argument and the in arguments are always assumed live. The vars
   456  // argument is a slice of *Nodes.
   457  func (lv *Liveness) pointerMap(liveout bitvec.BitVec, vars []*ir.Name, args, locals bitvec.BitVec) {
   458  	var slotsSeen map[int64]*ir.Name
   459  	checkForDuplicateSlots := base.Debug.MergeLocals != 0
   460  	if checkForDuplicateSlots {
   461  		slotsSeen = make(map[int64]*ir.Name)
   462  	}
   463  	for i := int32(0); ; i++ {
   464  		i = liveout.Next(i)
   465  		if i < 0 {
   466  			break
   467  		}
   468  		node := vars[i]
   469  		switch node.Class {
   470  		case ir.PPARAM, ir.PPARAMOUT:
   471  			if !node.IsOutputParamInRegisters() {
   472  				if node.FrameOffset() < 0 {
   473  					lv.f.Fatalf("Node %v has frameoffset %d\n", node.Sym().Name, node.FrameOffset())
   474  				}
   475  				typebits.SetNoCheck(node.Type(), node.FrameOffset(), args)
   476  				break
   477  			}
   478  			fallthrough // PPARAMOUT in registers acts memory-allocates like an AUTO
   479  		case ir.PAUTO:
   480  			if checkForDuplicateSlots {
   481  				if prev, ok := slotsSeen[node.FrameOffset()]; ok {
   482  					base.FatalfAt(node.Pos(), "two vars live at pointerMap generation: %q and %q", prev.Sym().Name, node.Sym().Name)
   483  				}
   484  				slotsSeen[node.FrameOffset()] = node
   485  			}
   486  			typebits.Set(node.Type(), node.FrameOffset()+lv.stkptrsize, locals)
   487  		}
   488  	}
   489  }
   490  
   491  // IsUnsafe indicates that all points in this function are
   492  // unsafe-points.
   493  func IsUnsafe(f *ssa.Func) bool {
   494  	// The runtime assumes the only safe-points are function
   495  	// prologues (because that's how it used to be). We could and
   496  	// should improve that, but for now keep consider all points
   497  	// in the runtime unsafe. obj will add prologues and their
   498  	// safe-points.
   499  	//
   500  	// go:nosplit functions are similar. Since safe points used to
   501  	// be coupled with stack checks, go:nosplit often actually
   502  	// means "no safe points in this function".
   503  	return base.Flag.CompilingRuntime || f.NoSplit
   504  }
   505  
   506  // markUnsafePoints finds unsafe points and computes lv.unsafePoints.
   507  func (lv *Liveness) markUnsafePoints() {
   508  	if IsUnsafe(lv.f) {
   509  		// No complex analysis necessary.
   510  		lv.allUnsafe = true
   511  		return
   512  	}
   513  
   514  	lv.unsafePoints = bitvec.New(int32(lv.f.NumValues()))
   515  	lv.unsafeBlocks = bitvec.New(int32(lv.f.NumBlocks()))
   516  
   517  	// Mark architecture-specific unsafe points.
   518  	for _, b := range lv.f.Blocks {
   519  		for _, v := range b.Values {
   520  			if v.Op.UnsafePoint() {
   521  				lv.unsafePoints.Set(int32(v.ID))
   522  			}
   523  		}
   524  	}
   525  
   526  	for _, b := range lv.f.Blocks {
   527  		for _, v := range b.Values {
   528  			if v.Op != ssa.OpWBend {
   529  				continue
   530  			}
   531  			// WBend appears at the start of a block, like this:
   532  			//    ...
   533  			//    if wbEnabled: goto C else D
   534  			// C:
   535  			//    ... some write barrier enabled code ...
   536  			//    goto B
   537  			// D:
   538  			//    ... some write barrier disabled code ...
   539  			//    goto B
   540  			// B:
   541  			//    m1 = Phi mem_C mem_D
   542  			//    m2 = store operation ... m1
   543  			//    m3 = store operation ... m2
   544  			//    m4 = WBend m3
   545  
   546  			// Find first memory op in the block, which should be a Phi.
   547  			m := v
   548  			for {
   549  				m = m.MemoryArg()
   550  				if m.Block != b {
   551  					lv.f.Fatalf("can't find Phi before write barrier end mark %v", v)
   552  				}
   553  				if m.Op == ssa.OpPhi {
   554  					break
   555  				}
   556  			}
   557  			// Find the two predecessor blocks (write barrier on and write barrier off)
   558  			if len(m.Args) != 2 {
   559  				lv.f.Fatalf("phi before write barrier end mark has %d args, want 2", len(m.Args))
   560  			}
   561  			c := b.Preds[0].Block()
   562  			d := b.Preds[1].Block()
   563  
   564  			// Find their common predecessor block (the one that branches based on wb on/off).
   565  			// It might be a diamond pattern, or one of the blocks in the diamond pattern might
   566  			// be missing.
   567  			var decisionBlock *ssa.Block
   568  			if len(c.Preds) == 1 && c.Preds[0].Block() == d {
   569  				decisionBlock = d
   570  			} else if len(d.Preds) == 1 && d.Preds[0].Block() == c {
   571  				decisionBlock = c
   572  			} else if len(c.Preds) == 1 && len(d.Preds) == 1 && c.Preds[0].Block() == d.Preds[0].Block() {
   573  				decisionBlock = c.Preds[0].Block()
   574  			} else {
   575  				lv.f.Fatalf("can't find write barrier pattern %v", v)
   576  			}
   577  			if len(decisionBlock.Succs) != 2 {
   578  				lv.f.Fatalf("common predecessor block the wrong type %s", decisionBlock.Kind)
   579  			}
   580  
   581  			// Flow backwards from the control value to find the
   582  			// flag load. We don't know what lowered ops we're
   583  			// looking for, but all current arches produce a
   584  			// single op that does the memory load from the flag
   585  			// address, so we look for that.
   586  			var load *ssa.Value
   587  			v := decisionBlock.Controls[0]
   588  			for {
   589  				if v.MemoryArg() != nil {
   590  					// Single instruction to load (and maybe compare) the write barrier flag.
   591  					if sym, ok := v.Aux.(*obj.LSym); ok && sym == ir.Syms.WriteBarrier {
   592  						load = v
   593  						break
   594  					}
   595  					// Some architectures have to materialize the address separate from
   596  					// the load.
   597  					if sym, ok := v.Args[0].Aux.(*obj.LSym); ok && sym == ir.Syms.WriteBarrier {
   598  						load = v
   599  						break
   600  					}
   601  					v.Fatalf("load of write barrier flag not from correct global: %s", v.LongString())
   602  				}
   603  				// Common case: just flow backwards.
   604  				if len(v.Args) == 1 || len(v.Args) == 2 && v.Args[0] == v.Args[1] {
   605  					// Note: 386 lowers Neq32 to (TESTL cond cond),
   606  					v = v.Args[0]
   607  					continue
   608  				}
   609  				v.Fatalf("write barrier control value has more than one argument: %s", v.LongString())
   610  			}
   611  
   612  			// Mark everything after the load unsafe.
   613  			found := false
   614  			for _, v := range decisionBlock.Values {
   615  				if found {
   616  					lv.unsafePoints.Set(int32(v.ID))
   617  				}
   618  				found = found || v == load
   619  			}
   620  			lv.unsafeBlocks.Set(int32(decisionBlock.ID))
   621  
   622  			// Mark the write barrier on/off blocks as unsafe.
   623  			for _, e := range decisionBlock.Succs {
   624  				x := e.Block()
   625  				if x == b {
   626  					continue
   627  				}
   628  				for _, v := range x.Values {
   629  					lv.unsafePoints.Set(int32(v.ID))
   630  				}
   631  				lv.unsafeBlocks.Set(int32(x.ID))
   632  			}
   633  
   634  			// Mark from the join point up to the WBend as unsafe.
   635  			for _, v := range b.Values {
   636  				if v.Op == ssa.OpWBend {
   637  					break
   638  				}
   639  				lv.unsafePoints.Set(int32(v.ID))
   640  			}
   641  		}
   642  	}
   643  }
   644  
   645  // Returns true for instructions that must have a stack map.
   646  //
   647  // This does not necessarily mean the instruction is a safe-point. In
   648  // particular, call Values can have a stack map in case the callee
   649  // grows the stack, but not themselves be a safe-point.
   650  func (lv *Liveness) hasStackMap(v *ssa.Value) bool {
   651  	if !v.Op.IsCall() {
   652  		return false
   653  	}
   654  	// wbZero and wbCopy are write barriers and
   655  	// deeply non-preemptible. They are unsafe points and
   656  	// hence should not have liveness maps.
   657  	if sym, ok := v.Aux.(*ssa.AuxCall); ok && (sym.Fn == ir.Syms.WBZero || sym.Fn == ir.Syms.WBMove) {
   658  		return false
   659  	}
   660  	return true
   661  }
   662  
   663  // Initializes the sets for solving the live variables. Visits all the
   664  // instructions in each basic block to summarizes the information at each basic
   665  // block
   666  func (lv *Liveness) prologue() {
   667  	lv.initcache()
   668  
   669  	for _, b := range lv.f.Blocks {
   670  		be := lv.blockEffects(b)
   671  
   672  		// Walk the block instructions backward and update the block
   673  		// effects with the each prog effects.
   674  		for j := len(b.Values) - 1; j >= 0; j-- {
   675  			pos, e := lv.valueEffects(b.Values[j])
   676  			if e&varkill != 0 {
   677  				be.varkill.Set(pos)
   678  				be.uevar.Unset(pos)
   679  			}
   680  			if e&uevar != 0 {
   681  				be.uevar.Set(pos)
   682  			}
   683  		}
   684  	}
   685  }
   686  
   687  // Solve the liveness dataflow equations.
   688  func (lv *Liveness) solve() {
   689  	// These temporary bitvectors exist to avoid successive allocations and
   690  	// frees within the loop.
   691  	nvars := int32(len(lv.vars))
   692  	newlivein := bitvec.New(nvars)
   693  	newliveout := bitvec.New(nvars)
   694  
   695  	// Walk blocks in postorder ordering. This improves convergence.
   696  	po := lv.f.Postorder()
   697  
   698  	// Iterate through the blocks in reverse round-robin fashion. A work
   699  	// queue might be slightly faster. As is, the number of iterations is
   700  	// so low that it hardly seems to be worth the complexity.
   701  
   702  	for change := true; change; {
   703  		change = false
   704  		for _, b := range po {
   705  			be := lv.blockEffects(b)
   706  
   707  			newliveout.Clear()
   708  			switch b.Kind {
   709  			case ssa.BlockRet:
   710  				for _, pos := range lv.cache.retuevar {
   711  					newliveout.Set(pos)
   712  				}
   713  			case ssa.BlockRetJmp:
   714  				for _, pos := range lv.cache.tailuevar {
   715  					newliveout.Set(pos)
   716  				}
   717  			case ssa.BlockExit:
   718  				// panic exit - nothing to do
   719  			default:
   720  				// A variable is live on output from this block
   721  				// if it is live on input to some successor.
   722  				//
   723  				// out[b] = \bigcup_{s \in succ[b]} in[s]
   724  				newliveout.Copy(lv.blockEffects(b.Succs[0].Block()).livein)
   725  				for _, succ := range b.Succs[1:] {
   726  					newliveout.Or(newliveout, lv.blockEffects(succ.Block()).livein)
   727  				}
   728  			}
   729  
   730  			if !be.liveout.Eq(newliveout) {
   731  				change = true
   732  				be.liveout.Copy(newliveout)
   733  			}
   734  
   735  			// A variable is live on input to this block
   736  			// if it is used by this block, or live on output from this block and
   737  			// not set by the code in this block.
   738  			//
   739  			// in[b] = uevar[b] \cup (out[b] \setminus varkill[b])
   740  			newlivein.AndNot(be.liveout, be.varkill)
   741  			be.livein.Or(newlivein, be.uevar)
   742  		}
   743  	}
   744  }
   745  
   746  // Visits all instructions in a basic block and computes a bit vector of live
   747  // variables at each safe point locations.
   748  func (lv *Liveness) epilogue() {
   749  	nvars := int32(len(lv.vars))
   750  	liveout := bitvec.New(nvars)
   751  	livedefer := bitvec.New(nvars) // always-live variables
   752  
   753  	// If there is a defer (that could recover), then all output
   754  	// parameters are live all the time.  In addition, any locals
   755  	// that are pointers to heap-allocated output parameters are
   756  	// also always live (post-deferreturn code needs these
   757  	// pointers to copy values back to the stack).
   758  	// TODO: if the output parameter is heap-allocated, then we
   759  	// don't need to keep the stack copy live?
   760  	if lv.fn.HasDefer() {
   761  		for i, n := range lv.vars {
   762  			if n.Class == ir.PPARAMOUT {
   763  				if n.IsOutputParamHeapAddr() {
   764  					// Just to be paranoid.  Heap addresses are PAUTOs.
   765  					base.Fatalf("variable %v both output param and heap output param", n)
   766  				}
   767  				if n.Heapaddr != nil {
   768  					// If this variable moved to the heap, then
   769  					// its stack copy is not live.
   770  					continue
   771  				}
   772  				// Note: zeroing is handled by zeroResults in walk.go.
   773  				livedefer.Set(int32(i))
   774  			}
   775  			if n.IsOutputParamHeapAddr() {
   776  				// This variable will be overwritten early in the function
   777  				// prologue (from the result of a mallocgc) but we need to
   778  				// zero it in case that malloc causes a stack scan.
   779  				n.SetNeedzero(true)
   780  				livedefer.Set(int32(i))
   781  			}
   782  			if n.OpenDeferSlot() {
   783  				// Open-coded defer args slots must be live
   784  				// everywhere in a function, since a panic can
   785  				// occur (almost) anywhere. Because it is live
   786  				// everywhere, it must be zeroed on entry.
   787  				livedefer.Set(int32(i))
   788  				// It was already marked as Needzero when created.
   789  				if !n.Needzero() {
   790  					base.Fatalf("all pointer-containing defer arg slots should have Needzero set")
   791  				}
   792  			}
   793  		}
   794  	}
   795  
   796  	// We must analyze the entry block first. The runtime assumes
   797  	// the function entry map is index 0. Conveniently, layout
   798  	// already ensured that the entry block is first.
   799  	if lv.f.Entry != lv.f.Blocks[0] {
   800  		lv.f.Fatalf("entry block must be first")
   801  	}
   802  
   803  	{
   804  		// Reserve an entry for function entry.
   805  		live := bitvec.New(nvars)
   806  		lv.livevars = append(lv.livevars, live)
   807  	}
   808  
   809  	for _, b := range lv.f.Blocks {
   810  		be := lv.blockEffects(b)
   811  
   812  		// Walk forward through the basic block instructions and
   813  		// allocate liveness maps for those instructions that need them.
   814  		for _, v := range b.Values {
   815  			if !lv.hasStackMap(v) {
   816  				continue
   817  			}
   818  
   819  			live := bitvec.New(nvars)
   820  			lv.livevars = append(lv.livevars, live)
   821  		}
   822  
   823  		// walk backward, construct maps at each safe point
   824  		index := int32(len(lv.livevars) - 1)
   825  
   826  		liveout.Copy(be.liveout)
   827  		for i := len(b.Values) - 1; i >= 0; i-- {
   828  			v := b.Values[i]
   829  
   830  			if lv.hasStackMap(v) {
   831  				// Found an interesting instruction, record the
   832  				// corresponding liveness information.
   833  
   834  				live := &lv.livevars[index]
   835  				live.Or(*live, liveout)
   836  				live.Or(*live, livedefer) // only for non-entry safe points
   837  				index--
   838  			}
   839  
   840  			// Update liveness information.
   841  			pos, e := lv.valueEffects(v)
   842  			if e&varkill != 0 {
   843  				liveout.Unset(pos)
   844  			}
   845  			if e&uevar != 0 {
   846  				liveout.Set(pos)
   847  			}
   848  		}
   849  
   850  		if b == lv.f.Entry {
   851  			if index != 0 {
   852  				base.Fatalf("bad index for entry point: %v", index)
   853  			}
   854  
   855  			// Check to make sure only input variables are live.
   856  			for i, n := range lv.vars {
   857  				if !liveout.Get(int32(i)) {
   858  					continue
   859  				}
   860  				if n.Class == ir.PPARAM {
   861  					continue // ok
   862  				}
   863  				base.FatalfAt(n.Pos(), "bad live variable at entry of %v: %L", lv.fn.Nname, n)
   864  			}
   865  
   866  			// Record live variables.
   867  			live := &lv.livevars[index]
   868  			live.Or(*live, liveout)
   869  		}
   870  
   871  		if lv.doClobber {
   872  			lv.clobber(b)
   873  		}
   874  
   875  		// The liveness maps for this block are now complete. Compact them.
   876  		lv.compact(b)
   877  	}
   878  
   879  	// If we have an open-coded deferreturn call, make a liveness map for it.
   880  	if lv.fn.OpenCodedDeferDisallowed() {
   881  		lv.livenessMap.DeferReturn = objw.StackMapDontCare
   882  	} else {
   883  		idx, _ := lv.stackMapSet.add(livedefer)
   884  		lv.livenessMap.DeferReturn = objw.StackMapIndex(idx)
   885  	}
   886  
   887  	// Done compacting. Throw out the stack map set.
   888  	lv.stackMaps = lv.stackMapSet.extractUnique()
   889  	lv.stackMapSet = bvecSet{}
   890  
   891  	// Useful sanity check: on entry to the function,
   892  	// the only things that can possibly be live are the
   893  	// input parameters.
   894  	for j, n := range lv.vars {
   895  		if n.Class != ir.PPARAM && lv.stackMaps[0].Get(int32(j)) {
   896  			lv.f.Fatalf("%v %L recorded as live on entry", lv.fn.Nname, n)
   897  		}
   898  	}
   899  }
   900  
   901  // Compact coalesces identical bitmaps from lv.livevars into the sets
   902  // lv.stackMapSet.
   903  //
   904  // Compact clears lv.livevars.
   905  //
   906  // There are actually two lists of bitmaps, one list for the local variables and one
   907  // list for the function arguments. Both lists are indexed by the same PCDATA
   908  // index, so the corresponding pairs must be considered together when
   909  // merging duplicates. The argument bitmaps change much less often during
   910  // function execution than the local variable bitmaps, so it is possible that
   911  // we could introduce a separate PCDATA index for arguments vs locals and
   912  // then compact the set of argument bitmaps separately from the set of
   913  // local variable bitmaps. As of 2014-04-02, doing this to the godoc binary
   914  // is actually a net loss: we save about 50k of argument bitmaps but the new
   915  // PCDATA tables cost about 100k. So for now we keep using a single index for
   916  // both bitmap lists.
   917  func (lv *Liveness) compact(b *ssa.Block) {
   918  	pos := 0
   919  	if b == lv.f.Entry {
   920  		// Handle entry stack map.
   921  		lv.stackMapSet.add(lv.livevars[0])
   922  		pos++
   923  	}
   924  	for _, v := range b.Values {
   925  		if lv.hasStackMap(v) {
   926  			idx, _ := lv.stackMapSet.add(lv.livevars[pos])
   927  			pos++
   928  			lv.livenessMap.set(v, objw.StackMapIndex(idx))
   929  		}
   930  		if lv.allUnsafe || v.Op != ssa.OpClobber && lv.unsafePoints.Get(int32(v.ID)) {
   931  			lv.livenessMap.setUnsafeVal(v)
   932  		}
   933  	}
   934  	if lv.allUnsafe || lv.unsafeBlocks.Get(int32(b.ID)) {
   935  		lv.livenessMap.setUnsafeBlock(b)
   936  	}
   937  
   938  	// Reset livevars.
   939  	lv.livevars = lv.livevars[:0]
   940  }
   941  
   942  func (lv *Liveness) enableClobber() {
   943  	// The clobberdead experiment inserts code to clobber pointer slots in all
   944  	// the dead variables (locals and args) at every synchronous safepoint.
   945  	if !base.Flag.ClobberDead {
   946  		return
   947  	}
   948  	if lv.fn.Pragma&ir.CgoUnsafeArgs != 0 {
   949  		// C or assembly code uses the exact frame layout. Don't clobber.
   950  		return
   951  	}
   952  	if len(lv.vars) > 10000 || len(lv.f.Blocks) > 10000 {
   953  		// Be careful to avoid doing too much work.
   954  		// Bail if >10000 variables or >10000 blocks.
   955  		// Otherwise, giant functions make this experiment generate too much code.
   956  		return
   957  	}
   958  	if lv.f.Name == "forkAndExecInChild" {
   959  		// forkAndExecInChild calls vfork on some platforms.
   960  		// The code we add here clobbers parts of the stack in the child.
   961  		// When the parent resumes, it is using the same stack frame. But the
   962  		// child has clobbered stack variables that the parent needs. Boom!
   963  		// In particular, the sys argument gets clobbered.
   964  		return
   965  	}
   966  	if lv.f.Name == "wbBufFlush" ||
   967  		((lv.f.Name == "callReflect" || lv.f.Name == "callMethod") && lv.fn.ABIWrapper()) {
   968  		// runtime.wbBufFlush must not modify its arguments. See the comments
   969  		// in runtime/mwbbuf.go:wbBufFlush.
   970  		//
   971  		// reflect.callReflect and reflect.callMethod are called from special
   972  		// functions makeFuncStub and methodValueCall. The runtime expects
   973  		// that it can find the first argument (ctxt) at 0(SP) in makeFuncStub
   974  		// and methodValueCall's frame (see runtime/traceback.go:getArgInfo).
   975  		// Normally callReflect and callMethod already do not modify the
   976  		// argument, and keep it alive. But the compiler-generated ABI wrappers
   977  		// don't do that. Special case the wrappers to not clobber its arguments.
   978  		lv.noClobberArgs = true
   979  	}
   980  	if h := os.Getenv("GOCLOBBERDEADHASH"); h != "" {
   981  		// Clobber only functions where the hash of the function name matches a pattern.
   982  		// Useful for binary searching for a miscompiled function.
   983  		hstr := ""
   984  		for _, b := range hash.Sum32([]byte(lv.f.Name)) {
   985  			hstr += fmt.Sprintf("%08b", b)
   986  		}
   987  		if !strings.HasSuffix(hstr, h) {
   988  			return
   989  		}
   990  		fmt.Printf("\t\t\tCLOBBERDEAD %s\n", lv.f.Name)
   991  	}
   992  	lv.doClobber = true
   993  }
   994  
   995  // Inserts code to clobber pointer slots in all the dead variables (locals and args)
   996  // at every synchronous safepoint in b.
   997  func (lv *Liveness) clobber(b *ssa.Block) {
   998  	// Copy block's values to a temporary.
   999  	oldSched := append([]*ssa.Value{}, b.Values...)
  1000  	b.Values = b.Values[:0]
  1001  	idx := 0
  1002  
  1003  	// Clobber pointer slots in all dead variables at entry.
  1004  	if b == lv.f.Entry {
  1005  		for len(oldSched) > 0 && len(oldSched[0].Args) == 0 {
  1006  			// Skip argless ops. We need to skip at least
  1007  			// the lowered ClosurePtr op, because it
  1008  			// really wants to be first. This will also
  1009  			// skip ops like InitMem and SP, which are ok.
  1010  			b.Values = append(b.Values, oldSched[0])
  1011  			oldSched = oldSched[1:]
  1012  		}
  1013  		clobber(lv, b, lv.livevars[0])
  1014  		idx++
  1015  	}
  1016  
  1017  	// Copy values into schedule, adding clobbering around safepoints.
  1018  	for _, v := range oldSched {
  1019  		if !lv.hasStackMap(v) {
  1020  			b.Values = append(b.Values, v)
  1021  			continue
  1022  		}
  1023  		clobber(lv, b, lv.livevars[idx])
  1024  		b.Values = append(b.Values, v)
  1025  		idx++
  1026  	}
  1027  }
  1028  
  1029  // clobber generates code to clobber pointer slots in all dead variables
  1030  // (those not marked in live). Clobbering instructions are added to the end
  1031  // of b.Values.
  1032  func clobber(lv *Liveness, b *ssa.Block, live bitvec.BitVec) {
  1033  	for i, n := range lv.vars {
  1034  		if !live.Get(int32(i)) && !n.Addrtaken() && !n.OpenDeferSlot() && !n.IsOutputParamHeapAddr() {
  1035  			// Don't clobber stack objects (address-taken). They are
  1036  			// tracked dynamically.
  1037  			// Also don't clobber slots that are live for defers (see
  1038  			// the code setting livedefer in epilogue).
  1039  			if lv.noClobberArgs && n.Class == ir.PPARAM {
  1040  				continue
  1041  			}
  1042  			clobberVar(b, n)
  1043  		}
  1044  	}
  1045  }
  1046  
  1047  // clobberVar generates code to trash the pointers in v.
  1048  // Clobbering instructions are added to the end of b.Values.
  1049  func clobberVar(b *ssa.Block, v *ir.Name) {
  1050  	clobberWalk(b, v, 0, v.Type())
  1051  }
  1052  
  1053  // b = block to which we append instructions
  1054  // v = variable
  1055  // offset = offset of (sub-portion of) variable to clobber (in bytes)
  1056  // t = type of sub-portion of v.
  1057  func clobberWalk(b *ssa.Block, v *ir.Name, offset int64, t *types.Type) {
  1058  	if !t.HasPointers() {
  1059  		return
  1060  	}
  1061  	switch t.Kind() {
  1062  	case types.TPTR,
  1063  		types.TUNSAFEPTR,
  1064  		types.TFUNC,
  1065  		types.TCHAN,
  1066  		types.TMAP:
  1067  		clobberPtr(b, v, offset)
  1068  
  1069  	case types.TSTRING:
  1070  		// struct { byte *str; int len; }
  1071  		clobberPtr(b, v, offset)
  1072  
  1073  	case types.TINTER:
  1074  		// struct { Itab *tab; void *data; }
  1075  		// or, when isnilinter(t)==true:
  1076  		// struct { Type *type; void *data; }
  1077  		clobberPtr(b, v, offset)
  1078  		clobberPtr(b, v, offset+int64(types.PtrSize))
  1079  
  1080  	case types.TSLICE:
  1081  		// struct { byte *array; int len; int cap; }
  1082  		clobberPtr(b, v, offset)
  1083  
  1084  	case types.TARRAY:
  1085  		for i := int64(0); i < t.NumElem(); i++ {
  1086  			clobberWalk(b, v, offset+i*t.Elem().Size(), t.Elem())
  1087  		}
  1088  
  1089  	case types.TSTRUCT:
  1090  		for _, t1 := range t.Fields() {
  1091  			clobberWalk(b, v, offset+t1.Offset, t1.Type)
  1092  		}
  1093  
  1094  	default:
  1095  		base.Fatalf("clobberWalk: unexpected type, %v", t)
  1096  	}
  1097  }
  1098  
  1099  // clobberPtr generates a clobber of the pointer at offset offset in v.
  1100  // The clobber instruction is added at the end of b.
  1101  func clobberPtr(b *ssa.Block, v *ir.Name, offset int64) {
  1102  	b.NewValue0IA(src.NoXPos, ssa.OpClobber, types.TypeVoid, offset, v)
  1103  }
  1104  
  1105  func (lv *Liveness) showlive(v *ssa.Value, live bitvec.BitVec) {
  1106  	if base.Flag.Live == 0 || ir.FuncName(lv.fn) == "init" || strings.HasPrefix(ir.FuncName(lv.fn), ".") {
  1107  		return
  1108  	}
  1109  	if lv.fn.Wrapper() || lv.fn.Dupok() {
  1110  		// Skip reporting liveness information for compiler-generated wrappers.
  1111  		return
  1112  	}
  1113  	if !(v == nil || v.Op.IsCall()) {
  1114  		// Historically we only printed this information at
  1115  		// calls. Keep doing so.
  1116  		return
  1117  	}
  1118  	if live.IsEmpty() {
  1119  		return
  1120  	}
  1121  
  1122  	pos, s := lv.format(v, live)
  1123  
  1124  	base.WarnfAt(pos, "%s", s)
  1125  }
  1126  
  1127  func (lv *Liveness) Format(v *ssa.Value) string {
  1128  	if v == nil {
  1129  		_, s := lv.format(nil, lv.stackMaps[0])
  1130  		return s
  1131  	}
  1132  	if idx := lv.livenessMap.Get(v); idx.StackMapValid() {
  1133  		_, s := lv.format(v, lv.stackMaps[idx])
  1134  		return s
  1135  	}
  1136  	return ""
  1137  }
  1138  
  1139  func (lv *Liveness) format(v *ssa.Value, live bitvec.BitVec) (src.XPos, string) {
  1140  	pos := lv.fn.Nname.Pos()
  1141  	if v != nil {
  1142  		pos = v.Pos
  1143  	}
  1144  
  1145  	s := "live at "
  1146  	if v == nil {
  1147  		s += fmt.Sprintf("entry to %s:", ir.FuncName(lv.fn))
  1148  	} else if sym, ok := v.Aux.(*ssa.AuxCall); ok && sym.Fn != nil {
  1149  		fn := sym.Fn.Name
  1150  		if pos := strings.Index(fn, "."); pos >= 0 {
  1151  			fn = fn[pos+1:]
  1152  		}
  1153  		s += fmt.Sprintf("call to %s:", fn)
  1154  	} else {
  1155  		s += "indirect call:"
  1156  	}
  1157  
  1158  	// Sort variable names for display. Variables aren't in any particular order, and
  1159  	// the order can change by architecture, particularly with differences in regabi.
  1160  	var names []string
  1161  	for j, n := range lv.vars {
  1162  		if live.Get(int32(j)) {
  1163  			names = append(names, n.Sym().Name)
  1164  		}
  1165  	}
  1166  	sort.Strings(names)
  1167  	for _, v := range names {
  1168  		s += " " + v
  1169  	}
  1170  	return pos, s
  1171  }
  1172  
  1173  func (lv *Liveness) printbvec(printed bool, name string, live bitvec.BitVec) bool {
  1174  	if live.IsEmpty() {
  1175  		return printed
  1176  	}
  1177  
  1178  	if !printed {
  1179  		fmt.Printf("\t")
  1180  	} else {
  1181  		fmt.Printf(" ")
  1182  	}
  1183  	fmt.Printf("%s=", name)
  1184  
  1185  	comma := ""
  1186  	for i, n := range lv.vars {
  1187  		if !live.Get(int32(i)) {
  1188  			continue
  1189  		}
  1190  		fmt.Printf("%s%s", comma, n.Sym().Name)
  1191  		comma = ","
  1192  	}
  1193  	return true
  1194  }
  1195  
  1196  // printeffect is like printbvec, but for valueEffects.
  1197  func (lv *Liveness) printeffect(printed bool, name string, pos int32, x bool) bool {
  1198  	if !x {
  1199  		return printed
  1200  	}
  1201  	if !printed {
  1202  		fmt.Printf("\t")
  1203  	} else {
  1204  		fmt.Printf(" ")
  1205  	}
  1206  	fmt.Printf("%s=", name)
  1207  	if x {
  1208  		fmt.Printf("%s", lv.vars[pos].Sym().Name)
  1209  	}
  1210  
  1211  	return true
  1212  }
  1213  
  1214  // Prints the computed liveness information and inputs, for debugging.
  1215  // This format synthesizes the information used during the multiple passes
  1216  // into a single presentation.
  1217  func (lv *Liveness) printDebug() {
  1218  	fmt.Printf("liveness: %s\n", ir.FuncName(lv.fn))
  1219  
  1220  	for i, b := range lv.f.Blocks {
  1221  		if i > 0 {
  1222  			fmt.Printf("\n")
  1223  		}
  1224  
  1225  		// bb#0 pred=1,2 succ=3,4
  1226  		fmt.Printf("bb#%d pred=", b.ID)
  1227  		for j, pred := range b.Preds {
  1228  			if j > 0 {
  1229  				fmt.Printf(",")
  1230  			}
  1231  			fmt.Printf("%d", pred.Block().ID)
  1232  		}
  1233  		fmt.Printf(" succ=")
  1234  		for j, succ := range b.Succs {
  1235  			if j > 0 {
  1236  				fmt.Printf(",")
  1237  			}
  1238  			fmt.Printf("%d", succ.Block().ID)
  1239  		}
  1240  		fmt.Printf("\n")
  1241  
  1242  		be := lv.blockEffects(b)
  1243  
  1244  		// initial settings
  1245  		printed := false
  1246  		printed = lv.printbvec(printed, "uevar", be.uevar)
  1247  		printed = lv.printbvec(printed, "livein", be.livein)
  1248  		if printed {
  1249  			fmt.Printf("\n")
  1250  		}
  1251  
  1252  		// program listing, with individual effects listed
  1253  
  1254  		if b == lv.f.Entry {
  1255  			live := lv.stackMaps[0]
  1256  			fmt.Printf("(%s) function entry\n", base.FmtPos(lv.fn.Nname.Pos()))
  1257  			fmt.Printf("\tlive=")
  1258  			printed = false
  1259  			for j, n := range lv.vars {
  1260  				if !live.Get(int32(j)) {
  1261  					continue
  1262  				}
  1263  				if printed {
  1264  					fmt.Printf(",")
  1265  				}
  1266  				fmt.Printf("%v", n)
  1267  				printed = true
  1268  			}
  1269  			fmt.Printf("\n")
  1270  		}
  1271  
  1272  		for _, v := range b.Values {
  1273  			fmt.Printf("(%s) %v\n", base.FmtPos(v.Pos), v.LongString())
  1274  
  1275  			pcdata := lv.livenessMap.Get(v)
  1276  
  1277  			pos, effect := lv.valueEffects(v)
  1278  			printed = false
  1279  			printed = lv.printeffect(printed, "uevar", pos, effect&uevar != 0)
  1280  			printed = lv.printeffect(printed, "varkill", pos, effect&varkill != 0)
  1281  			if printed {
  1282  				fmt.Printf("\n")
  1283  			}
  1284  
  1285  			if pcdata.StackMapValid() {
  1286  				fmt.Printf("\tlive=")
  1287  				printed = false
  1288  				if pcdata.StackMapValid() {
  1289  					live := lv.stackMaps[pcdata]
  1290  					for j, n := range lv.vars {
  1291  						if !live.Get(int32(j)) {
  1292  							continue
  1293  						}
  1294  						if printed {
  1295  							fmt.Printf(",")
  1296  						}
  1297  						fmt.Printf("%v", n)
  1298  						printed = true
  1299  					}
  1300  				}
  1301  				fmt.Printf("\n")
  1302  			}
  1303  
  1304  			if lv.livenessMap.GetUnsafe(v) {
  1305  				fmt.Printf("\tunsafe-point\n")
  1306  			}
  1307  		}
  1308  		if lv.livenessMap.GetUnsafeBlock(b) {
  1309  			fmt.Printf("\tunsafe-block\n")
  1310  		}
  1311  
  1312  		// bb bitsets
  1313  		fmt.Printf("end\n")
  1314  		printed = false
  1315  		printed = lv.printbvec(printed, "varkill", be.varkill)
  1316  		printed = lv.printbvec(printed, "liveout", be.liveout)
  1317  		if printed {
  1318  			fmt.Printf("\n")
  1319  		}
  1320  	}
  1321  
  1322  	fmt.Printf("\n")
  1323  }
  1324  
  1325  // Dumps a slice of bitmaps to a symbol as a sequence of uint32 values. The
  1326  // first word dumped is the total number of bitmaps. The second word is the
  1327  // length of the bitmaps. All bitmaps are assumed to be of equal length. The
  1328  // remaining bytes are the raw bitmaps.
  1329  func (lv *Liveness) emit() (argsSym, liveSym *obj.LSym) {
  1330  	// Size args bitmaps to be just large enough to hold the largest pointer.
  1331  	// First, find the largest Xoffset node we care about.
  1332  	// (Nodes without pointers aren't in lv.vars; see ShouldTrack.)
  1333  	var maxArgNode *ir.Name
  1334  	for _, n := range lv.vars {
  1335  		switch n.Class {
  1336  		case ir.PPARAM, ir.PPARAMOUT:
  1337  			if !n.IsOutputParamInRegisters() {
  1338  				if maxArgNode == nil || n.FrameOffset() > maxArgNode.FrameOffset() {
  1339  					maxArgNode = n
  1340  				}
  1341  			}
  1342  		}
  1343  	}
  1344  	// Next, find the offset of the largest pointer in the largest node.
  1345  	var maxArgs int64
  1346  	if maxArgNode != nil {
  1347  		maxArgs = maxArgNode.FrameOffset() + types.PtrDataSize(maxArgNode.Type())
  1348  	}
  1349  
  1350  	// Size locals bitmaps to be stkptrsize sized.
  1351  	// We cannot shrink them to only hold the largest pointer,
  1352  	// because their size is used to calculate the beginning
  1353  	// of the local variables frame.
  1354  	// Further discussion in https://golang.org/cl/104175.
  1355  	// TODO: consider trimming leading zeros.
  1356  	// This would require shifting all bitmaps.
  1357  	maxLocals := lv.stkptrsize
  1358  
  1359  	// Temporary symbols for encoding bitmaps.
  1360  	var argsSymTmp, liveSymTmp obj.LSym
  1361  
  1362  	args := bitvec.New(int32(maxArgs / int64(types.PtrSize)))
  1363  	aoff := objw.Uint32(&argsSymTmp, 0, uint32(len(lv.stackMaps))) // number of bitmaps
  1364  	aoff = objw.Uint32(&argsSymTmp, aoff, uint32(args.N))          // number of bits in each bitmap
  1365  
  1366  	locals := bitvec.New(int32(maxLocals / int64(types.PtrSize)))
  1367  	loff := objw.Uint32(&liveSymTmp, 0, uint32(len(lv.stackMaps))) // number of bitmaps
  1368  	loff = objw.Uint32(&liveSymTmp, loff, uint32(locals.N))        // number of bits in each bitmap
  1369  
  1370  	for _, live := range lv.stackMaps {
  1371  		args.Clear()
  1372  		locals.Clear()
  1373  
  1374  		lv.pointerMap(live, lv.vars, args, locals)
  1375  
  1376  		aoff = objw.BitVec(&argsSymTmp, aoff, args)
  1377  		loff = objw.BitVec(&liveSymTmp, loff, locals)
  1378  	}
  1379  
  1380  	// These symbols will be added to Ctxt.Data by addGCLocals
  1381  	// after parallel compilation is done.
  1382  	return base.Ctxt.GCLocalsSym(argsSymTmp.P), base.Ctxt.GCLocalsSym(liveSymTmp.P)
  1383  }
  1384  
  1385  // Entry pointer for Compute analysis. Solves for the Compute of
  1386  // pointer variables in the function and emits a runtime data
  1387  // structure read by the garbage collector.
  1388  // Returns a map from GC safe points to their corresponding stack map index,
  1389  // and a map that contains all input parameters that may be partially live.
  1390  func Compute(curfn *ir.Func, f *ssa.Func, stkptrsize int64, pp *objw.Progs, retLiveness bool) (Map, map[*ir.Name]bool, *Liveness) {
  1391  	// Construct the global liveness state.
  1392  	vars, idx := getvariables(curfn)
  1393  	lv := newliveness(curfn, f, vars, idx, stkptrsize)
  1394  
  1395  	// Run the dataflow framework.
  1396  	lv.prologue()
  1397  	lv.solve()
  1398  	lv.epilogue()
  1399  	if base.Flag.Live > 0 {
  1400  		lv.showlive(nil, lv.stackMaps[0])
  1401  		for _, b := range f.Blocks {
  1402  			for _, val := range b.Values {
  1403  				if idx := lv.livenessMap.Get(val); idx.StackMapValid() {
  1404  					lv.showlive(val, lv.stackMaps[idx])
  1405  				}
  1406  			}
  1407  		}
  1408  	}
  1409  	if base.Flag.Live >= 2 {
  1410  		lv.printDebug()
  1411  	}
  1412  
  1413  	// Update the function cache.
  1414  	{
  1415  		cache := f.Cache.Liveness.(*livenessFuncCache)
  1416  		if cap(lv.be) < 2000 { // Threshold from ssa.Cache slices.
  1417  			for i := range lv.be {
  1418  				lv.be[i] = blockEffects{}
  1419  			}
  1420  			cache.be = lv.be
  1421  		}
  1422  		if len(lv.livenessMap.Vals) < 2000 {
  1423  			cache.livenessMap = lv.livenessMap
  1424  		}
  1425  	}
  1426  
  1427  	// Emit the live pointer map data structures
  1428  	ls := curfn.LSym
  1429  	fninfo := ls.Func()
  1430  	fninfo.GCArgs, fninfo.GCLocals = lv.emit()
  1431  
  1432  	p := pp.Prog(obj.AFUNCDATA)
  1433  	p.From.SetConst(rtabi.FUNCDATA_ArgsPointerMaps)
  1434  	p.To.Type = obj.TYPE_MEM
  1435  	p.To.Name = obj.NAME_EXTERN
  1436  	p.To.Sym = fninfo.GCArgs
  1437  
  1438  	p = pp.Prog(obj.AFUNCDATA)
  1439  	p.From.SetConst(rtabi.FUNCDATA_LocalsPointerMaps)
  1440  	p.To.Type = obj.TYPE_MEM
  1441  	p.To.Name = obj.NAME_EXTERN
  1442  	p.To.Sym = fninfo.GCLocals
  1443  
  1444  	if x := lv.emitStackObjects(); x != nil {
  1445  		p := pp.Prog(obj.AFUNCDATA)
  1446  		p.From.SetConst(rtabi.FUNCDATA_StackObjects)
  1447  		p.To.Type = obj.TYPE_MEM
  1448  		p.To.Name = obj.NAME_EXTERN
  1449  		p.To.Sym = x
  1450  	}
  1451  
  1452  	retLv := lv
  1453  	if !retLiveness {
  1454  		retLv = nil
  1455  	}
  1456  
  1457  	return lv.livenessMap, lv.partLiveArgs, retLv
  1458  }
  1459  
  1460  func (lv *Liveness) emitStackObjects() *obj.LSym {
  1461  	var vars []*ir.Name
  1462  	for _, n := range lv.fn.Dcl {
  1463  		if shouldTrack(n) && n.Addrtaken() && n.Esc() != ir.EscHeap {
  1464  			vars = append(vars, n)
  1465  		}
  1466  	}
  1467  	if len(vars) == 0 {
  1468  		return nil
  1469  	}
  1470  
  1471  	// Sort variables from lowest to highest address.
  1472  	slices.SortFunc(vars, func(a, b *ir.Name) int { return cmp.Compare(a.FrameOffset(), b.FrameOffset()) })
  1473  
  1474  	// Populate the stack object data.
  1475  	// Format must match runtime/stack.go:stackObjectRecord.
  1476  	x := base.Ctxt.Lookup(lv.fn.LSym.Name + ".stkobj")
  1477  	x.Set(obj.AttrContentAddressable, true)
  1478  	lv.fn.LSym.Func().StackObjects = x
  1479  	off := 0
  1480  	off = objw.Uintptr(x, off, uint64(len(vars)))
  1481  	for _, v := range vars {
  1482  		// Note: arguments and return values have non-negative Xoffset,
  1483  		// in which case the offset is relative to argp.
  1484  		// Locals have a negative Xoffset, in which case the offset is relative to varp.
  1485  		// We already limit the frame size, so the offset and the object size
  1486  		// should not be too big.
  1487  		frameOffset := v.FrameOffset()
  1488  		if frameOffset != int64(int32(frameOffset)) {
  1489  			base.Fatalf("frame offset too big: %v %d", v, frameOffset)
  1490  		}
  1491  		off = objw.Uint32(x, off, uint32(frameOffset))
  1492  
  1493  		t := v.Type()
  1494  		sz := t.Size()
  1495  		if sz != int64(int32(sz)) {
  1496  			base.Fatalf("stack object too big: %v of type %v, size %d", v, t, sz)
  1497  		}
  1498  		lsym, ptrBytes := reflectdata.GCSym(t)
  1499  		off = objw.Uint32(x, off, uint32(sz))
  1500  		off = objw.Uint32(x, off, uint32(ptrBytes))
  1501  		off = objw.SymPtrOff(x, off, lsym)
  1502  	}
  1503  
  1504  	if base.Flag.Live != 0 {
  1505  		for _, v := range vars {
  1506  			base.WarnfAt(v.Pos(), "stack object %v %v", v, v.Type())
  1507  		}
  1508  	}
  1509  
  1510  	return x
  1511  }
  1512  
  1513  // isfat reports whether a variable of type t needs multiple assignments to initialize.
  1514  // For example:
  1515  //
  1516  //	type T struct { x, y int }
  1517  //	x := T{x: 0, y: 1}
  1518  //
  1519  // Then we need:
  1520  //
  1521  //	var t T
  1522  //	t.x = 0
  1523  //	t.y = 1
  1524  //
  1525  // to fully initialize t.
  1526  func isfat(t *types.Type) bool {
  1527  	if t != nil {
  1528  		switch t.Kind() {
  1529  		case types.TSLICE, types.TSTRING,
  1530  			types.TINTER: // maybe remove later
  1531  			return true
  1532  		case types.TARRAY:
  1533  			// Array of 1 element, check if element is fat
  1534  			if t.NumElem() == 1 {
  1535  				return isfat(t.Elem())
  1536  			}
  1537  			return true
  1538  		case types.TSTRUCT:
  1539  			// Struct with 1 field, check if field is fat
  1540  			if t.NumFields() == 1 {
  1541  				return isfat(t.Field(0).Type)
  1542  			}
  1543  			return true
  1544  		}
  1545  	}
  1546  
  1547  	return false
  1548  }
  1549  
  1550  // WriteFuncMap writes the pointer bitmaps for bodyless function fn's
  1551  // inputs and outputs as the value of symbol <fn>.args_stackmap.
  1552  // If fn has outputs, two bitmaps are written, otherwise just one.
  1553  func WriteFuncMap(fn *ir.Func, abiInfo *abi.ABIParamResultInfo) {
  1554  	if ir.FuncName(fn) == "_" {
  1555  		return
  1556  	}
  1557  	nptr := int(abiInfo.ArgWidth() / int64(types.PtrSize))
  1558  	bv := bitvec.New(int32(nptr))
  1559  
  1560  	for _, p := range abiInfo.InParams() {
  1561  		typebits.SetNoCheck(p.Type, p.FrameOffset(abiInfo), bv)
  1562  	}
  1563  
  1564  	nbitmap := 1
  1565  	if fn.Type().NumResults() > 0 {
  1566  		nbitmap = 2
  1567  	}
  1568  	lsym := base.Ctxt.Lookup(fn.LSym.Name + ".args_stackmap")
  1569  	lsym.Set(obj.AttrLinkname, true) // allow args_stackmap referenced from assembly
  1570  	off := objw.Uint32(lsym, 0, uint32(nbitmap))
  1571  	off = objw.Uint32(lsym, off, uint32(bv.N))
  1572  	off = objw.BitVec(lsym, off, bv)
  1573  
  1574  	if fn.Type().NumResults() > 0 {
  1575  		for _, p := range abiInfo.OutParams() {
  1576  			if len(p.Registers) == 0 {
  1577  				typebits.SetNoCheck(p.Type, p.FrameOffset(abiInfo), bv)
  1578  			}
  1579  		}
  1580  		off = objw.BitVec(lsym, off, bv)
  1581  	}
  1582  
  1583  	objw.Global(lsym, int32(off), obj.RODATA|obj.LOCAL)
  1584  }
  1585  

View as plain text