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

View as plain text