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

     1	// Copyright 2011 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package gc
     6	
     7	import (
     8		"cmd/compile/internal/types"
     9		"fmt"
    10		"strconv"
    11		"strings"
    12	)
    13	
    14	// Escape analysis.
    15	
    16	// An escape analysis pass for a set of functions. The
    17	// analysis assumes that closures and the functions in which
    18	// they appear are analyzed together, so that the aliasing
    19	// between their variables can be modeled more precisely.
    20	//
    21	// First escfunc, esc and escassign recurse over the ast of
    22	// each function to dig out flow(dst,src) edges between any
    23	// pointer-containing  nodes and store those edges in
    24	// e.nodeEscState(dst).Flowsrc. For values assigned to a
    25	// variable in an outer scope or used as a return value,
    26	// they store a flow(theSink, src) edge to a fake node 'the
    27	// Sink'.  For variables referenced in closures, an edge
    28	// flow(closure, &var) is recorded and the flow of a closure
    29	// itself to an outer scope is tracked the same way as other
    30	// variables.
    31	//
    32	// Then escflood walks the graph in destination-to-source
    33	// order, starting at theSink, propagating a computed
    34	// "escape level", and tags as escaping values it can
    35	// reach that are either & (address-taken) nodes or new(T),
    36	// and tags pointer-typed or pointer-containing function
    37	// parameters it can reach as leaking.
    38	//
    39	// If a value's address is taken but the address does not escape,
    40	// then the value can stay on the stack. If the value new(T) does
    41	// not escape, then new(T) can be rewritten into a stack allocation.
    42	// The same is true of slice literals.
    43	
    44	// If newescape is true, then escape.go drives escape analysis instead
    45	// of esc.go.
    46	var newescape bool
    47	
    48	func escapes(all []*Node) {
    49		visitBottomUp(all, escapeImpl())
    50	}
    51	
    52	func escapeImpl() func([]*Node, bool) {
    53		if newescape {
    54			return escapeFuncs
    55		}
    56		return escAnalyze
    57	}
    58	
    59	const (
    60		EscFuncUnknown = 0 + iota
    61		EscFuncPlanned
    62		EscFuncStarted
    63		EscFuncTagged
    64	)
    65	
    66	// A Level encodes the reference state and context applied to
    67	// (stack, heap) allocated memory.
    68	//
    69	// value is the overall sum of *(1) and &(-1) operations encountered
    70	// along a path from a destination (sink, return value) to a source
    71	// (allocation, parameter).
    72	//
    73	// suffixValue is the maximum-copy-started-suffix-level on
    74	// a flow path from a sink/destination.  That is, a value
    75	// with suffixValue N is guaranteed to be dereferenced at least
    76	// N deep (chained applications of DOTPTR or IND or INDEX)
    77	// before the result is assigned to a sink.
    78	//
    79	// For example, suppose x is a pointer to T, declared type T struct { left, right *T }
    80	//   sink = x.left.left --> level(x)=2, x is reached via two dereferences (DOTPTR) and does not escape to sink.
    81	//   sink = &T{right:x} --> level(x)=-1, x is accessible from sink via one "address of"
    82	//   sink = &T{right:&T{right:x}} --> level(x)=-2, x is accessible from sink via two "address of"
    83	//
    84	// However, in the next example x's level value and suffixValue differ:
    85	//   sink = &T{right:&T{right:x.left}} --> level(x).value=-1, level(x).suffixValue=1
    86	// The positive suffixValue indicates that x is NOT accessible
    87	// from sink. Without a separate suffixValue to capture this, x would
    88	// appear to escape because its "value" would be -1.  (The copy
    89	// operations are sometimes implicit in the source code; in this case,
    90	// the value of x.left was copied into a field of an newly allocated T).
    91	//
    92	// Each node's level (value and suffixValue) is the maximum for
    93	// all flow paths from (any) sink to that node.
    94	
    95	// There's one of these for each Node, and the integer values
    96	// rarely exceed even what can be stored in 4 bits, never mind 8.
    97	type Level struct {
    98		value, suffixValue int8
    99	}
   100	
   101	// There are loops in the escape graph,
   102	// causing arbitrary recursion into deeper and deeper
   103	// levels. Cut this off safely by making minLevel sticky:
   104	// once you get that deep, you cannot go down any further
   105	// but you also cannot go up any further. This is a
   106	// conservative fix. Making minLevel smaller (more negative)
   107	// would handle more complex chains of indirections followed
   108	// by address-of operations, at the cost of repeating the
   109	// traversal once for each additional allowed level when a
   110	// loop is encountered. Using -2 suffices to pass all the
   111	// tests we have written so far, which we assume matches the
   112	// level of complexity we want the escape analysis code to
   113	// handle.
   114	const MinLevel = -2
   115	
   116	func (l Level) int() int {
   117		return int(l.value)
   118	}
   119	
   120	func levelFrom(i int) Level {
   121		if i <= MinLevel {
   122			return Level{value: MinLevel}
   123		}
   124		return Level{value: int8(i)}
   125	}
   126	
   127	func satInc8(x int8) int8 {
   128		if x == 127 {
   129			return 127
   130		}
   131		return x + 1
   132	}
   133	
   134	func min8(a, b int8) int8 {
   135		if a < b {
   136			return a
   137		}
   138		return b
   139	}
   140	
   141	func max8(a, b int8) int8 {
   142		if a > b {
   143			return a
   144		}
   145		return b
   146	}
   147	
   148	// inc returns the level l + 1, representing the effect of an indirect (*) operation.
   149	func (l Level) inc() Level {
   150		if l.value <= MinLevel {
   151			return Level{value: MinLevel}
   152		}
   153		return Level{value: satInc8(l.value), suffixValue: satInc8(l.suffixValue)}
   154	}
   155	
   156	// dec returns the level l - 1, representing the effect of an address-of (&) operation.
   157	func (l Level) dec() Level {
   158		if l.value <= MinLevel {
   159			return Level{value: MinLevel}
   160		}
   161		return Level{value: l.value - 1, suffixValue: l.suffixValue - 1}
   162	}
   163	
   164	// copy returns the level for a copy of a value with level l.
   165	// The resulting suffixValue is at least zero, or larger if it was already larger.
   166	func (l Level) copy() Level {
   167		return Level{value: l.value, suffixValue: max8(l.suffixValue, 0)}
   168	}
   169	
   170	func (l1 Level) min(l2 Level) Level {
   171		return Level{
   172			value:       min8(l1.value, l2.value),
   173			suffixValue: min8(l1.suffixValue, l2.suffixValue)}
   174	}
   175	
   176	// guaranteedDereference returns the number of dereferences
   177	// applied to a pointer before addresses are taken/generated.
   178	// This is the maximum level computed from path suffixes starting
   179	// with copies where paths flow from destination to source.
   180	func (l Level) guaranteedDereference() int {
   181		return int(l.suffixValue)
   182	}
   183	
   184	// An EscStep documents one step in the path from memory
   185	// that is heap allocated to the (alleged) reason for the
   186	// heap allocation.
   187	type EscStep struct {
   188		src, dst *Node    // the endpoints of this edge in the escape-to-heap chain.
   189		where    *Node    // sometimes the endpoints don't match source locations; set 'where' to make that right
   190		parent   *EscStep // used in flood to record path
   191		why      string   // explanation for this step in the escape-to-heap chain
   192		busy     bool     // used in prevent to snip cycles.
   193	}
   194	
   195	type NodeEscState struct {
   196		Curfn             *Node
   197		Flowsrc           []EscStep // flow(this, src)
   198		Retval            Nodes     // on OCALLxxx, list of dummy return values
   199		Loopdepth         int32     // -1: global, 0: return variables, 1:function top level, increased inside function for every loop or label to mark scopes
   200		Level             Level
   201		Walkgen           uint32
   202		Maxextraloopdepth int32
   203	}
   204	
   205	func (e *EscState) nodeEscState(n *Node) *NodeEscState {
   206		if nE, ok := n.Opt().(*NodeEscState); ok {
   207			return nE
   208		}
   209		if n.Opt() != nil {
   210			Fatalf("nodeEscState: opt in use (%T)", n.Opt())
   211		}
   212		nE := &NodeEscState{
   213			Curfn: Curfn,
   214		}
   215		n.SetOpt(nE)
   216		e.opts = append(e.opts, n)
   217		return nE
   218	}
   219	
   220	func (e *EscState) track(n *Node) {
   221		if Curfn == nil {
   222			Fatalf("EscState.track: Curfn nil")
   223		}
   224		n.Esc = EscNone // until proven otherwise
   225		nE := e.nodeEscState(n)
   226		nE.Loopdepth = e.loopdepth
   227		e.noesc = append(e.noesc, n)
   228	}
   229	
   230	// Escape constants are numbered in order of increasing "escapiness"
   231	// to help make inferences be monotonic. With the exception of
   232	// EscNever which is sticky, eX < eY means that eY is more exposed
   233	// than eX, and hence replaces it in a conservative analysis.
   234	const (
   235		EscUnknown        = iota
   236		EscNone           // Does not escape to heap, result, or parameters.
   237		EscReturn         // Is returned or reachable from returned.
   238		EscHeap           // Reachable from the heap
   239		EscNever          // By construction will not escape.
   240		EscBits           = 3
   241		EscMask           = (1 << EscBits) - 1
   242		EscContentEscapes = 1 << EscBits // value obtained by indirect of parameter escapes to heap
   243		EscReturnBits     = EscBits + 1
   244		// Node.esc encoding = | escapeReturnEncoding:(width-4) | contentEscapes:1 | escEnum:3
   245	)
   246	
   247	// escMax returns the maximum of an existing escape value
   248	// (and its additional parameter flow flags) and a new escape type.
   249	func escMax(e, etype uint16) uint16 {
   250		if e&EscMask >= EscHeap {
   251			// normalize
   252			if e&^EscMask != 0 {
   253				Fatalf("Escape information had unexpected return encoding bits (w/ EscHeap, EscNever), e&EscMask=%v", e&EscMask)
   254			}
   255		}
   256		if e&EscMask > etype {
   257			return e
   258		}
   259		if etype == EscNone || etype == EscReturn {
   260			return (e &^ EscMask) | etype
   261		}
   262		return etype
   263	}
   264	
   265	// For each input parameter to a function, the escapeReturnEncoding describes
   266	// how the parameter may leak to the function's outputs. This is currently the
   267	// "level" of the leak where level is 0 or larger (negative level means stored into
   268	// something whose address is returned -- but that implies stored into the heap,
   269	// hence EscHeap, which means that the details are not currently relevant. )
   270	const (
   271		bitsPerOutputInTag = 3                                 // For each output, the number of bits for a tag
   272		bitsMaskForTag     = uint16(1<<bitsPerOutputInTag) - 1 // The bit mask to extract a single tag.
   273		maxEncodedLevel    = int(bitsMaskForTag - 1)           // The largest level that can be stored in a tag.
   274	)
   275	
   276	type EscState struct {
   277		// Fake node that all
   278		//   - return values and output variables
   279		//   - parameters on imported functions not marked 'safe'
   280		//   - assignments to global variables
   281		// flow to.
   282		theSink Node
   283	
   284		dsts      []*Node // all dst nodes
   285		loopdepth int32   // for detecting nested loop scopes
   286		pdepth    int     // for debug printing in recursions.
   287		dstcount  int     // diagnostic
   288		edgecount int     // diagnostic
   289		noesc     []*Node // list of possible non-escaping nodes, for printing
   290		recursive bool    // recursive function or group of mutually recursive functions.
   291		opts      []*Node // nodes with .Opt initialized
   292		walkgen   uint32
   293	}
   294	
   295	func newEscState(recursive bool) *EscState {
   296		e := new(EscState)
   297		e.theSink.Op = ONAME
   298		e.theSink.Orig = &e.theSink
   299		e.theSink.SetClass(PEXTERN)
   300		e.theSink.Sym = lookup(".sink")
   301		e.nodeEscState(&e.theSink).Loopdepth = -1
   302		e.recursive = recursive
   303		return e
   304	}
   305	
   306	func (e *EscState) stepWalk(dst, src *Node, why string, parent *EscStep) *EscStep {
   307		// TODO: keep a cache of these, mark entry/exit in escwalk to avoid allocation
   308		// Or perhaps never mind, since it is disabled unless printing is on.
   309		// We may want to revisit this, since the EscStep nodes would make
   310		// an excellent replacement for the poorly-separated graph-build/graph-flood
   311		// stages.
   312		if Debug['m'] == 0 {
   313			return nil
   314		}
   315		return &EscStep{src: src, dst: dst, why: why, parent: parent}
   316	}
   317	
   318	func (e *EscState) stepAssign(step *EscStep, dst, src *Node, why string) *EscStep {
   319		if Debug['m'] == 0 {
   320			return nil
   321		}
   322		if step != nil { // Caller may have known better.
   323			if step.why == "" {
   324				step.why = why
   325			}
   326			if step.dst == nil {
   327				step.dst = dst
   328			}
   329			if step.src == nil {
   330				step.src = src
   331			}
   332			return step
   333		}
   334		return &EscStep{src: src, dst: dst, why: why}
   335	}
   336	
   337	func (e *EscState) stepAssignWhere(dst, src *Node, why string, where *Node) *EscStep {
   338		if Debug['m'] == 0 {
   339			return nil
   340		}
   341		return &EscStep{src: src, dst: dst, why: why, where: where}
   342	}
   343	
   344	// funcSym returns fn.Func.Nname.Sym if no nils are encountered along the way.
   345	func funcSym(fn *Node) *types.Sym {
   346		if fn == nil || fn.Func.Nname == nil {
   347			return nil
   348		}
   349		return fn.Func.Nname.Sym
   350	}
   351	
   352	// curfnSym returns n.Curfn.Nname.Sym if no nils are encountered along the way.
   353	func (e *EscState) curfnSym(n *Node) *types.Sym {
   354		nE := e.nodeEscState(n)
   355		return funcSym(nE.Curfn)
   356	}
   357	
   358	func escAnalyze(all []*Node, recursive bool) {
   359		e := newEscState(recursive)
   360	
   361		for _, n := range all {
   362			if n.Op == ODCLFUNC {
   363				n.Esc = EscFuncPlanned
   364				if Debug['m'] > 3 {
   365					Dump("escAnalyze", n)
   366				}
   367	
   368			}
   369		}
   370	
   371		// flow-analyze functions
   372		for _, n := range all {
   373			if n.Op == ODCLFUNC {
   374				e.escfunc(n)
   375			}
   376		}
   377	
   378		// visit the upstream of each dst, mark address nodes with
   379		// addrescapes, mark parameters unsafe
   380		escapes := make([]uint16, len(e.dsts))
   381		for i, n := range e.dsts {
   382			escapes[i] = n.Esc
   383		}
   384		for _, n := range e.dsts {
   385			e.escflood(n)
   386		}
   387		for {
   388			done := true
   389			for i, n := range e.dsts {
   390				if n.Esc != escapes[i] {
   391					done = false
   392					if Debug['m'] > 2 {
   393						Warnl(n.Pos, "Reflooding %v %S", e.curfnSym(n), n)
   394					}
   395					escapes[i] = n.Esc
   396					e.escflood(n)
   397				}
   398			}
   399			if done {
   400				break
   401			}
   402		}
   403	
   404		// for all top level functions, tag the typenodes corresponding to the param nodes
   405		for _, n := range all {
   406			if n.Op == ODCLFUNC {
   407				esctag(n)
   408			}
   409		}
   410	
   411		if Debug['m'] != 0 {
   412			for _, n := range e.noesc {
   413				if n.Esc == EscNone && n.Op != OADDR {
   414					Warnl(n.Pos, "%v %S does not escape", e.curfnSym(n), n)
   415				}
   416			}
   417		}
   418	
   419		for _, x := range e.opts {
   420			x.SetOpt(nil)
   421		}
   422	}
   423	
   424	func (e *EscState) escfunc(fn *Node) {
   425		if fn.Esc != EscFuncPlanned {
   426			Fatalf("repeat escfunc %v", fn.Func.Nname)
   427		}
   428		fn.Esc = EscFuncStarted
   429	
   430		saveld := e.loopdepth
   431		e.loopdepth = 1
   432		savefn := Curfn
   433		Curfn = fn
   434	
   435		for _, ln := range Curfn.Func.Dcl {
   436			if ln.Op != ONAME {
   437				continue
   438			}
   439			lnE := e.nodeEscState(ln)
   440			switch ln.Class() {
   441			// out params are in a loopdepth between the sink and all local variables
   442			case PPARAMOUT:
   443				lnE.Loopdepth = 0
   444	
   445			case PPARAM:
   446				lnE.Loopdepth = 1
   447				if ln.Type != nil && !types.Haspointers(ln.Type) {
   448					break
   449				}
   450				if Curfn.Nbody.Len() == 0 && !Curfn.Noescape() {
   451					ln.Esc = EscHeap
   452				} else {
   453					ln.Esc = EscNone // prime for escflood later
   454				}
   455				e.noesc = append(e.noesc, ln)
   456			}
   457		}
   458	
   459		// in a mutually recursive group we lose track of the return values
   460		if e.recursive {
   461			for _, ln := range Curfn.Func.Dcl {
   462				if ln.Op == ONAME && ln.Class() == PPARAMOUT {
   463					e.escflows(&e.theSink, ln, e.stepAssign(nil, ln, ln, "returned from recursive function"))
   464				}
   465			}
   466		}
   467	
   468		e.escloopdepthlist(Curfn.Nbody)
   469		e.esclist(Curfn.Nbody, Curfn)
   470		Curfn = savefn
   471		e.loopdepth = saveld
   472	}
   473	
   474	// Mark labels that have no backjumps to them as not increasing e.loopdepth.
   475	// Walk hasn't generated (goto|label).Left.Sym.Label yet, so we'll cheat
   476	// and set it to one of the following two. Then in esc we'll clear it again.
   477	var (
   478		looping    Node
   479		nonlooping Node
   480	)
   481	
   482	func (e *EscState) escloopdepthlist(l Nodes) {
   483		for _, n := range l.Slice() {
   484			e.escloopdepth(n)
   485		}
   486	}
   487	
   488	func (e *EscState) escloopdepth(n *Node) {
   489		if n == nil {
   490			return
   491		}
   492	
   493		e.escloopdepthlist(n.Ninit)
   494	
   495		switch n.Op {
   496		case OLABEL:
   497			if n.Sym == nil {
   498				Fatalf("esc:label without label: %+v", n)
   499			}
   500	
   501			// Walk will complain about this label being already defined, but that's not until
   502			// after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc
   503			n.Sym.Label = asTypesNode(&nonlooping)
   504	
   505		case OGOTO:
   506			if n.Sym == nil {
   507				Fatalf("esc:goto without label: %+v", n)
   508			}
   509	
   510			// If we come past one that's uninitialized, this must be a (harmless) forward jump
   511			// but if it's set to nonlooping the label must have preceded this goto.
   512			if asNode(n.Sym.Label) == &nonlooping {
   513				n.Sym.Label = asTypesNode(&looping)
   514			}
   515		}
   516	
   517		e.escloopdepth(n.Left)
   518		e.escloopdepth(n.Right)
   519		e.escloopdepthlist(n.List)
   520		e.escloopdepthlist(n.Nbody)
   521		e.escloopdepthlist(n.Rlist)
   522	}
   523	
   524	func (e *EscState) esclist(l Nodes, parent *Node) {
   525		for _, n := range l.Slice() {
   526			e.esc(n, parent)
   527		}
   528	}
   529	
   530	func isSliceSelfAssign(dst, src *Node) bool {
   531		// Detect the following special case.
   532		//
   533		//	func (b *Buffer) Foo() {
   534		//		n, m := ...
   535		//		b.buf = b.buf[n:m]
   536		//	}
   537		//
   538		// This assignment is a no-op for escape analysis,
   539		// it does not store any new pointers into b that were not already there.
   540		// However, without this special case b will escape, because we assign to OIND/ODOTPTR.
   541		// Here we assume that the statement will not contain calls,
   542		// that is, that order will move any calls to init.
   543		// Otherwise base ONAME value could change between the moments
   544		// when we evaluate it for dst and for src.
   545	
   546		// dst is ONAME dereference.
   547		if dst.Op != ODEREF && dst.Op != ODOTPTR || dst.Left.Op != ONAME {
   548			return false
   549		}
   550		// src is a slice operation.
   551		switch src.Op {
   552		case OSLICE, OSLICE3, OSLICESTR:
   553			// OK.
   554		case OSLICEARR, OSLICE3ARR:
   555			// Since arrays are embedded into containing object,
   556			// slice of non-pointer array will introduce a new pointer into b that was not already there
   557			// (pointer to b itself). After such assignment, if b contents escape,
   558			// b escapes as well. If we ignore such OSLICEARR, we will conclude
   559			// that b does not escape when b contents do.
   560			//
   561			// Pointer to an array is OK since it's not stored inside b directly.
   562			// For slicing an array (not pointer to array), there is an implicit OADDR.
   563			// We check that to determine non-pointer array slicing.
   564			if src.Left.Op == OADDR {
   565				return false
   566			}
   567		default:
   568			return false
   569		}
   570		// slice is applied to ONAME dereference.
   571		if src.Left.Op != ODEREF && src.Left.Op != ODOTPTR || src.Left.Left.Op != ONAME {
   572			return false
   573		}
   574		// dst and src reference the same base ONAME.
   575		return dst.Left == src.Left.Left
   576	}
   577	
   578	// isSelfAssign reports whether assignment from src to dst can
   579	// be ignored by the escape analysis as it's effectively a self-assignment.
   580	func isSelfAssign(dst, src *Node) bool {
   581		if isSliceSelfAssign(dst, src) {
   582			return true
   583		}
   584	
   585		// Detect trivial assignments that assign back to the same object.
   586		//
   587		// It covers these cases:
   588		//	val.x = val.y
   589		//	val.x[i] = val.y[j]
   590		//	val.x1.x2 = val.x1.y2
   591		//	... etc
   592		//
   593		// These assignments do not change assigned object lifetime.
   594	
   595		if dst == nil || src == nil || dst.Op != src.Op {
   596			return false
   597		}
   598	
   599		switch dst.Op {
   600		case ODOT, ODOTPTR:
   601			// Safe trailing accessors that are permitted to differ.
   602		case OINDEX:
   603			if mayAffectMemory(dst.Right) || mayAffectMemory(src.Right) {
   604				return false
   605			}
   606		default:
   607			return false
   608		}
   609	
   610		// The expression prefix must be both "safe" and identical.
   611		return samesafeexpr(dst.Left, src.Left)
   612	}
   613	
   614	// mayAffectMemory reports whether n evaluation may affect program memory state.
   615	// If expression can't affect it, then it can be safely ignored by the escape analysis.
   616	func mayAffectMemory(n *Node) bool {
   617		// We may want to use "memory safe" black list instead of general
   618		// "side-effect free", which can include all calls and other ops
   619		// that can affect allocate or change global state.
   620		// It's safer to start from a whitelist for now.
   621		//
   622		// We're ignoring things like division by zero, index out of range,
   623		// and nil pointer dereference here.
   624		switch n.Op {
   625		case ONAME, OCLOSUREVAR, OLITERAL:
   626			return false
   627	
   628		// Left+Right group.
   629		case OINDEX, OADD, OSUB, OOR, OXOR, OMUL, OLSH, ORSH, OAND, OANDNOT, ODIV, OMOD:
   630			return mayAffectMemory(n.Left) || mayAffectMemory(n.Right)
   631	
   632		// Left group.
   633		case ODOT, ODOTPTR, ODEREF, OCONVNOP, OCONV, OLEN, OCAP,
   634			ONOT, OBITNOT, OPLUS, ONEG, OALIGNOF, OOFFSETOF, OSIZEOF:
   635			return mayAffectMemory(n.Left)
   636	
   637		default:
   638			return true
   639		}
   640	}
   641	
   642	func mustHeapAlloc(n *Node) bool {
   643		// TODO(mdempsky): Cleanup this mess.
   644		return n.Type != nil &&
   645			(n.Type.Width > maxStackVarSize ||
   646				(n.Op == ONEW || n.Op == OPTRLIT) && n.Type.Elem().Width >= maxImplicitStackVarSize ||
   647				n.Op == OMAKESLICE && !isSmallMakeSlice(n))
   648	}
   649	
   650	func (e *EscState) esc(n *Node, parent *Node) {
   651		if n == nil {
   652			return
   653		}
   654	
   655		lno := setlineno(n)
   656	
   657		// ninit logically runs at a different loopdepth than the rest of the for loop.
   658		e.esclist(n.Ninit, n)
   659	
   660		if n.Op == OFOR || n.Op == OFORUNTIL || n.Op == ORANGE {
   661			e.loopdepth++
   662		}
   663	
   664		// type switch variables have no ODCL.
   665		// process type switch as declaration.
   666		// must happen before processing of switch body,
   667		// so before recursion.
   668		if n.Op == OSWITCH && n.Left != nil && n.Left.Op == OTYPESW {
   669			for _, cas := range n.List.Slice() { // cases
   670				// it.N().Rlist is the variable per case
   671				if cas.Rlist.Len() != 0 {
   672					e.nodeEscState(cas.Rlist.First()).Loopdepth = e.loopdepth
   673				}
   674			}
   675		}
   676	
   677		// Big stuff and non-constant-sized stuff escapes unconditionally.
   678		// "Big" conditions that were scattered around in walk have been
   679		// gathered here.
   680		if n.Esc != EscHeap && mustHeapAlloc(n) {
   681			// isSmallMakeSlice returns false for non-constant len/cap.
   682			// If that's the case, print a more accurate escape reason.
   683			var msgVerb, escapeMsg string
   684			if n.Op == OMAKESLICE && (!Isconst(n.Left, CTINT) || !Isconst(n.Right, CTINT)) {
   685				msgVerb, escapeMsg = "has ", "non-constant size"
   686			} else {
   687				msgVerb, escapeMsg = "is ", "too large for stack"
   688			}
   689	
   690			if Debug['m'] > 2 {
   691				Warnl(n.Pos, "%v "+msgVerb+escapeMsg, n)
   692			}
   693			n.Esc = EscHeap
   694			addrescapes(n)
   695			e.escassignSinkWhy(n, n, escapeMsg) // TODO category: tooLarge
   696		}
   697	
   698		e.esc(n.Left, n)
   699	
   700		if n.Op == ORANGE {
   701			// ORANGE node's Right is evaluated before the loop
   702			e.loopdepth--
   703		}
   704	
   705		e.esc(n.Right, n)
   706	
   707		if n.Op == ORANGE {
   708			e.loopdepth++
   709		}
   710	
   711		e.esclist(n.Nbody, n)
   712		e.esclist(n.List, n)
   713		e.esclist(n.Rlist, n)
   714	
   715		if n.Op == OFOR || n.Op == OFORUNTIL || n.Op == ORANGE {
   716			e.loopdepth--
   717		}
   718	
   719		if Debug['m'] > 2 {
   720			fmt.Printf("%v:[%d] %v esc: %v\n", linestr(lineno), e.loopdepth, funcSym(Curfn), n)
   721		}
   722	
   723	opSwitch:
   724		switch n.Op {
   725		// Record loop depth at declaration.
   726		case ODCL:
   727			if n.Left != nil {
   728				e.nodeEscState(n.Left).Loopdepth = e.loopdepth
   729			}
   730	
   731		case OLABEL:
   732			switch asNode(n.Sym.Label) {
   733			case &nonlooping:
   734				if Debug['m'] > 2 {
   735					fmt.Printf("%v:%v non-looping label\n", linestr(lineno), n)
   736				}
   737			case &looping:
   738				if Debug['m'] > 2 {
   739					fmt.Printf("%v: %v looping label\n", linestr(lineno), n)
   740				}
   741				e.loopdepth++
   742			}
   743	
   744			n.Sym.Label = nil
   745	
   746		case ORANGE:
   747			if n.List.Len() >= 2 {
   748				// Everything but fixed array is a dereference.
   749	
   750				// If fixed array is really the address of fixed array,
   751				// it is also a dereference, because it is implicitly
   752				// dereferenced (see #12588)
   753				if n.Type.IsArray() &&
   754					!(n.Right.Type.IsPtr() && types.Identical(n.Right.Type.Elem(), n.Type)) {
   755					e.escassignWhyWhere(n.List.Second(), n.Right, "range", n)
   756				} else {
   757					e.escassignDereference(n.List.Second(), n.Right, e.stepAssignWhere(n.List.Second(), n.Right, "range-deref", n))
   758				}
   759			}
   760	
   761		case OSWITCH:
   762			if n.Left != nil && n.Left.Op == OTYPESW {
   763				for _, cas := range n.List.Slice() {
   764					// cases
   765					// n.Left.Right is the argument of the .(type),
   766					// it.N().Rlist is the variable per case
   767					if cas.Rlist.Len() != 0 {
   768						e.escassignWhyWhere(cas.Rlist.First(), n.Left.Right, "switch case", n)
   769					}
   770				}
   771			}
   772	
   773		case OAS, OASOP:
   774			// Filter out some no-op assignments for escape analysis.
   775			if isSelfAssign(n.Left, n.Right) {
   776				if Debug['m'] != 0 {
   777					Warnl(n.Pos, "%v ignoring self-assignment in %S", e.curfnSym(n), n)
   778				}
   779				break
   780			}
   781	
   782			e.escassign(n.Left, n.Right, e.stepAssignWhere(nil, nil, "", n))
   783	
   784		case OAS2: // x,y = a,b
   785			if n.List.Len() == n.Rlist.Len() {
   786				rs := n.Rlist.Slice()
   787				where := n
   788				for i, n := range n.List.Slice() {
   789					e.escassignWhyWhere(n, rs[i], "assign-pair", where)
   790				}
   791			}
   792	
   793		case OAS2RECV: // v, ok = <-ch
   794			e.escassignWhyWhere(n.List.First(), n.Rlist.First(), "assign-pair-receive", n)
   795		case OAS2MAPR: // v, ok = m[k]
   796			e.escassignWhyWhere(n.List.First(), n.Rlist.First(), "assign-pair-mapr", n)
   797		case OAS2DOTTYPE: // v, ok = x.(type)
   798			e.escassignWhyWhere(n.List.First(), n.Rlist.First(), "assign-pair-dot-type", n)
   799	
   800		case OSEND: // ch <- x
   801			e.escassignSinkWhy(n, n.Right, "send")
   802	
   803		case ODEFER:
   804			if e.loopdepth == 1 { // top level
   805				n.Esc = EscNever // force stack allocation of defer record (see ssa.go)
   806				break
   807			}
   808			// arguments leak out of scope
   809			// TODO: leak to a dummy node instead
   810			// defer f(x) - f and x escape
   811			e.escassignSinkWhy(n, n.Left.Left, "defer func")
   812			e.escassignSinkWhy(n, n.Left.Right, "defer func ...") // ODDDARG for call
   813			for _, arg := range n.Left.List.Slice() {
   814				e.escassignSinkWhy(n, arg, "defer func arg")
   815			}
   816	
   817		case OGO:
   818			// go f(x) - f and x escape
   819			e.escassignSinkWhy(n, n.Left.Left, "go func")
   820			e.escassignSinkWhy(n, n.Left.Right, "go func ...") // ODDDARG for call
   821			for _, arg := range n.Left.List.Slice() {
   822				e.escassignSinkWhy(n, arg, "go func arg")
   823			}
   824	
   825		case OCALLMETH, OCALLFUNC, OCALLINTER:
   826			e.esccall(n, parent)
   827	
   828			// esccall already done on n.Rlist.First()
   829			// tie its Retval to n.List
   830		case OAS2FUNC: // x,y = f()
   831			rs := e.nodeEscState(n.Rlist.First()).Retval.Slice()
   832			where := n
   833			for i, n := range n.List.Slice() {
   834				if i >= len(rs) {
   835					break
   836				}
   837				e.escassignWhyWhere(n, rs[i], "assign-pair-func-call", where)
   838			}
   839			if n.List.Len() != len(rs) {
   840				Fatalf("esc oas2func")
   841			}
   842	
   843		case ORETURN:
   844			retList := n.List
   845			if retList.Len() == 1 && Curfn.Type.NumResults() > 1 {
   846				// OAS2FUNC in disguise
   847				// esccall already done on n.List.First()
   848				// tie e.nodeEscState(n.List.First()).Retval to Curfn.Func.Dcl PPARAMOUT's
   849				retList = e.nodeEscState(n.List.First()).Retval
   850			}
   851	
   852			i := 0
   853			for _, lrn := range Curfn.Func.Dcl {
   854				if i >= retList.Len() {
   855					break
   856				}
   857				if lrn.Op != ONAME || lrn.Class() != PPARAMOUT {
   858					continue
   859				}
   860				e.escassignWhyWhere(lrn, retList.Index(i), "return", n)
   861				i++
   862			}
   863	
   864			if i < retList.Len() {
   865				Fatalf("esc return list")
   866			}
   867	
   868			// Argument could leak through recover.
   869		case OPANIC:
   870			e.escassignSinkWhy(n, n.Left, "panic")
   871	
   872		case OAPPEND:
   873			if !n.IsDDD() {
   874				for _, nn := range n.List.Slice()[1:] {
   875					e.escassignSinkWhy(n, nn, "appended to slice") // lose track of assign to dereference
   876				}
   877			} else {
   878				// append(slice1, slice2...) -- slice2 itself does not escape, but contents do.
   879				slice2 := n.List.Second()
   880				e.escassignDereference(&e.theSink, slice2, e.stepAssignWhere(n, slice2, "appended slice...", n)) // lose track of assign of dereference
   881				if Debug['m'] > 3 {
   882					Warnl(n.Pos, "%v special treatment of append(slice1, slice2...) %S", e.curfnSym(n), n)
   883				}
   884			}
   885			e.escassignDereference(&e.theSink, n.List.First(), e.stepAssignWhere(n, n.List.First(), "appendee slice", n)) // The original elements are now leaked, too
   886	
   887		case OCOPY:
   888			e.escassignDereference(&e.theSink, n.Right, e.stepAssignWhere(n, n.Right, "copied slice", n)) // lose track of assign of dereference
   889	
   890		case OCONV, OCONVNOP:
   891			e.escassignWhyWhere(n, n.Left, "converted", n)
   892	
   893		case OCONVIFACE:
   894			e.track(n)
   895			e.escassignWhyWhere(n, n.Left, "interface-converted", n)
   896	
   897		case OARRAYLIT:
   898			// Link values to array
   899			for _, elt := range n.List.Slice() {
   900				if elt.Op == OKEY {
   901					elt = elt.Right
   902				}
   903				e.escassign(n, elt, e.stepAssignWhere(n, elt, "array literal element", n))
   904			}
   905	
   906		case OSLICELIT:
   907			// Slice is not leaked until proven otherwise
   908			e.track(n)
   909			// Link values to slice
   910			for _, elt := range n.List.Slice() {
   911				if elt.Op == OKEY {
   912					elt = elt.Right
   913				}
   914				e.escassign(n, elt, e.stepAssignWhere(n, elt, "slice literal element", n))
   915			}
   916	
   917			// Link values to struct.
   918		case OSTRUCTLIT:
   919			for _, elt := range n.List.Slice() {
   920				e.escassignWhyWhere(n, elt.Left, "struct literal element", n)
   921			}
   922	
   923		case OPTRLIT:
   924			e.track(n)
   925	
   926			// Link OSTRUCTLIT to OPTRLIT; if OPTRLIT escapes, OSTRUCTLIT elements do too.
   927			e.escassignWhyWhere(n, n.Left, "pointer literal [assign]", n)
   928	
   929		case OCALLPART:
   930			e.track(n)
   931	
   932			// Contents make it to memory, lose track.
   933			e.escassignSinkWhy(n, n.Left, "call part")
   934	
   935		case OMAPLIT:
   936			e.track(n)
   937			// Keys and values make it to memory, lose track.
   938			for _, elt := range n.List.Slice() {
   939				e.escassignSinkWhy(n, elt.Left, "map literal key")
   940				e.escassignSinkWhy(n, elt.Right, "map literal value")
   941			}
   942	
   943		case OCLOSURE:
   944			// Link addresses of captured variables to closure.
   945			for _, v := range n.Func.Closure.Func.Cvars.Slice() {
   946				if v.Op == OXXX { // unnamed out argument; see dcl.go:/^funcargs
   947					continue
   948				}
   949				a := v.Name.Defn
   950				if !v.Name.Byval() {
   951					a = nod(OADDR, a, nil)
   952					a.Pos = v.Pos
   953					e.nodeEscState(a).Loopdepth = e.loopdepth
   954					a = typecheck(a, ctxExpr)
   955				}
   956	
   957				e.escassignWhyWhere(n, a, "captured by a closure", n)
   958			}
   959			fallthrough
   960	
   961		case OMAKECHAN,
   962			OMAKEMAP,
   963			OMAKESLICE,
   964			ONEW,
   965			ORUNES2STR,
   966			OBYTES2STR,
   967			OSTR2RUNES,
   968			OSTR2BYTES,
   969			ORUNESTR:
   970			e.track(n)
   971	
   972		case OADDSTR:
   973			e.track(n)
   974			// Arguments of OADDSTR do not escape.
   975	
   976		case OADDR:
   977			// current loop depth is an upper bound on actual loop depth
   978			// of addressed value.
   979			e.track(n)
   980	
   981			// for &x, use loop depth of x if known.
   982			// it should always be known, but if not, be conservative
   983			// and keep the current loop depth.
   984			if n.Left.Op == ONAME {
   985				switch n.Left.Class() {
   986				// PPARAM is loop depth 1 always.
   987				// PPARAMOUT is loop depth 0 for writes
   988				// but considered loop depth 1 for address-of,
   989				// so that writing the address of one result
   990				// to another (or the same) result makes the
   991				// first result move to the heap.
   992				case PPARAM, PPARAMOUT:
   993					nE := e.nodeEscState(n)
   994					nE.Loopdepth = 1
   995					break opSwitch
   996				}
   997			}
   998			nE := e.nodeEscState(n)
   999			leftE := e.nodeEscState(n.Left)
  1000			if leftE.Loopdepth != 0 {
  1001				nE.Loopdepth = leftE.Loopdepth
  1002			}
  1003	
  1004		case ODOT,
  1005			ODOTPTR,
  1006			OINDEX:
  1007			// Propagate the loopdepth of t to t.field.
  1008			if n.Left.Op != OLITERAL { // OLITERAL node doesn't have esc state
  1009				e.nodeEscState(n).Loopdepth = e.nodeEscState(n.Left).Loopdepth
  1010			}
  1011		}
  1012	
  1013		lineno = lno
  1014	}
  1015	
  1016	// escassignWhyWhere bundles a common case of
  1017	// escassign(e, dst, src, e.stepAssignWhere(dst, src, reason, where))
  1018	func (e *EscState) escassignWhyWhere(dst, src *Node, reason string, where *Node) {
  1019		var step *EscStep
  1020		if Debug['m'] != 0 {
  1021			step = e.stepAssignWhere(dst, src, reason, where)
  1022		}
  1023		e.escassign(dst, src, step)
  1024	}
  1025	
  1026	// escassignSinkWhy bundles a common case of
  1027	// escassign(e, &e.theSink, src, e.stepAssign(nil, dst, src, reason))
  1028	func (e *EscState) escassignSinkWhy(dst, src *Node, reason string) {
  1029		var step *EscStep
  1030		if Debug['m'] != 0 {
  1031			step = e.stepAssign(nil, dst, src, reason)
  1032		}
  1033		e.escassign(&e.theSink, src, step)
  1034	}
  1035	
  1036	// escassignSinkWhyWhere is escassignSinkWhy but includes a call site
  1037	// for accurate location reporting.
  1038	func (e *EscState) escassignSinkWhyWhere(dst, src *Node, reason string, call *Node) {
  1039		var step *EscStep
  1040		if Debug['m'] != 0 {
  1041			step = e.stepAssignWhere(dst, src, reason, call)
  1042		}
  1043		e.escassign(&e.theSink, src, step)
  1044	}
  1045	
  1046	// Assert that expr somehow gets assigned to dst, if non nil.  for
  1047	// dst==nil, any name node expr still must be marked as being
  1048	// evaluated in curfn.	For expr==nil, dst must still be examined for
  1049	// evaluations inside it (e.g *f(x) = y)
  1050	func (e *EscState) escassign(dst, src *Node, step *EscStep) {
  1051		if dst.isBlank() || dst == nil || src == nil || src.Op == ONONAME || src.Op == OXXX {
  1052			return
  1053		}
  1054	
  1055		if Debug['m'] > 2 {
  1056			fmt.Printf("%v:[%d] %v escassign: %S(%0j)[%v] = %S(%0j)[%v]\n",
  1057				linestr(lineno), e.loopdepth, funcSym(Curfn),
  1058				dst, dst, dst.Op,
  1059				src, src, src.Op)
  1060		}
  1061	
  1062		setlineno(dst)
  1063	
  1064		originalDst := dst
  1065		dstwhy := "assigned"
  1066	
  1067		// Analyze lhs of assignment.
  1068		// Replace dst with &e.theSink if we can't track it.
  1069		switch dst.Op {
  1070		default:
  1071			Dump("dst", dst)
  1072			Fatalf("escassign: unexpected dst")
  1073	
  1074		case OARRAYLIT,
  1075			OSLICELIT,
  1076			OCLOSURE,
  1077			OCONV,
  1078			OCONVIFACE,
  1079			OCONVNOP,
  1080			OMAPLIT,
  1081			OSTRUCTLIT,
  1082			OPTRLIT,
  1083			ODDDARG,
  1084			OCALLPART:
  1085	
  1086		case ONAME:
  1087			if dst.Class() == PEXTERN {
  1088				dstwhy = "assigned to top level variable"
  1089				dst = &e.theSink
  1090			}
  1091	
  1092		case ODOT: // treat "dst.x = src" as "dst = src"
  1093			e.escassign(dst.Left, src, e.stepAssign(step, originalDst, src, "dot-equals"))
  1094			return
  1095	
  1096		case OINDEX:
  1097			if dst.Left.Type.IsArray() {
  1098				e.escassign(dst.Left, src, e.stepAssign(step, originalDst, src, "array-element-equals"))
  1099				return
  1100			}
  1101	
  1102			dstwhy = "slice-element-equals"
  1103			dst = &e.theSink // lose track of dereference
  1104	
  1105		case ODEREF:
  1106			dstwhy = "star-equals"
  1107			dst = &e.theSink // lose track of dereference
  1108	
  1109		case ODOTPTR:
  1110			dstwhy = "star-dot-equals"
  1111			dst = &e.theSink // lose track of dereference
  1112	
  1113			// lose track of key and value
  1114		case OINDEXMAP:
  1115			e.escassign(&e.theSink, dst.Right, e.stepAssign(nil, originalDst, src, "key of map put"))
  1116			dstwhy = "value of map put"
  1117			dst = &e.theSink
  1118		}
  1119	
  1120		lno := setlineno(src)
  1121		e.pdepth++
  1122	
  1123		switch src.Op {
  1124		case OADDR, // dst = &x
  1125			ODEREF,  // dst = *x
  1126			ODOTPTR, // dst = (*x).f
  1127			ONAME,
  1128			ODDDARG,
  1129			OPTRLIT,
  1130			OARRAYLIT,
  1131			OSLICELIT,
  1132			OMAPLIT,
  1133			OSTRUCTLIT,
  1134			OMAKECHAN,
  1135			OMAKEMAP,
  1136			OMAKESLICE,
  1137			ORUNES2STR,
  1138			OBYTES2STR,
  1139			OSTR2RUNES,
  1140			OSTR2BYTES,
  1141			OADDSTR,
  1142			ONEW,
  1143			OCALLPART,
  1144			ORUNESTR,
  1145			OCONVIFACE:
  1146			e.escflows(dst, src, e.stepAssign(step, originalDst, src, dstwhy))
  1147	
  1148		case OCLOSURE:
  1149			// OCLOSURE is lowered to OPTRLIT,
  1150			// insert OADDR to account for the additional indirection.
  1151			a := nod(OADDR, src, nil)
  1152			a.Pos = src.Pos
  1153			e.nodeEscState(a).Loopdepth = e.nodeEscState(src).Loopdepth
  1154			a.Type = types.NewPtr(src.Type)
  1155			e.escflows(dst, a, e.stepAssign(nil, originalDst, src, dstwhy))
  1156	
  1157		// Flowing multiple returns to a single dst happens when
  1158		// analyzing "go f(g())": here g() flows to sink (issue 4529).
  1159		case OCALLMETH, OCALLFUNC, OCALLINTER:
  1160			for _, n := range e.nodeEscState(src).Retval.Slice() {
  1161				e.escflows(dst, n, e.stepAssign(nil, originalDst, n, dstwhy))
  1162			}
  1163	
  1164			// A non-pointer escaping from a struct does not concern us.
  1165		case ODOT:
  1166			if src.Type != nil && !types.Haspointers(src.Type) {
  1167				break
  1168			}
  1169			fallthrough
  1170	
  1171			// Conversions, field access, slice all preserve the input value.
  1172		case OCONV,
  1173			OCONVNOP,
  1174			ODOTMETH,
  1175			// treat recv.meth as a value with recv in it, only happens in ODEFER and OGO
  1176			// iface.method already leaks iface in esccall, no need to put in extra ODOTINTER edge here
  1177			OSLICE,
  1178			OSLICE3,
  1179			OSLICEARR,
  1180			OSLICE3ARR,
  1181			OSLICESTR:
  1182			// Conversions, field access, slice all preserve the input value.
  1183			e.escassign(dst, src.Left, e.stepAssign(step, originalDst, src, dstwhy))
  1184	
  1185		case ODOTTYPE,
  1186			ODOTTYPE2:
  1187			if src.Type != nil && !types.Haspointers(src.Type) {
  1188				break
  1189			}
  1190			e.escassign(dst, src.Left, e.stepAssign(step, originalDst, src, dstwhy))
  1191	
  1192		case OAPPEND:
  1193			// Append returns first argument.
  1194			// Subsequent arguments are already leaked because they are operands to append.
  1195			e.escassign(dst, src.List.First(), e.stepAssign(step, dst, src.List.First(), dstwhy))
  1196	
  1197		case OINDEX:
  1198			// Index of array preserves input value.
  1199			if src.Left.Type.IsArray() {
  1200				e.escassign(dst, src.Left, e.stepAssign(step, originalDst, src, dstwhy))
  1201			} else {
  1202				e.escflows(dst, src, e.stepAssign(step, originalDst, src, dstwhy))
  1203			}
  1204	
  1205		// Might be pointer arithmetic, in which case
  1206		// the operands flow into the result.
  1207		// TODO(rsc): Decide what the story is here. This is unsettling.
  1208		case OADD,
  1209			OSUB,
  1210			OOR,
  1211			OXOR,
  1212			OMUL,
  1213			ODIV,
  1214			OMOD,
  1215			OLSH,
  1216			ORSH,
  1217			OAND,
  1218			OANDNOT,
  1219			OPLUS,
  1220			ONEG,
  1221			OBITNOT:
  1222			e.escassign(dst, src.Left, e.stepAssign(step, originalDst, src, dstwhy))
  1223	
  1224			e.escassign(dst, src.Right, e.stepAssign(step, originalDst, src, dstwhy))
  1225		}
  1226	
  1227		e.pdepth--
  1228		lineno = lno
  1229	}
  1230	
  1231	// Common case for escapes is 16 bits 000000000xxxEEEE
  1232	// where commonest cases for xxx encoding in-to-out pointer
  1233	//  flow are 000, 001, 010, 011  and EEEE is computed Esc bits.
  1234	// Note width of xxx depends on value of constant
  1235	// bitsPerOutputInTag -- expect 2 or 3, so in practice the
  1236	// tag cache array is 64 or 128 long. Some entries will
  1237	// never be populated.
  1238	var tags [1 << (bitsPerOutputInTag + EscReturnBits)]string
  1239	
  1240	// mktag returns the string representation for an escape analysis tag.
  1241	func mktag(mask int) string {
  1242		switch mask & EscMask {
  1243		case EscNone, EscReturn:
  1244		default:
  1245			Fatalf("escape mktag")
  1246		}
  1247	
  1248		if mask < len(tags) && tags[mask] != "" {
  1249			return tags[mask]
  1250		}
  1251	
  1252		s := fmt.Sprintf("esc:0x%x", mask)
  1253		if mask < len(tags) {
  1254			tags[mask] = s
  1255		}
  1256		return s
  1257	}
  1258	
  1259	// parsetag decodes an escape analysis tag and returns the esc value.
  1260	func parsetag(note string) uint16 {
  1261		if !strings.HasPrefix(note, "esc:") {
  1262			return EscUnknown
  1263		}
  1264		n, _ := strconv.ParseInt(note[4:], 0, 0)
  1265		em := uint16(n)
  1266		if em == 0 {
  1267			return EscNone
  1268		}
  1269		return em
  1270	}
  1271	
  1272	// describeEscape returns a string describing the escape tag.
  1273	// The result is either one of {EscUnknown, EscNone, EscHeap} which all have no further annotation
  1274	// or a description of parameter flow, which takes the form of an optional "contentToHeap"
  1275	// indicating that the content of this parameter is leaked to the heap, followed by a sequence
  1276	// of level encodings separated by spaces, one for each parameter, where _ means no flow,
  1277	// = means direct flow, and N asterisks (*) encodes content (obtained by indirection) flow.
  1278	// e.g., "contentToHeap _ =" means that a parameter's content (one or more dereferences)
  1279	// escapes to the heap, the parameter does not leak to the first output, but does leak directly
  1280	// to the second output (and if there are more than two outputs, there is no flow to those.)
  1281	func describeEscape(em uint16) string {
  1282		var s string
  1283		switch em & EscMask {
  1284		case EscUnknown:
  1285			s = "EscUnknown"
  1286		case EscNone:
  1287			s = "EscNone"
  1288		case EscHeap:
  1289			s = "EscHeap"
  1290		case EscReturn:
  1291			s = "EscReturn"
  1292		}
  1293		if em&EscContentEscapes != 0 {
  1294			if s != "" {
  1295				s += " "
  1296			}
  1297			s += "contentToHeap"
  1298		}
  1299		for em >>= EscReturnBits; em != 0; em >>= bitsPerOutputInTag {
  1300			// See encoding description above
  1301			if s != "" {
  1302				s += " "
  1303			}
  1304			switch embits := em & bitsMaskForTag; embits {
  1305			case 0:
  1306				s += "_"
  1307			case 1:
  1308				s += "="
  1309			default:
  1310				for i := uint16(0); i < embits-1; i++ {
  1311					s += "*"
  1312				}
  1313			}
  1314	
  1315		}
  1316		return s
  1317	}
  1318	
  1319	// escassignfromtag models the input-to-output assignment flow of one of a function
  1320	// calls arguments, where the flow is encoded in "note".
  1321	func (e *EscState) escassignfromtag(note string, dsts Nodes, src, call *Node) uint16 {
  1322		em := parsetag(note)
  1323		if src.Op == OLITERAL {
  1324			return em
  1325		}
  1326	
  1327		if Debug['m'] > 3 {
  1328			fmt.Printf("%v::assignfromtag:: src=%S, em=%s\n",
  1329				linestr(lineno), src, describeEscape(em))
  1330		}
  1331	
  1332		if em == EscUnknown {
  1333			e.escassignSinkWhyWhere(src, src, "passed to call[argument escapes]", call)
  1334			return em
  1335		}
  1336	
  1337		if em == EscNone {
  1338			return em
  1339		}
  1340	
  1341		// If content inside parameter (reached via indirection)
  1342		// escapes to heap, mark as such.
  1343		if em&EscContentEscapes != 0 {
  1344			e.escassign(&e.theSink, e.addDereference(src), e.stepAssignWhere(src, src, "passed to call[argument content escapes]", call))
  1345		}
  1346	
  1347		em0 := em
  1348		dstsi := 0
  1349		for em >>= EscReturnBits; em != 0 && dstsi < dsts.Len(); em >>= bitsPerOutputInTag {
  1350			// Prefer the lowest-level path to the reference (for escape purposes).
  1351			// Two-bit encoding (for example. 1, 3, and 4 bits are other options)
  1352			//  01 = 0-level
  1353			//  10 = 1-level, (content escapes),
  1354			//  11 = 2-level, (content of content escapes),
  1355			embits := em & bitsMaskForTag
  1356			if embits > 0 {
  1357				n := src
  1358				for i := uint16(0); i < embits-1; i++ {
  1359					n = e.addDereference(n) // encode level>0 as indirections
  1360				}
  1361				e.escassign(dsts.Index(dstsi), n, e.stepAssignWhere(dsts.Index(dstsi), src, "passed-to-and-returned-from-call", call))
  1362			}
  1363			dstsi++
  1364		}
  1365		// If there are too many outputs to fit in the tag,
  1366		// that is handled at the encoding end as EscHeap,
  1367		// so there is no need to check here.
  1368	
  1369		if em != 0 && dstsi >= dsts.Len() {
  1370			Fatalf("corrupt esc tag %q or messed up escretval list\n", note)
  1371		}
  1372		return em0
  1373	}
  1374	
  1375	func (e *EscState) escassignDereference(dst *Node, src *Node, step *EscStep) {
  1376		if src.Op == OLITERAL {
  1377			return
  1378		}
  1379		e.escassign(dst, e.addDereference(src), step)
  1380	}
  1381	
  1382	// addDereference constructs a suitable ODEREF note applied to src.
  1383	// Because this is for purposes of escape accounting, not execution,
  1384	// some semantically dubious node combinations are (currently) possible.
  1385	func (e *EscState) addDereference(n *Node) *Node {
  1386		ind := nod(ODEREF, n, nil)
  1387		e.nodeEscState(ind).Loopdepth = e.nodeEscState(n).Loopdepth
  1388		ind.Pos = n.Pos
  1389		t := n.Type
  1390		if t.IsPtr() || t.IsSlice() {
  1391			// This should model our own sloppy use of ODEREF to encode
  1392			// decreasing levels of indirection; i.e., "indirecting" a slice
  1393			// yields the type of an element.
  1394			t = t.Elem()
  1395		} else if t.IsString() {
  1396			t = types.Types[TUINT8]
  1397		}
  1398		ind.Type = t
  1399		return ind
  1400	}
  1401	
  1402	// escNoteOutputParamFlow encodes maxEncodedLevel/.../1/0-level flow to the vargen'th parameter.
  1403	// Levels greater than maxEncodedLevel are replaced with maxEncodedLevel.
  1404	// If the encoding cannot describe the modified input level and output number, then EscHeap is returned.
  1405	func escNoteOutputParamFlow(e uint16, vargen int32, level Level) uint16 {
  1406		// Flow+level is encoded in two bits.
  1407		// 00 = not flow, xx = level+1 for 0 <= level <= maxEncodedLevel
  1408		// 16 bits for Esc allows 6x2bits or 4x3bits or 3x4bits if additional information would be useful.
  1409		if level.int() <= 0 && level.guaranteedDereference() > 0 {
  1410			return escMax(e|EscContentEscapes, EscNone) // At least one deref, thus only content.
  1411		}
  1412		if level.int() < 0 {
  1413			return EscHeap
  1414		}
  1415		if level.int() > maxEncodedLevel {
  1416			// Cannot encode larger values than maxEncodedLevel.
  1417			level = levelFrom(maxEncodedLevel)
  1418		}
  1419		encoded := uint16(level.int() + 1)
  1420	
  1421		shift := uint(bitsPerOutputInTag*(vargen-1) + EscReturnBits)
  1422		old := (e >> shift) & bitsMaskForTag
  1423		if old == 0 || encoded != 0 && encoded < old {
  1424			old = encoded
  1425		}
  1426	
  1427		encodedFlow := old << shift
  1428		if (encodedFlow>>shift)&bitsMaskForTag != old {
  1429			// Encoding failure defaults to heap.
  1430			return EscHeap
  1431		}
  1432	
  1433		return (e &^ (bitsMaskForTag << shift)) | encodedFlow
  1434	}
  1435	
  1436	func (e *EscState) initEscRetval(call *Node, fntype *types.Type) {
  1437		cE := e.nodeEscState(call)
  1438		cE.Retval.Set(nil) // Suspect this is not nil for indirect calls.
  1439		for i, f := range fntype.Results().Fields().Slice() {
  1440			buf := fmt.Sprintf(".out%d", i)
  1441			ret := newname(lookup(buf))
  1442			ret.SetAddable(false) // TODO(mdempsky): Seems suspicious.
  1443			ret.Type = f.Type
  1444			ret.SetClass(PAUTO)
  1445			ret.Name.Curfn = Curfn
  1446			e.nodeEscState(ret).Loopdepth = e.loopdepth
  1447			ret.Name.SetUsed(true)
  1448			ret.Pos = call.Pos
  1449			cE.Retval.Append(ret)
  1450		}
  1451	}
  1452	
  1453	// This is a bit messier than fortunate, pulled out of esc's big
  1454	// switch for clarity. We either have the paramnodes, which may be
  1455	// connected to other things through flows or we have the parameter type
  1456	// nodes, which may be marked "noescape". Navigating the ast is slightly
  1457	// different for methods vs plain functions and for imported vs
  1458	// this-package
  1459	func (e *EscState) esccall(call *Node, parent *Node) {
  1460		var fntype *types.Type
  1461		var indirect bool
  1462		var fn *Node
  1463		switch call.Op {
  1464		default:
  1465			Fatalf("esccall")
  1466	
  1467		case OCALLFUNC:
  1468			fn = call.Left
  1469			fntype = fn.Type
  1470			indirect = fn.Op != ONAME || fn.Class() != PFUNC
  1471	
  1472		case OCALLMETH:
  1473			fn = asNode(call.Left.Sym.Def)
  1474			if fn != nil {
  1475				fntype = fn.Type
  1476			} else {
  1477				fntype = call.Left.Type
  1478			}
  1479	
  1480		case OCALLINTER:
  1481			fntype = call.Left.Type
  1482			indirect = true
  1483		}
  1484	
  1485		argList := call.List
  1486		args := argList.Slice()
  1487	
  1488		if indirect {
  1489			// We know nothing!
  1490			// Leak all the parameters
  1491			for _, arg := range args {
  1492				e.escassignSinkWhy(call, arg, "parameter to indirect call")
  1493				if Debug['m'] > 3 {
  1494					fmt.Printf("%v::esccall:: indirect call <- %S, untracked\n", linestr(lineno), arg)
  1495				}
  1496			}
  1497			// Set up bogus outputs
  1498			e.initEscRetval(call, fntype)
  1499			// If there is a receiver, it also leaks to heap.
  1500			if call.Op != OCALLFUNC {
  1501				rf := fntype.Recv()
  1502				r := call.Left.Left
  1503				if types.Haspointers(rf.Type) {
  1504					e.escassignSinkWhy(call, r, "receiver in indirect call")
  1505				}
  1506			} else { // indirect and OCALLFUNC = could be captured variables, too. (#14409)
  1507				rets := e.nodeEscState(call).Retval.Slice()
  1508				for _, ret := range rets {
  1509					e.escassignDereference(ret, fn, e.stepAssignWhere(ret, fn, "captured by called closure", call))
  1510				}
  1511			}
  1512			return
  1513		}
  1514	
  1515		cE := e.nodeEscState(call)
  1516		if fn != nil && fn.Op == ONAME && fn.Class() == PFUNC &&
  1517			fn.Name.Defn != nil && fn.Name.Defn.Nbody.Len() != 0 && fn.Name.Param.Ntype != nil && fn.Name.Defn.Esc < EscFuncTagged {
  1518			// function in same mutually recursive group. Incorporate into flow graph.
  1519			if Debug['m'] > 3 {
  1520				fmt.Printf("%v::esccall:: %S in recursive group\n", linestr(lineno), call)
  1521			}
  1522	
  1523			if fn.Name.Defn.Esc == EscFuncUnknown || cE.Retval.Len() != 0 {
  1524				Fatalf("graph inconsistency")
  1525			}
  1526	
  1527			i := 0
  1528	
  1529			// Receiver.
  1530			if call.Op != OCALLFUNC {
  1531				rf := fntype.Recv()
  1532				if rf.Sym != nil && !rf.Sym.IsBlank() {
  1533					n := fn.Name.Defn.Func.Dcl[0]
  1534					i++
  1535					if n.Class() != PPARAM {
  1536						Fatalf("esccall: not a parameter %+v", n)
  1537					}
  1538					e.escassignWhyWhere(n, call.Left.Left, "recursive call receiver", call)
  1539				}
  1540			}
  1541	
  1542			// Parameters.
  1543			for _, param := range fntype.Params().FieldSlice() {
  1544				if param.Sym == nil || param.Sym.IsBlank() {
  1545					// Unnamed parameter is not listed in Func.Dcl.
  1546					// But we need to consume the arg.
  1547					if param.IsDDD() && !call.IsDDD() {
  1548						args = nil
  1549					} else {
  1550						args = args[1:]
  1551					}
  1552					continue
  1553				}
  1554	
  1555				n := fn.Name.Defn.Func.Dcl[i]
  1556				i++
  1557				if n.Class() != PPARAM {
  1558					Fatalf("esccall: not a parameter %+v", n)
  1559				}
  1560				if len(args) == 0 {
  1561					continue
  1562				}
  1563				arg := args[0]
  1564				if n.IsDDD() && !call.IsDDD() {
  1565					// Introduce ODDDARG node to represent ... allocation.
  1566					arg = nod(ODDDARG, nil, nil)
  1567					arr := types.NewArray(n.Type.Elem(), int64(len(args)))
  1568					arg.Type = types.NewPtr(arr) // make pointer so it will be tracked
  1569					arg.Pos = call.Pos
  1570					e.track(arg)
  1571					call.Right = arg
  1572				}
  1573				e.escassignWhyWhere(n, arg, "arg to recursive call", call) // TODO this message needs help.
  1574				if arg == args[0] {
  1575					args = args[1:]
  1576					continue
  1577				}
  1578				// "..." arguments are untracked
  1579				for _, a := range args {
  1580					if Debug['m'] > 3 {
  1581						fmt.Printf("%v::esccall:: ... <- %S, untracked\n", linestr(lineno), a)
  1582					}
  1583					e.escassignSinkWhyWhere(arg, a, "... arg to recursive call", call)
  1584				}
  1585				// ... arg consumes all remaining arguments
  1586				args = nil
  1587			}
  1588	
  1589			// Results.
  1590			for _, n := range fn.Name.Defn.Func.Dcl[i:] {
  1591				if n.Class() == PPARAMOUT {
  1592					cE.Retval.Append(n)
  1593				}
  1594			}
  1595	
  1596			// Sanity check: all arguments must be consumed.
  1597			if len(args) != 0 {
  1598				Fatalf("esccall not consumed all args %+v\n", call)
  1599			}
  1600			return
  1601		}
  1602	
  1603		// Imported or completely analyzed function. Use the escape tags.
  1604		if cE.Retval.Len() != 0 {
  1605			Fatalf("esc already decorated call %+v\n", call)
  1606		}
  1607	
  1608		if Debug['m'] > 3 {
  1609			fmt.Printf("%v::esccall:: %S not recursive\n", linestr(lineno), call)
  1610		}
  1611	
  1612		// set up out list on this call node with dummy auto ONAMES in the current (calling) function.
  1613		e.initEscRetval(call, fntype)
  1614	
  1615		// Receiver.
  1616		if call.Op != OCALLFUNC {
  1617			rf := fntype.Recv()
  1618			r := call.Left.Left
  1619			if types.Haspointers(rf.Type) {
  1620				e.escassignfromtag(rf.Note, cE.Retval, r, call)
  1621			}
  1622		}
  1623	
  1624		for i, param := range fntype.Params().FieldSlice() {
  1625			note := param.Note
  1626			var arg *Node
  1627			if param.IsDDD() && !call.IsDDD() {
  1628				rest := args[i:]
  1629				if len(rest) == 0 {
  1630					break
  1631				}
  1632	
  1633				// Introduce ODDDARG node to represent ... allocation.
  1634				arg = nod(ODDDARG, nil, nil)
  1635				arg.Pos = call.Pos
  1636				arr := types.NewArray(param.Type.Elem(), int64(len(rest)))
  1637				arg.Type = types.NewPtr(arr) // make pointer so it will be tracked
  1638				e.track(arg)
  1639				call.Right = arg
  1640	
  1641				// Store arguments into slice for ... arg.
  1642				for _, a := range rest {
  1643					if Debug['m'] > 3 {
  1644						fmt.Printf("%v::esccall:: ... <- %S\n", linestr(lineno), a)
  1645					}
  1646					if note == uintptrEscapesTag {
  1647						e.escassignSinkWhyWhere(arg, a, "arg to uintptrescapes ...", call)
  1648					} else {
  1649						e.escassignWhyWhere(arg, a, "arg to ...", call)
  1650					}
  1651				}
  1652			} else {
  1653				arg = args[i]
  1654				if note == uintptrEscapesTag {
  1655					e.escassignSinkWhy(arg, arg, "escaping uintptr")
  1656				}
  1657			}
  1658	
  1659			if types.Haspointers(param.Type) && e.escassignfromtag(note, cE.Retval, arg, call)&EscMask == EscNone && parent.Op != ODEFER && parent.Op != OGO {
  1660				a := arg
  1661				for a.Op == OCONVNOP {
  1662					a = a.Left
  1663				}
  1664				switch a.Op {
  1665				// The callee has already been analyzed, so its arguments have esc tags.
  1666				// The argument is marked as not escaping at all.
  1667				// Record that fact so that any temporary used for
  1668				// synthesizing this expression can be reclaimed when
  1669				// the function returns.
  1670				// This 'noescape' is even stronger than the usual esc == EscNone.
  1671				// arg.Esc == EscNone means that arg does not escape the current function.
  1672				// arg.SetNoescape(true) here means that arg does not escape this statement
  1673				// in the current function.
  1674				case OCALLPART, OCLOSURE, ODDDARG, OARRAYLIT, OSLICELIT, OPTRLIT, OSTRUCTLIT:
  1675					a.SetNoescape(true)
  1676				}
  1677			}
  1678		}
  1679	}
  1680	
  1681	// escflows records the link src->dst in dst, throwing out some quick wins,
  1682	// and also ensuring that dst is noted as a flow destination.
  1683	func (e *EscState) escflows(dst, src *Node, why *EscStep) {
  1684		if dst == nil || src == nil || dst == src {
  1685			return
  1686		}
  1687	
  1688		// Don't bother building a graph for scalars.
  1689		if src.Type != nil && !types.Haspointers(src.Type) && !isReflectHeaderDataField(src) {
  1690			if Debug['m'] > 3 {
  1691				fmt.Printf("%v::NOT flows:: %S <- %S\n", linestr(lineno), dst, src)
  1692			}
  1693			return
  1694		}
  1695	
  1696		if Debug['m'] > 3 {
  1697			fmt.Printf("%v::flows:: %S <- %S\n", linestr(lineno), dst, src)
  1698		}
  1699	
  1700		dstE := e.nodeEscState(dst)
  1701		if len(dstE.Flowsrc) == 0 {
  1702			e.dsts = append(e.dsts, dst)
  1703			e.dstcount++
  1704		}
  1705	
  1706		e.edgecount++
  1707	
  1708		if why == nil {
  1709			dstE.Flowsrc = append(dstE.Flowsrc, EscStep{src: src})
  1710		} else {
  1711			starwhy := *why
  1712			starwhy.src = src // TODO: need to reconcile this w/ needs of explanations.
  1713			dstE.Flowsrc = append(dstE.Flowsrc, starwhy)
  1714		}
  1715	}
  1716	
  1717	// Whenever we hit a reference node, the level goes up by one, and whenever
  1718	// we hit an OADDR, the level goes down by one. as long as we're on a level > 0
  1719	// finding an OADDR just means we're following the upstream of a dereference,
  1720	// so this address doesn't leak (yet).
  1721	// If level == 0, it means the /value/ of this node can reach the root of this flood.
  1722	// so if this node is an OADDR, its argument should be marked as escaping iff
  1723	// its currfn/e.loopdepth are different from the flood's root.
  1724	// Once an object has been moved to the heap, all of its upstream should be considered
  1725	// escaping to the global scope.
  1726	func (e *EscState) escflood(dst *Node) {
  1727		switch dst.Op {
  1728		case ONAME, OCLOSURE:
  1729		default:
  1730			return
  1731		}
  1732	
  1733		dstE := e.nodeEscState(dst)
  1734		if Debug['m'] > 2 {
  1735			fmt.Printf("\nescflood:%d: dst %S scope:%v[%d]\n", e.walkgen, dst, e.curfnSym(dst), dstE.Loopdepth)
  1736		}
  1737	
  1738		for i := range dstE.Flowsrc {
  1739			e.walkgen++
  1740			s := &dstE.Flowsrc[i]
  1741			s.parent = nil
  1742			e.escwalk(levelFrom(0), dst, s.src, s)
  1743		}
  1744	}
  1745	
  1746	// funcOutputAndInput reports whether dst and src correspond to output and input parameters of the same function.
  1747	func funcOutputAndInput(dst, src *Node) bool {
  1748		// Note if dst is marked as escaping, then "returned" is too weak.
  1749		return dst.Op == ONAME && dst.Class() == PPARAMOUT &&
  1750			src.Op == ONAME && src.Class() == PPARAM && src.Name.Curfn == dst.Name.Curfn
  1751	}
  1752	
  1753	func (es *EscStep) describe(src *Node) {
  1754		if Debug['m'] < 2 {
  1755			return
  1756		}
  1757		step0 := es
  1758		for step := step0; step != nil && !step.busy; step = step.parent {
  1759			// TODO: We get cycles. Trigger is i = &i (where var i interface{})
  1760			step.busy = true
  1761			// The trail is a little odd because of how the
  1762			// graph is constructed.  The link to the current
  1763			// Node is parent.src unless parent is nil in which
  1764			// case it is step.dst.
  1765			nextDest := step.parent
  1766			dst := step.dst
  1767			where := step.where
  1768			if nextDest != nil {
  1769				dst = nextDest.src
  1770			}
  1771			if where == nil {
  1772				where = dst
  1773			}
  1774			Warnl(src.Pos, "\tfrom %v (%s) at %s", dst, step.why, where.Line())
  1775		}
  1776		for step := step0; step != nil && step.busy; step = step.parent {
  1777			step.busy = false
  1778		}
  1779	}
  1780	
  1781	const NOTALOOPDEPTH = -1
  1782	
  1783	func (e *EscState) escwalk(level Level, dst *Node, src *Node, step *EscStep) {
  1784		e.escwalkBody(level, dst, src, step, NOTALOOPDEPTH)
  1785	}
  1786	
  1787	func (e *EscState) escwalkBody(level Level, dst *Node, src *Node, step *EscStep, extraloopdepth int32) {
  1788		if src.Op == OLITERAL {
  1789			return
  1790		}
  1791		srcE := e.nodeEscState(src)
  1792		if srcE.Walkgen == e.walkgen {
  1793			// Esclevels are vectors, do not compare as integers,
  1794			// and must use "min" of old and new to guarantee
  1795			// convergence.
  1796			level = level.min(srcE.Level)
  1797			if level == srcE.Level {
  1798				// Have we been here already with an extraloopdepth,
  1799				// or is the extraloopdepth provided no improvement on
  1800				// what's already been seen?
  1801				if srcE.Maxextraloopdepth >= extraloopdepth || srcE.Loopdepth >= extraloopdepth {
  1802					return
  1803				}
  1804				srcE.Maxextraloopdepth = extraloopdepth
  1805			}
  1806		} else { // srcE.Walkgen < e.walkgen -- first time, reset this.
  1807			srcE.Maxextraloopdepth = NOTALOOPDEPTH
  1808		}
  1809	
  1810		srcE.Walkgen = e.walkgen
  1811		srcE.Level = level
  1812		modSrcLoopdepth := srcE.Loopdepth
  1813	
  1814		if extraloopdepth > modSrcLoopdepth {
  1815			modSrcLoopdepth = extraloopdepth
  1816		}
  1817	
  1818		if Debug['m'] > 2 {
  1819			fmt.Printf("escwalk: level:%d depth:%d %.*s op=%v %S(%0j) scope:%v[%d] extraloopdepth=%v\n",
  1820				level, e.pdepth, e.pdepth, "\t\t\t\t\t\t\t\t\t\t", src.Op, src, src, e.curfnSym(src), srcE.Loopdepth, extraloopdepth)
  1821		}
  1822	
  1823		e.pdepth++
  1824	
  1825		// Input parameter flowing to output parameter?
  1826		var leaks bool
  1827		var osrcesc uint16 // used to prevent duplicate error messages
  1828	
  1829		dstE := e.nodeEscState(dst)
  1830		if funcOutputAndInput(dst, src) && src.Esc&EscMask < EscHeap && dst.Esc != EscHeap {
  1831			// This case handles:
  1832			// 1. return in
  1833			// 2. return &in
  1834			// 3. tmp := in; return &tmp
  1835			// 4. return *in
  1836			if Debug['m'] != 0 {
  1837				if Debug['m'] <= 2 {
  1838					Warnl(src.Pos, "leaking param: %S to result %v level=%v", src, dst.Sym, level.int())
  1839					step.describe(src)
  1840				} else {
  1841					Warnl(src.Pos, "leaking param: %S to result %v level=%v", src, dst.Sym, level)
  1842				}
  1843			}
  1844			if src.Esc&EscMask != EscReturn {
  1845				src.Esc = EscReturn | src.Esc&EscContentEscapes
  1846			}
  1847			src.Esc = escNoteOutputParamFlow(src.Esc, dst.Name.Vargen, level)
  1848			goto recurse
  1849		}
  1850	
  1851		// If parameter content escapes to heap, set EscContentEscapes
  1852		// Note minor confusion around escape from pointer-to-struct vs escape from struct
  1853		if dst.Esc == EscHeap &&
  1854			src.Op == ONAME && src.Class() == PPARAM && src.Esc&EscMask < EscHeap &&
  1855			level.int() > 0 {
  1856			src.Esc = escMax(EscContentEscapes|src.Esc, EscNone)
  1857		}
  1858	
  1859		leaks = level.int() <= 0 && level.guaranteedDereference() <= 0 && dstE.Loopdepth < modSrcLoopdepth
  1860		leaks = leaks || level.int() <= 0 && dst.Esc&EscMask == EscHeap
  1861	
  1862		osrcesc = src.Esc
  1863		switch src.Op {
  1864		case ONAME:
  1865			if src.Class() == PPARAM && (leaks || dstE.Loopdepth < 0) && src.Esc&EscMask < EscHeap {
  1866				if level.guaranteedDereference() > 0 {
  1867					src.Esc = escMax(EscContentEscapes|src.Esc, EscNone)
  1868					if Debug['m'] != 0 {
  1869						if Debug['m'] <= 2 {
  1870							if osrcesc != src.Esc {
  1871								Warnl(src.Pos, "leaking param content: %S", src)
  1872								step.describe(src)
  1873							}
  1874						} else {
  1875							Warnl(src.Pos, "leaking param content: %S level=%v dst.eld=%v src.eld=%v dst=%S",
  1876								src, level, dstE.Loopdepth, modSrcLoopdepth, dst)
  1877						}
  1878					}
  1879				} else {
  1880					src.Esc = EscHeap
  1881					if Debug['m'] != 0 {
  1882						if Debug['m'] <= 2 {
  1883							Warnl(src.Pos, "leaking param: %S", src)
  1884							step.describe(src)
  1885						} else {
  1886							Warnl(src.Pos, "leaking param: %S level=%v dst.eld=%v src.eld=%v dst=%S",
  1887								src, level, dstE.Loopdepth, modSrcLoopdepth, dst)
  1888						}
  1889					}
  1890				}
  1891			}
  1892	
  1893			// Treat a captured closure variable as equivalent to the
  1894			// original variable.
  1895			if src.IsClosureVar() {
  1896				e.escwalk(level, dst, src.Name.Defn, e.stepWalk(dst, src.Name.Defn, "closure-var", step))
  1897			}
  1898	
  1899		case OPTRLIT, OADDR:
  1900			why := "pointer literal"
  1901			if src.Op == OADDR {
  1902				why = "address-of"
  1903			}
  1904			if leaks {
  1905				src.Esc = EscHeap
  1906				if Debug['m'] != 0 && osrcesc != src.Esc && src.Op != OADDR {
  1907					p := src
  1908					if p.Left.Op == OCLOSURE {
  1909						p = p.Left // merely to satisfy error messages in tests
  1910					}
  1911					if Debug['m'] > 2 {
  1912						Warnl(src.Pos, "%S escapes to heap, level=%v, dst=%v dst.eld=%v, src.eld=%v",
  1913							p, level, dst, dstE.Loopdepth, modSrcLoopdepth)
  1914					} else {
  1915						Warnl(src.Pos, "%S escapes to heap", p)
  1916						step.describe(src)
  1917					}
  1918				}
  1919				addrescapes(src.Left)
  1920				e.escwalkBody(level.dec(), dst, src.Left, e.stepWalk(dst, src.Left, why, step), modSrcLoopdepth)
  1921				extraloopdepth = modSrcLoopdepth // passes to recursive case, seems likely a no-op
  1922			} else {
  1923				e.escwalk(level.dec(), dst, src.Left, e.stepWalk(dst, src.Left, why, step))
  1924			}
  1925	
  1926		case OAPPEND:
  1927			e.escwalk(level, dst, src.List.First(), e.stepWalk(dst, src.List.First(), "append-first-arg", step))
  1928	
  1929		case ODDDARG:
  1930			if leaks {
  1931				src.Esc = EscHeap
  1932				if Debug['m'] != 0 && osrcesc != src.Esc {
  1933					Warnl(src.Pos, "%S escapes to heap", src)
  1934					step.describe(src)
  1935				}
  1936				extraloopdepth = modSrcLoopdepth
  1937			}
  1938			// similar to a slice arraylit and its args.
  1939			level = level.dec()
  1940	
  1941		case OSLICELIT:
  1942			for _, elt := range src.List.Slice() {
  1943				if elt.Op == OKEY {
  1944					elt = elt.Right
  1945				}
  1946				e.escwalk(level.dec(), dst, elt, e.stepWalk(dst, elt, "slice-literal-element", step))
  1947			}
  1948	
  1949			fallthrough
  1950	
  1951		case OMAKECHAN,
  1952			OMAKEMAP,
  1953			OMAKESLICE,
  1954			ORUNES2STR,
  1955			OBYTES2STR,
  1956			OSTR2RUNES,
  1957			OSTR2BYTES,
  1958			OADDSTR,
  1959			OMAPLIT,
  1960			ONEW,
  1961			OCLOSURE,
  1962			OCALLPART,
  1963			ORUNESTR,
  1964			OCONVIFACE:
  1965			if leaks {
  1966				src.Esc = EscHeap
  1967				if Debug['m'] != 0 && osrcesc != src.Esc {
  1968					Warnl(src.Pos, "%S escapes to heap", src)
  1969					step.describe(src)
  1970				}
  1971				extraloopdepth = modSrcLoopdepth
  1972				if src.Op == OCONVIFACE {
  1973					lt := src.Left.Type
  1974					if !lt.IsInterface() && !isdirectiface(lt) && types.Haspointers(lt) {
  1975						// We're converting from a non-direct interface type.
  1976						// The interface will hold a heap copy of the data
  1977						// (by calling convT2I or friend). Flow the data to heap.
  1978						// See issue 29353.
  1979						e.escwalk(level, &e.theSink, src.Left, e.stepWalk(dst, src.Left, "interface-converted", step))
  1980					}
  1981				}
  1982			}
  1983	
  1984		case ODOT,
  1985			ODOTTYPE:
  1986			e.escwalk(level, dst, src.Left, e.stepWalk(dst, src.Left, "dot", step))
  1987	
  1988		case
  1989			OSLICE,
  1990			OSLICEARR,
  1991			OSLICE3,
  1992			OSLICE3ARR,
  1993			OSLICESTR:
  1994			e.escwalk(level, dst, src.Left, e.stepWalk(dst, src.Left, "slice", step))
  1995	
  1996		case OINDEX:
  1997			if src.Left.Type.IsArray() {
  1998				e.escwalk(level, dst, src.Left, e.stepWalk(dst, src.Left, "fixed-array-index-of", step))
  1999				break
  2000			}
  2001			fallthrough
  2002	
  2003		case ODOTPTR:
  2004			e.escwalk(level.inc(), dst, src.Left, e.stepWalk(dst, src.Left, "dot of pointer", step))
  2005		case OINDEXMAP:
  2006			e.escwalk(level.inc(), dst, src.Left, e.stepWalk(dst, src.Left, "map index", step))
  2007		case ODEREF:
  2008			e.escwalk(level.inc(), dst, src.Left, e.stepWalk(dst, src.Left, "indirection", step))
  2009	
  2010		// In this case a link went directly to a call, but should really go
  2011		// to the dummy .outN outputs that were created for the call that
  2012		// themselves link to the inputs with levels adjusted.
  2013		// See e.g. #10466
  2014		// This can only happen with functions returning a single result.
  2015		case OCALLMETH, OCALLFUNC, OCALLINTER:
  2016			if srcE.Retval.Len() != 0 {
  2017				if Debug['m'] > 2 {
  2018					fmt.Printf("%v:[%d] dst %S escwalk replace src: %S with %S\n",
  2019						linestr(lineno), e.loopdepth,
  2020						dst, src, srcE.Retval.First())
  2021				}
  2022				src = srcE.Retval.First()
  2023				srcE = e.nodeEscState(src)
  2024			}
  2025		}
  2026	
  2027	recurse:
  2028		level = level.copy()
  2029	
  2030		for i := range srcE.Flowsrc {
  2031			s := &srcE.Flowsrc[i]
  2032			s.parent = step
  2033			e.escwalkBody(level, dst, s.src, s, extraloopdepth)
  2034			s.parent = nil
  2035		}
  2036	
  2037		e.pdepth--
  2038	}
  2039	
  2040	// addrescapes tags node n as having had its address taken
  2041	// by "increasing" the "value" of n.Esc to EscHeap.
  2042	// Storage is allocated as necessary to allow the address
  2043	// to be taken.
  2044	func addrescapes(n *Node) {
  2045		switch n.Op {
  2046		default:
  2047			// Unexpected Op, probably due to a previous type error. Ignore.
  2048	
  2049		case ODEREF, ODOTPTR:
  2050			// Nothing to do.
  2051	
  2052		case ONAME:
  2053			if n == nodfp {
  2054				break
  2055			}
  2056	
  2057			// if this is a tmpname (PAUTO), it was tagged by tmpname as not escaping.
  2058			// on PPARAM it means something different.
  2059			if n.Class() == PAUTO && n.Esc == EscNever {
  2060				break
  2061			}
  2062	
  2063			// If a closure reference escapes, mark the outer variable as escaping.
  2064			if n.IsClosureVar() {
  2065				addrescapes(n.Name.Defn)
  2066				break
  2067			}
  2068	
  2069			if n.Class() != PPARAM && n.Class() != PPARAMOUT && n.Class() != PAUTO {
  2070				break
  2071			}
  2072	
  2073			// This is a plain parameter or local variable that needs to move to the heap,
  2074			// but possibly for the function outside the one we're compiling.
  2075			// That is, if we have:
  2076			//
  2077			//	func f(x int) {
  2078			//		func() {
  2079			//			global = &x
  2080			//		}
  2081			//	}
  2082			//
  2083			// then we're analyzing the inner closure but we need to move x to the
  2084			// heap in f, not in the inner closure. Flip over to f before calling moveToHeap.
  2085			oldfn := Curfn
  2086			Curfn = n.Name.Curfn
  2087			if Curfn.Func.Closure != nil && Curfn.Op == OCLOSURE {
  2088				Curfn = Curfn.Func.Closure
  2089			}
  2090			ln := lineno
  2091			lineno = Curfn.Pos
  2092			moveToHeap(n)
  2093			Curfn = oldfn
  2094			lineno = ln
  2095	
  2096		// ODOTPTR has already been introduced,
  2097		// so these are the non-pointer ODOT and OINDEX.
  2098		// In &x[0], if x is a slice, then x does not
  2099		// escape--the pointer inside x does, but that
  2100		// is always a heap pointer anyway.
  2101		case ODOT, OINDEX, OPAREN, OCONVNOP:
  2102			if !n.Left.Type.IsSlice() {
  2103				addrescapes(n.Left)
  2104			}
  2105		}
  2106	}
  2107	
  2108	// moveToHeap records the parameter or local variable n as moved to the heap.
  2109	func moveToHeap(n *Node) {
  2110		if Debug['r'] != 0 {
  2111			Dump("MOVE", n)
  2112		}
  2113		if compiling_runtime {
  2114			yyerror("%v escapes to heap, not allowed in runtime.", n)
  2115		}
  2116		if n.Class() == PAUTOHEAP {
  2117			Dump("n", n)
  2118			Fatalf("double move to heap")
  2119		}
  2120	
  2121		// Allocate a local stack variable to hold the pointer to the heap copy.
  2122		// temp will add it to the function declaration list automatically.
  2123		heapaddr := temp(types.NewPtr(n.Type))
  2124		heapaddr.Sym = lookup("&" + n.Sym.Name)
  2125		heapaddr.Orig.Sym = heapaddr.Sym
  2126		heapaddr.Pos = n.Pos
  2127	
  2128		// Unset AutoTemp to persist the &foo variable name through SSA to
  2129		// liveness analysis.
  2130		// TODO(mdempsky/drchase): Cleaner solution?
  2131		heapaddr.Name.SetAutoTemp(false)
  2132	
  2133		// Parameters have a local stack copy used at function start/end
  2134		// in addition to the copy in the heap that may live longer than
  2135		// the function.
  2136		if n.Class() == PPARAM || n.Class() == PPARAMOUT {
  2137			if n.Xoffset == BADWIDTH {
  2138				Fatalf("addrescapes before param assignment")
  2139			}
  2140	
  2141			// We rewrite n below to be a heap variable (indirection of heapaddr).
  2142			// Preserve a copy so we can still write code referring to the original,
  2143			// and substitute that copy into the function declaration list
  2144			// so that analyses of the local (on-stack) variables use it.
  2145			stackcopy := newname(n.Sym)
  2146			stackcopy.SetAddable(false)
  2147			stackcopy.Type = n.Type
  2148			stackcopy.Xoffset = n.Xoffset
  2149			stackcopy.SetClass(n.Class())
  2150			stackcopy.Name.Param.Heapaddr = heapaddr
  2151			if n.Class() == PPARAMOUT {
  2152				// Make sure the pointer to the heap copy is kept live throughout the function.
  2153				// The function could panic at any point, and then a defer could recover.
  2154				// Thus, we need the pointer to the heap copy always available so the
  2155				// post-deferreturn code can copy the return value back to the stack.
  2156				// See issue 16095.
  2157				heapaddr.SetIsOutputParamHeapAddr(true)
  2158			}
  2159			n.Name.Param.Stackcopy = stackcopy
  2160	
  2161			// Substitute the stackcopy into the function variable list so that
  2162			// liveness and other analyses use the underlying stack slot
  2163			// and not the now-pseudo-variable n.
  2164			found := false
  2165			for i, d := range Curfn.Func.Dcl {
  2166				if d == n {
  2167					Curfn.Func.Dcl[i] = stackcopy
  2168					found = true
  2169					break
  2170				}
  2171				// Parameters are before locals, so can stop early.
  2172				// This limits the search even in functions with many local variables.
  2173				if d.Class() == PAUTO {
  2174					break
  2175				}
  2176			}
  2177			if !found {
  2178				Fatalf("cannot find %v in local variable list", n)
  2179			}
  2180			Curfn.Func.Dcl = append(Curfn.Func.Dcl, n)
  2181		}
  2182	
  2183		// Modify n in place so that uses of n now mean indirection of the heapaddr.
  2184		n.SetClass(PAUTOHEAP)
  2185		n.Xoffset = 0
  2186		n.Name.Param.Heapaddr = heapaddr
  2187		n.Esc = EscHeap
  2188		if Debug['m'] != 0 {
  2189			fmt.Printf("%v: moved to heap: %v\n", n.Line(), n)
  2190		}
  2191	}
  2192	
  2193	// This special tag is applied to uintptr variables
  2194	// that we believe may hold unsafe.Pointers for
  2195	// calls into assembly functions.
  2196	const unsafeUintptrTag = "unsafe-uintptr"
  2197	
  2198	// This special tag is applied to uintptr parameters of functions
  2199	// marked go:uintptrescapes.
  2200	const uintptrEscapesTag = "uintptr-escapes"
  2201	
  2202	func esctag(fn *Node) {
  2203		fn.Esc = EscFuncTagged
  2204	
  2205		name := func(s *types.Sym, narg int) string {
  2206			if s != nil {
  2207				return s.Name
  2208			}
  2209			return fmt.Sprintf("arg#%d", narg)
  2210		}
  2211	
  2212		// External functions are assumed unsafe,
  2213		// unless //go:noescape is given before the declaration.
  2214		if fn.Nbody.Len() == 0 {
  2215			if fn.Noescape() {
  2216				for _, f := range fn.Type.Params().Fields().Slice() {
  2217					if types.Haspointers(f.Type) {
  2218						f.Note = mktag(EscNone)
  2219					}
  2220				}
  2221			}
  2222	
  2223			// Assume that uintptr arguments must be held live across the call.
  2224			// This is most important for syscall.Syscall.
  2225			// See golang.org/issue/13372.
  2226			// This really doesn't have much to do with escape analysis per se,
  2227			// but we are reusing the ability to annotate an individual function
  2228			// argument and pass those annotations along to importing code.
  2229			narg := 0
  2230			for _, f := range fn.Type.Params().Fields().Slice() {
  2231				narg++
  2232				if f.Type.Etype == TUINTPTR {
  2233					if Debug['m'] != 0 {
  2234						Warnl(fn.Pos, "%v assuming %v is unsafe uintptr", funcSym(fn), name(f.Sym, narg))
  2235					}
  2236					f.Note = unsafeUintptrTag
  2237				}
  2238			}
  2239	
  2240			return
  2241		}
  2242	
  2243		if fn.Func.Pragma&UintptrEscapes != 0 {
  2244			narg := 0
  2245			for _, f := range fn.Type.Params().Fields().Slice() {
  2246				narg++
  2247				if f.Type.Etype == TUINTPTR {
  2248					if Debug['m'] != 0 {
  2249						Warnl(fn.Pos, "%v marking %v as escaping uintptr", funcSym(fn), name(f.Sym, narg))
  2250					}
  2251					f.Note = uintptrEscapesTag
  2252				}
  2253	
  2254				if f.IsDDD() && f.Type.Elem().Etype == TUINTPTR {
  2255					// final argument is ...uintptr.
  2256					if Debug['m'] != 0 {
  2257						Warnl(fn.Pos, "%v marking %v as escaping ...uintptr", funcSym(fn), name(f.Sym, narg))
  2258					}
  2259					f.Note = uintptrEscapesTag
  2260				}
  2261			}
  2262		}
  2263	
  2264		for _, fs := range types.RecvsParams {
  2265			for _, f := range fs(fn.Type).Fields().Slice() {
  2266				if !types.Haspointers(f.Type) { // don't bother tagging for scalars
  2267					continue
  2268				}
  2269				if f.Note == uintptrEscapesTag {
  2270					// Note is already set in the loop above.
  2271					continue
  2272				}
  2273	
  2274				// Unnamed parameters are unused and therefore do not escape.
  2275				if f.Sym == nil || f.Sym.IsBlank() {
  2276					f.Note = mktag(EscNone)
  2277					continue
  2278				}
  2279	
  2280				switch esc := asNode(f.Nname).Esc; esc & EscMask {
  2281				case EscNone, // not touched by escflood
  2282					EscReturn:
  2283					f.Note = mktag(int(esc))
  2284	
  2285				case EscHeap: // touched by escflood, moved to heap
  2286				}
  2287			}
  2288		}
  2289	}
  2290	

View as plain text