escape.go

     1  // Copyright 2018 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 escape
     6  
     7  import (
     8  	"fmt"
     9  
    10  	"cmd/compile/internal/base"
    11  	"cmd/compile/internal/ir"
    12  	"cmd/compile/internal/logopt"
    13  	"cmd/compile/internal/typecheck"
    14  	"cmd/compile/internal/types"
    15  	"cmd/internal/src"
    16  )
    17  
    18  // Escape analysis.
    19  //
    20  // Here we analyze functions to determine which Go variables
    21  // (including implicit allocations such as calls to "new" or "make",
    22  // composite literals, etc.) can be allocated on the stack. The two
    23  // key invariants we have to ensure are: (1) pointers to stack objects
    24  // cannot be stored in the heap, and (2) pointers to a stack object
    25  // cannot outlive that object (e.g., because the declaring function
    26  // returned and destroyed the object's stack frame, or its space is
    27  // reused across loop iterations for logically distinct variables).
    28  //
    29  // We implement this with a static data-flow analysis of the AST.
    30  // First, we construct a directed weighted graph where vertices
    31  // (termed "locations") represent variables allocated by statements
    32  // and expressions, and edges represent assignments between variables
    33  // (with weights representing addressing/dereference counts).
    34  //
    35  // Next we walk the graph looking for assignment paths that might
    36  // violate the invariants stated above. If a variable v's address is
    37  // stored in the heap or elsewhere that may outlive it, then v is
    38  // marked as requiring heap allocation.
    39  //
    40  // To support interprocedural analysis, we also record data-flow from
    41  // each function's parameters to the heap and to its result
    42  // parameters. This information is summarized as "parameter tags",
    43  // which are used at static call sites to improve escape analysis of
    44  // function arguments.
    45  
    46  // Constructing the location graph.
    47  //
    48  // Every allocating statement (e.g., variable declaration) or
    49  // expression (e.g., "new" or "make") is first mapped to a unique
    50  // "location."
    51  //
    52  // We also model every Go assignment as a directed edges between
    53  // locations. The number of dereference operations minus the number of
    54  // addressing operations is recorded as the edge's weight (termed
    55  // "derefs"). For example:
    56  //
    57  //     p = &q    // -1
    58  //     p = q     //  0
    59  //     p = *q    //  1
    60  //     p = **q   //  2
    61  //
    62  //     p = **&**&q  // 2
    63  //
    64  // Note that the & operator can only be applied to addressable
    65  // expressions, and the expression &x itself is not addressable, so
    66  // derefs cannot go below -1.
    67  //
    68  // Every Go language construct is lowered into this representation,
    69  // generally without sensitivity to flow, path, or context; and
    70  // without distinguishing elements within a compound variable. For
    71  // example:
    72  //
    73  //     var x struct { f, g *int }
    74  //     var u []*int
    75  //
    76  //     x.f = u[0]
    77  //
    78  // is modeled simply as
    79  //
    80  //     x = *u
    81  //
    82  // That is, we don't distinguish x.f from x.g, or u[0] from u[1],
    83  // u[2], etc. However, we do record the implicit dereference involved
    84  // in indexing a slice.
    85  
    86  // A batch holds escape analysis state that's shared across an entire
    87  // batch of functions being analyzed at once.
    88  type batch struct {
    89  	allLocs  []*location
    90  	closures []closure
    91  
    92  	heapLoc    location
    93  	mutatorLoc location
    94  	calleeLoc  location
    95  	blankLoc   location
    96  }
    97  
    98  // A closure holds a closure expression and its spill hole (i.e.,
    99  // where the hole representing storing into its closure record).
   100  type closure struct {
   101  	k   hole
   102  	clo *ir.ClosureExpr
   103  }
   104  
   105  // An escape holds state specific to a single function being analyzed
   106  // within a batch.
   107  type escape struct {
   108  	*batch
   109  
   110  	curfn *ir.Func // function being analyzed
   111  
   112  	labels map[*types.Sym]labelState // known labels
   113  
   114  	// loopDepth counts the current loop nesting depth within
   115  	// curfn. It increments within each "for" loop and at each
   116  	// label with a corresponding backwards "goto" (i.e.,
   117  	// unstructured loop).
   118  	loopDepth int
   119  }
   120  
   121  func Funcs(all []*ir.Func) {
   122  	ir.VisitFuncsBottomUp(all, Batch)
   123  }
   124  
   125  // Batch performs escape analysis on a minimal batch of
   126  // functions.
   127  func Batch(fns []*ir.Func, recursive bool) {
   128  	var b batch
   129  	b.heapLoc.attrs = attrEscapes | attrPersists | attrMutates | attrCalls
   130  	b.mutatorLoc.attrs = attrMutates
   131  	b.calleeLoc.attrs = attrCalls
   132  
   133  	// Construct data-flow graph from syntax trees.
   134  	for _, fn := range fns {
   135  		if base.Flag.W > 1 {
   136  			s := fmt.Sprintf("\nbefore escape %v", fn)
   137  			ir.Dump(s, fn)
   138  		}
   139  		b.initFunc(fn)
   140  	}
   141  	for _, fn := range fns {
   142  		if !fn.IsHiddenClosure() {
   143  			b.walkFunc(fn)
   144  		}
   145  	}
   146  
   147  	// We've walked the function bodies, so we've seen everywhere a
   148  	// variable might be reassigned or have it's address taken. Now we
   149  	// can decide whether closures should capture their free variables
   150  	// by value or reference.
   151  	for _, closure := range b.closures {
   152  		b.flowClosure(closure.k, closure.clo)
   153  	}
   154  	b.closures = nil
   155  
   156  	for _, loc := range b.allLocs {
   157  		if why := HeapAllocReason(loc.n); why != "" {
   158  			b.flow(b.heapHole().addr(loc.n, why), loc)
   159  		}
   160  	}
   161  
   162  	b.walkAll()
   163  	b.finish(fns)
   164  }
   165  
   166  func (b *batch) with(fn *ir.Func) *escape {
   167  	return &escape{
   168  		batch:     b,
   169  		curfn:     fn,
   170  		loopDepth: 1,
   171  	}
   172  }
   173  
   174  func (b *batch) initFunc(fn *ir.Func) {
   175  	e := b.with(fn)
   176  	if fn.Esc() != escFuncUnknown {
   177  		base.Fatalf("unexpected node: %v", fn)
   178  	}
   179  	fn.SetEsc(escFuncPlanned)
   180  	if base.Flag.LowerM > 3 {
   181  		ir.Dump("escAnalyze", fn)
   182  	}
   183  
   184  	// Allocate locations for local variables.
   185  	for _, n := range fn.Dcl {
   186  		e.newLoc(n, true)
   187  	}
   188  
   189  	// Also for hidden parameters (e.g., the ".this" parameter to a
   190  	// method value wrapper).
   191  	if fn.OClosure == nil {
   192  		for _, n := range fn.ClosureVars {
   193  			e.newLoc(n.Canonical(), true)
   194  		}
   195  	}
   196  
   197  	// Initialize resultIndex for result parameters.
   198  	for i, f := range fn.Type().Results() {
   199  		e.oldLoc(f.Nname.(*ir.Name)).resultIndex = 1 + i
   200  	}
   201  }
   202  
   203  func (b *batch) walkFunc(fn *ir.Func) {
   204  	e := b.with(fn)
   205  	fn.SetEsc(escFuncStarted)
   206  
   207  	// Identify labels that mark the head of an unstructured loop.
   208  	ir.Visit(fn, func(n ir.Node) {
   209  		switch n.Op() {
   210  		case ir.OLABEL:
   211  			n := n.(*ir.LabelStmt)
   212  			if n.Label.IsBlank() {
   213  				break
   214  			}
   215  			if e.labels == nil {
   216  				e.labels = make(map[*types.Sym]labelState)
   217  			}
   218  			e.labels[n.Label] = nonlooping
   219  
   220  		case ir.OGOTO:
   221  			// If we visited the label before the goto,
   222  			// then this is a looping label.
   223  			n := n.(*ir.BranchStmt)
   224  			if e.labels[n.Label] == nonlooping {
   225  				e.labels[n.Label] = looping
   226  			}
   227  		}
   228  	})
   229  
   230  	e.block(fn.Body)
   231  
   232  	if len(e.labels) != 0 {
   233  		base.FatalfAt(fn.Pos(), "leftover labels after walkFunc")
   234  	}
   235  }
   236  
   237  func (b *batch) flowClosure(k hole, clo *ir.ClosureExpr) {
   238  	for _, cv := range clo.Func.ClosureVars {
   239  		n := cv.Canonical()
   240  		loc := b.oldLoc(cv)
   241  		if !loc.captured {
   242  			base.FatalfAt(cv.Pos(), "closure variable never captured: %v", cv)
   243  		}
   244  
   245  		// Capture by value for variables <= 128 bytes that are never reassigned.
   246  		n.SetByval(!loc.addrtaken && !loc.reassigned && n.Type().Size() <= 128)
   247  		if !n.Byval() {
   248  			n.SetAddrtaken(true)
   249  			if n.Sym().Name == typecheck.LocalDictName {
   250  				base.FatalfAt(n.Pos(), "dictionary variable not captured by value")
   251  			}
   252  		}
   253  
   254  		if base.Flag.LowerM > 1 {
   255  			how := "ref"
   256  			if n.Byval() {
   257  				how = "value"
   258  			}
   259  			base.WarnfAt(n.Pos(), "%v capturing by %s: %v (addr=%v assign=%v width=%d)", n.Curfn, how, n, loc.addrtaken, loc.reassigned, n.Type().Size())
   260  		}
   261  
   262  		// Flow captured variables to closure.
   263  		k := k
   264  		if !cv.Byval() {
   265  			k = k.addr(cv, "reference")
   266  		}
   267  		b.flow(k.note(cv, "captured by a closure"), loc)
   268  	}
   269  }
   270  
   271  func (b *batch) finish(fns []*ir.Func) {
   272  	// Record parameter tags for package export data.
   273  	for _, fn := range fns {
   274  		fn.SetEsc(escFuncTagged)
   275  
   276  		for i, param := range fn.Type().RecvParams() {
   277  			param.Note = b.paramTag(fn, 1+i, param)
   278  		}
   279  	}
   280  
   281  	for _, loc := range b.allLocs {
   282  		n := loc.n
   283  		if n == nil {
   284  			continue
   285  		}
   286  
   287  		if n.Op() == ir.ONAME {
   288  			n := n.(*ir.Name)
   289  			n.Opt = nil
   290  		}
   291  
   292  		// Update n.Esc based on escape analysis results.
   293  
   294  		// Omit escape diagnostics for go/defer wrappers, at least for now.
   295  		// Historically, we haven't printed them, and test cases don't expect them.
   296  		// TODO(mdempsky): Update tests to expect this.
   297  		goDeferWrapper := n.Op() == ir.OCLOSURE && n.(*ir.ClosureExpr).Func.Wrapper()
   298  
   299  		if loc.hasAttr(attrEscapes) {
   300  			if n.Op() == ir.ONAME {
   301  				if base.Flag.CompilingRuntime {
   302  					base.ErrorfAt(n.Pos(), 0, "%v escapes to heap, not allowed in runtime", n)
   303  				}
   304  				if base.Flag.LowerM != 0 {
   305  					base.WarnfAt(n.Pos(), "moved to heap: %v", n)
   306  				}
   307  			} else {
   308  				if base.Flag.LowerM != 0 && !goDeferWrapper {
   309  					base.WarnfAt(n.Pos(), "%v escapes to heap", n)
   310  				}
   311  				if logopt.Enabled() {
   312  					var e_curfn *ir.Func // TODO(mdempsky): Fix.
   313  					logopt.LogOpt(n.Pos(), "escape", "escape", ir.FuncName(e_curfn))
   314  				}
   315  			}
   316  			n.SetEsc(ir.EscHeap)
   317  		} else {
   318  			if base.Flag.LowerM != 0 && n.Op() != ir.ONAME && !goDeferWrapper {
   319  				base.WarnfAt(n.Pos(), "%v does not escape", n)
   320  			}
   321  			n.SetEsc(ir.EscNone)
   322  			if !loc.hasAttr(attrPersists) {
   323  				switch n.Op() {
   324  				case ir.OCLOSURE:
   325  					n := n.(*ir.ClosureExpr)
   326  					n.SetTransient(true)
   327  				case ir.OMETHVALUE:
   328  					n := n.(*ir.SelectorExpr)
   329  					n.SetTransient(true)
   330  				case ir.OSLICELIT:
   331  					n := n.(*ir.CompLitExpr)
   332  					n.SetTransient(true)
   333  				}
   334  			}
   335  		}
   336  
   337  		// If the result of a string->[]byte conversion is never mutated,
   338  		// then it can simply reuse the string's memory directly.
   339  		if base.Debug.ZeroCopy != 0 {
   340  			if n, ok := n.(*ir.ConvExpr); ok && n.Op() == ir.OSTR2BYTES && !loc.hasAttr(attrMutates) {
   341  				if base.Flag.LowerM >= 1 {
   342  					base.WarnfAt(n.Pos(), "zero-copy string->[]byte conversion")
   343  				}
   344  				n.SetOp(ir.OSTR2BYTESTMP)
   345  			}
   346  		}
   347  	}
   348  }
   349  
   350  // inMutualBatch reports whether function fn is in the batch of
   351  // mutually recursive functions being analyzed. When this is true,
   352  // fn has not yet been analyzed, so its parameters and results
   353  // should be incorporated directly into the flow graph instead of
   354  // relying on its escape analysis tagging.
   355  func (b *batch) inMutualBatch(fn *ir.Name) bool {
   356  	if fn.Defn != nil && fn.Defn.Esc() < escFuncTagged {
   357  		if fn.Defn.Esc() == escFuncUnknown {
   358  			base.FatalfAt(fn.Pos(), "graph inconsistency: %v", fn)
   359  		}
   360  		return true
   361  	}
   362  	return false
   363  }
   364  
   365  const (
   366  	escFuncUnknown = 0 + iota
   367  	escFuncPlanned
   368  	escFuncStarted
   369  	escFuncTagged
   370  )
   371  
   372  // Mark labels that have no backjumps to them as not increasing e.loopdepth.
   373  type labelState int
   374  
   375  const (
   376  	looping labelState = 1 + iota
   377  	nonlooping
   378  )
   379  
   380  func (b *batch) paramTag(fn *ir.Func, narg int, f *types.Field) string {
   381  	name := func() string {
   382  		if f.Nname != nil {
   383  			return f.Nname.Sym().Name
   384  		}
   385  		return fmt.Sprintf("arg#%d", narg)
   386  	}
   387  
   388  	// Only report diagnostics for user code;
   389  	// not for wrappers generated around them.
   390  	// TODO(mdempsky): Generalize this.
   391  	diagnose := base.Flag.LowerM != 0 && !(fn.Wrapper() || fn.Dupok())
   392  
   393  	if len(fn.Body) == 0 {
   394  		// Assume that uintptr arguments must be held live across the call.
   395  		// This is most important for syscall.Syscall.
   396  		// See golang.org/issue/13372.
   397  		// This really doesn't have much to do with escape analysis per se,
   398  		// but we are reusing the ability to annotate an individual function
   399  		// argument and pass those annotations along to importing code.
   400  		fn.Pragma |= ir.UintptrKeepAlive
   401  
   402  		if f.Type.IsUintptr() {
   403  			if diagnose {
   404  				base.WarnfAt(f.Pos, "assuming %v is unsafe uintptr", name())
   405  			}
   406  			return ""
   407  		}
   408  
   409  		if !f.Type.HasPointers() { // don't bother tagging for scalars
   410  			return ""
   411  		}
   412  
   413  		var esc leaks
   414  
   415  		// External functions are assumed unsafe, unless
   416  		// //go:noescape is given before the declaration.
   417  		if fn.Pragma&ir.Noescape != 0 {
   418  			if diagnose && f.Sym != nil {
   419  				base.WarnfAt(f.Pos, "%v does not escape", name())
   420  			}
   421  			esc.AddMutator(0)
   422  			esc.AddCallee(0)
   423  		} else {
   424  			if diagnose && f.Sym != nil {
   425  				base.WarnfAt(f.Pos, "leaking param: %v", name())
   426  			}
   427  			esc.AddHeap(0)
   428  		}
   429  
   430  		return esc.Encode()
   431  	}
   432  
   433  	if fn.Pragma&ir.UintptrEscapes != 0 {
   434  		if f.Type.IsUintptr() {
   435  			if diagnose {
   436  				base.WarnfAt(f.Pos, "marking %v as escaping uintptr", name())
   437  			}
   438  			return ""
   439  		}
   440  		if f.IsDDD() && f.Type.Elem().IsUintptr() {
   441  			// final argument is ...uintptr.
   442  			if diagnose {
   443  				base.WarnfAt(f.Pos, "marking %v as escaping ...uintptr", name())
   444  			}
   445  			return ""
   446  		}
   447  	}
   448  
   449  	if !f.Type.HasPointers() { // don't bother tagging for scalars
   450  		return ""
   451  	}
   452  
   453  	// Unnamed parameters are unused and therefore do not escape.
   454  	if f.Sym == nil || f.Sym.IsBlank() {
   455  		var esc leaks
   456  		return esc.Encode()
   457  	}
   458  
   459  	n := f.Nname.(*ir.Name)
   460  	loc := b.oldLoc(n)
   461  	esc := loc.paramEsc
   462  	esc.Optimize()
   463  
   464  	if diagnose && !loc.hasAttr(attrEscapes) {
   465  		b.reportLeaks(f.Pos, name(), esc, fn.Type())
   466  	}
   467  
   468  	return esc.Encode()
   469  }
   470  
   471  func (b *batch) reportLeaks(pos src.XPos, name string, esc leaks, sig *types.Type) {
   472  	warned := false
   473  	if x := esc.Heap(); x >= 0 {
   474  		if x == 0 {
   475  			base.WarnfAt(pos, "leaking param: %v", name)
   476  		} else {
   477  			// TODO(mdempsky): Mention level=x like below?
   478  			base.WarnfAt(pos, "leaking param content: %v", name)
   479  		}
   480  		warned = true
   481  	}
   482  	for i := 0; i < numEscResults; i++ {
   483  		if x := esc.Result(i); x >= 0 {
   484  			res := sig.Result(i).Nname.Sym().Name
   485  			base.WarnfAt(pos, "leaking param: %v to result %v level=%d", name, res, x)
   486  			warned = true
   487  		}
   488  	}
   489  
   490  	if base.Debug.EscapeMutationsCalls <= 0 {
   491  		if !warned {
   492  			base.WarnfAt(pos, "%v does not escape", name)
   493  		}
   494  		return
   495  	}
   496  
   497  	if x := esc.Mutator(); x >= 0 {
   498  		base.WarnfAt(pos, "mutates param: %v derefs=%v", name, x)
   499  		warned = true
   500  	}
   501  	if x := esc.Callee(); x >= 0 {
   502  		base.WarnfAt(pos, "calls param: %v derefs=%v", name, x)
   503  		warned = true
   504  	}
   505  
   506  	if !warned {
   507  		base.WarnfAt(pos, "%v does not escape, mutate, or call", name)
   508  	}
   509  }
   510
View as plain text