// Copyright 2018 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package gc import ( "cmd/compile/internal/types" "fmt" ) // Escape analysis. // // Here we analyze functions to determine which Go variables // (including implicit allocations such as calls to "new" or "make", // composite literals, etc.) can be allocated on the stack. The two // key invariants we have to ensure are: (1) pointers to stack objects // cannot be stored in the heap, and (2) pointers to a stack object // cannot outlive that object (e.g., because the declaring function // returned and destroyed the object's stack frame, or its space is // reused across loop iterations for logically distinct variables). // // We implement this with a static data-flow analysis of the AST. // First, we construct a directed weighted graph where vertices // (termed "locations") represent variables allocated by statements // and expressions, and edges represent assignments between variables // (with weights reperesenting addressing/dereference counts). // // Next we walk the graph looking for assignment paths that might // violate the invariants stated above. If a variable v's address is // stored in the heap or elsewhere that may outlive it, then v is // marked as requiring heap allocation. // // To support interprocedural analysis, we also record data-flow from // each function's parameters to the heap and to its result // parameters. This information is summarized as "paremeter tags", // which are used at static call sites to improve escape analysis of // function arguments. // Constructing the location graph. // // Every allocating statement (e.g., variable declaration) or // expression (e.g., "new" or "make") is first mapped to a unique // "location." // // We also model every Go assignment as a directed edges between // locations. The number of derefence operations minus the number of // addressing operations is recorded as the edge's weight (termed // "derefs"). For example: // // p = &q // -1 // p = q // 0 // p = *q // 1 // p = **q // 2 // // p = **&**&q // 2 // // Note that the & operator can only be applied to addressable // expressions, and the expression &x itself is not addressable, so // derefs cannot go below -1. // // Every Go language construct is lowered into this representation, // generally without sensitivity to flow, path, or context; and // without distinguishing elements within a compound variable. For // example: // // var x struct { f, g *int } // var u []*int // // x.f = u[0] // // is modeled simply as // // x = *u // // That is, we don't distinguish x.f from x.g, or u[0] from u[1], // u[2], etc. However, we do record the implicit dereference involved // in indexing a slice. type Escape struct { allLocs []*EscLocation curfn *Node // loopDepth counts the current loop nesting depth within // curfn. It increments within each "for" loop and at each // label with a corresponding backwards "goto" (i.e., // unstructured loop). loopDepth int heapLoc EscLocation blankLoc EscLocation } // An EscLocation represents an abstract location that stores a Go // variable. type EscLocation struct { n *Node // represented variable or expression, if any curfn *Node // enclosing function edges []EscEdge // incoming edges loopDepth int // loopDepth at declaration // derefs and walkgen are used during walk to track the // minimal dereferences from the walk root. derefs int // >= -1 walkgen uint32 // escapes reports whether the represented variable's address // escapes; that is, whether the variable must be heap // allocated. escapes bool // transient reports whether the represented expression's // address does not outlive the statement; that is, whether // its storage can be immediately reused. transient bool // paramEsc records the represented parameter's escape tags. // See "Parameter tags" below for details. paramEsc uint16 } // An EscEdge represents an assignment edge between two Go variables. type EscEdge struct { src *EscLocation derefs int // >= -1 } // escapeFuncs performs escape analysis on a minimal batch of // functions. func escapeFuncs(fns []*Node, recursive bool) { for _, fn := range fns { if fn.Op != ODCLFUNC { Fatalf("unexpected node: %v", fn) } } var e Escape // Construct data-flow graph from syntax trees. for _, fn := range fns { e.initFunc(fn) } for _, fn := range fns { e.walkFunc(fn) } e.curfn = nil e.walkAll() e.finish() // Record parameter tags for package export data. for _, fn := range fns { esctag(fn) } } func (e *Escape) initFunc(fn *Node) { if fn.Op != ODCLFUNC || fn.Esc != EscFuncUnknown { Fatalf("unexpected node: %v", fn) } fn.Esc = EscFuncPlanned if Debug['m'] > 3 { Dump("escAnalyze", fn) } e.curfn = fn e.loopDepth = 1 // Allocate locations for local variables. for _, dcl := range fn.Func.Dcl { if dcl.Op == ONAME { loc := e.newLoc(dcl, false) if dcl.Class() == PPARAM && fn.Nbody.Len() == 0 && !fn.Noescape() { loc.paramEsc = EscHeap } } } } func (e *Escape) walkFunc(fn *Node) { fn.Esc = EscFuncStarted // Identify labels that mark the head of an unstructured loop. inspectList(fn.Nbody, func(n *Node) bool { switch n.Op { case OLABEL: n.Sym.Label = asTypesNode(&nonlooping) case OGOTO: // If we visited the label before the goto, // then this is a looping label. if n.Sym.Label == asTypesNode(&nonlooping) { n.Sym.Label = asTypesNode(&looping) } } return true }) e.curfn = fn e.loopDepth = 1 e.stmts(fn.Nbody) } // Below we implement the methods for walking the AST and recording // data flow edges. Note that because a sub-expression might have // side-effects, it's important to always visit the entire AST. // // For example, write either: // // if x { // e.discard(n.Left) // } else { // e.value(k, n.Left) // } // // or // // if x { // k = e.discardHole() // } // e.value(k, n.Left) // // Do NOT write: // // // BAD: possibly loses side-effects within n.Left // if !x { // e.value(k, n.Left) // } // stmt evaluates a single Go statement. func (e *Escape) stmt(n *Node) { if n == nil { return } lno := setlineno(n) defer func() { lineno = lno }() if Debug['m'] > 2 { fmt.Printf("%v:[%d] %v stmt: %v\n", linestr(lineno), e.loopDepth, funcSym(e.curfn), n) } e.stmts(n.Ninit) switch n.Op { default: Fatalf("unexpected stmt: %v", n) case ODCLCONST, ODCLTYPE, OEMPTY, OFALL, OINLMARK: // nop case OBREAK, OCONTINUE, OGOTO: // TODO(mdempsky): Handle dead code? case OBLOCK: e.stmts(n.List) case ODCL: // Record loop depth at declaration. if !n.Left.isBlank() { e.dcl(n.Left) } case OLABEL: switch asNode(n.Sym.Label) { case &nonlooping: if Debug['m'] > 2 { fmt.Printf("%v:%v non-looping label\n", linestr(lineno), n) } case &looping: if Debug['m'] > 2 { fmt.Printf("%v: %v looping label\n", linestr(lineno), n) } e.loopDepth++ default: Fatalf("label missing tag") } n.Sym.Label = nil case OIF: e.discard(n.Left) e.stmts(n.Nbody) e.stmts(n.Rlist) case OFOR, OFORUNTIL: e.loopDepth++ e.discard(n.Left) e.stmt(n.Right) e.stmts(n.Nbody) e.loopDepth-- case ORANGE: // for List = range Right { Nbody } // Right is evaluated outside the loop. tv := e.newLoc(n, false) e.expr(tv.asHole(), n.Right) e.loopDepth++ ks := e.addrs(n.List) if len(ks) >= 2 { if n.Right.Type.IsArray() { e.flow(ks[1].note(n, "range"), tv) } else { e.flow(ks[1].deref(n, "range-deref"), tv) } } e.stmts(n.Nbody) e.loopDepth-- case OSWITCH: var tv *EscLocation if n.Left != nil { if n.Left.Op == OTYPESW { k := e.discardHole() if n.Left.Left != nil { tv = e.newLoc(n.Left, false) k = tv.asHole() } e.expr(k, n.Left.Right) } else { e.discard(n.Left) } } for _, cas := range n.List.Slice() { // cases if tv != nil { // type switch variables have no ODCL. cv := cas.Rlist.First() k := e.dcl(cv) if types.Haspointers(cv.Type) { e.flow(k.dotType(cv.Type, n, "switch case"), tv) } } e.discards(cas.List) e.stmts(cas.Nbody) } case OSELECT: for _, cas := range n.List.Slice() { e.stmt(cas.Left) e.stmts(cas.Nbody) } case OSELRECV: e.assign(n.Left, n.Right, "selrecv", n) case OSELRECV2: e.assign(n.Left, n.Right, "selrecv", n) e.assign(n.List.First(), nil, "selrecv", n) case ORECV: // TODO(mdempsky): Consider e.discard(n.Left). e.exprSkipInit(e.discardHole(), n) // already visited n.Ninit case OSEND: e.discard(n.Left) e.assignHeap(n.Right, "send", n) case OAS, OASOP: e.assign(n.Left, n.Right, "assign", n) case OAS2: for i, nl := range n.List.Slice() { e.assign(nl, n.Rlist.Index(i), "assign-pair", n) } case OAS2DOTTYPE: // v, ok = x.(type) e.assign(n.List.First(), n.Rlist.First(), "assign-pair-dot-type", n) e.assign(n.List.Second(), nil, "assign-pair-dot-type", n) case OAS2MAPR: // v, ok = m[k] e.assign(n.List.First(), n.Rlist.First(), "assign-pair-mapr", n) e.assign(n.List.Second(), nil, "assign-pair-mapr", n) case OAS2RECV: // v, ok = <-ch e.assign(n.List.First(), n.Rlist.First(), "assign-pair-receive", n) e.assign(n.List.Second(), nil, "assign-pair-receive", n) case OAS2FUNC: e.stmts(n.Rlist.First().Ninit) e.call(e.addrs(n.List), n.Rlist.First(), nil) case ORETURN: results := e.curfn.Type.Results().FieldSlice() for i, v := range n.List.Slice() { e.assign(asNode(results[i].Nname), v, "return", n) } case OCALLFUNC, OCALLMETH, OCALLINTER, OCLOSE, OCOPY, ODELETE, OPANIC, OPRINT, OPRINTN, ORECOVER: e.call(nil, n, nil) case OGO, ODEFER: e.stmts(n.Left.Ninit) e.call(nil, n.Left, n) case ORETJMP: // TODO(mdempsky): What do? esc.go just ignores it. } } func (e *Escape) stmts(l Nodes) { // TODO(mdempsky): Preserve and restore e.loopDepth? See also #22438. for _, n := range l.Slice() { e.stmt(n) } } // expr models evaluating an expression n and flowing the result into // hole k. func (e *Escape) expr(k EscHole, n *Node) { if n == nil { return } e.stmts(n.Ninit) e.exprSkipInit(k, n) } func (e *Escape) exprSkipInit(k EscHole, n *Node) { if n == nil { return } lno := setlineno(n) defer func() { lineno = lno }() if k.derefs >= 0 && !types.Haspointers(n.Type) { k = e.discardHole() } switch n.Op { default: Fatalf("unexpected expr: %v", n) case OLITERAL, OGETG, OCLOSUREVAR, OTYPE: // nop case ONAME: if n.Class() == PFUNC || n.Class() == PEXTERN { return } e.flow(k, e.oldLoc(n)) case OPLUS, ONEG, OBITNOT, ONOT: e.discard(n.Left) case OADD, OSUB, OOR, OXOR, OMUL, ODIV, OMOD, OLSH, ORSH, OAND, OANDNOT, OEQ, ONE, OLT, OLE, OGT, OGE, OANDAND, OOROR: e.discard(n.Left) e.discard(n.Right) case OADDR: e.expr(k.addr(n, "address-of"), n.Left) // "address-of" case ODEREF: e.expr(k.deref(n, "indirection"), n.Left) // "indirection" case ODOT, ODOTMETH, ODOTINTER: e.expr(k.note(n, "dot"), n.Left) case ODOTPTR: e.expr(k.deref(n, "dot of pointer"), n.Left) // "dot of pointer" case ODOTTYPE, ODOTTYPE2: e.expr(k.dotType(n.Type, n, "dot"), n.Left) case OINDEX: if n.Left.Type.IsArray() { e.expr(k.note(n, "fixed-array-index-of"), n.Left) } else { // TODO(mdempsky): Fix why reason text. e.expr(k.deref(n, "dot of pointer"), n.Left) } e.discard(n.Right) case OINDEXMAP: e.discard(n.Left) e.discard(n.Right) case OSLICE, OSLICEARR, OSLICE3, OSLICE3ARR, OSLICESTR: e.expr(k.note(n, "slice"), n.Left) low, high, max := n.SliceBounds() e.discard(low) e.discard(high) e.discard(max) case OCONV, OCONVNOP: if n.Type.Etype == TUNSAFEPTR && n.Left.Type.Etype == TUINTPTR { e.unsafeValue(k, n.Left) } else { e.expr(k, n.Left) } case OCONVIFACE: if !n.Left.Type.IsInterface() && !isdirectiface(n.Left.Type) { k = e.spill(k, n) } else { // esc.go prints "escapes to heap" / "does not // escape" messages for OCONVIFACE even when // they don't allocate. Match that behavior // because it's easy. // TODO(mdempsky): Remove and cleanup test expectations. _ = e.spill(k, n) } e.expr(k.note(n, "interface-converted"), n.Left) case ORECV: e.discard(n.Left) case OCALLMETH, OCALLFUNC, OCALLINTER, OLEN, OCAP, OCOMPLEX, OREAL, OIMAG, OAPPEND, OCOPY: e.call([]EscHole{k}, n, nil) case ONEW: e.spill(k, n) case OMAKESLICE: e.spill(k, n) e.discard(n.Left) e.discard(n.Right) case OMAKECHAN: e.discard(n.Left) case OMAKEMAP: e.spill(k, n) e.discard(n.Left) case ORECOVER: // nop case OCALLPART: e.spill(k, n) // esc.go says "Contents make it to memory, lose // track." I think we can just flow n.Left to our // spilled location though. // TODO(mdempsky): Try that. e.assignHeap(n.Left, "call part", n) case OPTRLIT: e.expr(e.spill(k, n), n.Left) case OARRAYLIT: for _, elt := range n.List.Slice() { if elt.Op == OKEY { elt = elt.Right } e.expr(k.note(n, "array literal element"), elt) } case OSLICELIT: k = e.spill(k, n) for _, elt := range n.List.Slice() { if elt.Op == OKEY { elt = elt.Right } e.expr(k.note(n, "slice-literal-element"), elt) } case OSTRUCTLIT: for _, elt := range n.List.Slice() { e.expr(k.note(n, "struct literal element"), elt.Left) } case OMAPLIT: e.spill(k, n) // Map keys and values are always stored in the heap. for _, elt := range n.List.Slice() { e.assignHeap(elt.Left, "map literal key", n) e.assignHeap(elt.Right, "map literal value", n) } case OCLOSURE: k = e.spill(k, n) // Link addresses of captured variables to closure. for _, v := range n.Func.Closure.Func.Cvars.Slice() { if v.Op == OXXX { // unnamed out argument; see dcl.go:/^funcargs continue } k := k if !v.Name.Byval() { k = k.addr(v, "reference") } e.expr(k.note(n, "captured by a closure"), v.Name.Defn) } case ORUNES2STR, OBYTES2STR, OSTR2RUNES, OSTR2BYTES, ORUNESTR: e.spill(k, n) e.discard(n.Left) case OADDSTR: e.spill(k, n) // Arguments of OADDSTR never escape; // runtime.concatstrings makes sure of that. e.discards(n.List) } } // unsafeValue evaluates a uintptr-typed arithmetic expression looking // for conversions from an unsafe.Pointer. func (e *Escape) unsafeValue(k EscHole, n *Node) { if n.Type.Etype != TUINTPTR { Fatalf("unexpected type %v for %v", n.Type, n) } e.stmts(n.Ninit) switch n.Op { case OCONV, OCONVNOP: if n.Left.Type.Etype == TUNSAFEPTR { e.expr(k, n.Left) } else { e.discard(n.Left) } case ODOTPTR: if isReflectHeaderDataField(n) { e.expr(k.deref(n, "reflect.Header.Data"), n.Left) } else { e.discard(n.Left) } case OPLUS, ONEG, OBITNOT: e.unsafeValue(k, n.Left) case OADD, OSUB, OOR, OXOR, OMUL, ODIV, OMOD, OAND, OANDNOT: e.unsafeValue(k, n.Left) e.unsafeValue(k, n.Right) case OLSH, ORSH: e.unsafeValue(k, n.Left) // RHS need not be uintptr-typed (#32959) and can't meaningfully // flow pointers anyway. e.discard(n.Right) default: e.exprSkipInit(e.discardHole(), n) } } // discard evaluates an expression n for side-effects, but discards // its value. func (e *Escape) discard(n *Node) { e.expr(e.discardHole(), n) } func (e *Escape) discards(l Nodes) { for _, n := range l.Slice() { e.discard(n) } } // addr evaluates an addressable expression n and returns an EscHole // that represents storing into the represented location. func (e *Escape) addr(n *Node) EscHole { if n == nil || n.isBlank() { // Can happen at least in OSELRECV. // TODO(mdempsky): Anywhere else? return e.discardHole() } k := e.heapHole() switch n.Op { default: Fatalf("unexpected addr: %v", n) case ONAME: if n.Class() == PEXTERN { break } k = e.oldLoc(n).asHole() case ODOT: k = e.addr(n.Left) case OINDEX: e.discard(n.Right) if n.Left.Type.IsArray() { k = e.addr(n.Left) } else { e.discard(n.Left) } case ODEREF, ODOTPTR: e.discard(n) case OINDEXMAP: e.discard(n.Left) e.assignHeap(n.Right, "key of map put", n) } if !types.Haspointers(n.Type) { k = e.discardHole() } return k } func (e *Escape) addrs(l Nodes) []EscHole { var ks []EscHole for _, n := range l.Slice() { ks = append(ks, e.addr(n)) } return ks } // assign evaluates the assignment dst = src. func (e *Escape) assign(dst, src *Node, why string, where *Node) { // Filter out some no-op assignments for escape analysis. ignore := dst != nil && src != nil && isSelfAssign(dst, src) if ignore && Debug['m'] != 0 { Warnl(where.Pos, "%v ignoring self-assignment in %S", funcSym(e.curfn), where) } k := e.addr(dst) if dst != nil && dst.Op == ODOTPTR && isReflectHeaderDataField(dst) { e.unsafeValue(e.heapHole(), src) } else { if ignore { k = e.discardHole() } e.expr(k, src) } } func (e *Escape) assignHeap(src *Node, why string, where *Node) { e.expr(e.heapHole().note(where, why), src) } // call evaluates a call expressions, including builtin calls. ks // should contain the holes representing where the function callee's // results flows; where is the OGO/ODEFER context of the call, if any. func (e *Escape) call(ks []EscHole, call, where *Node) { // First, pick out the function callee, its type, and receiver // (if any) and normal arguments list. var fn, recv *Node var fntype *types.Type args := call.List.Slice() switch call.Op { case OCALLFUNC: fn = call.Left if fn.Op == OCLOSURE { fn = fn.Func.Closure.Func.Nname } fntype = fn.Type case OCALLMETH: fn = asNode(call.Left.Type.FuncType().Nname) fntype = fn.Type recv = call.Left.Left case OCALLINTER: fntype = call.Left.Type recv = call.Left.Left case OAPPEND, ODELETE, OPRINT, OPRINTN, ORECOVER: // ok case OLEN, OCAP, OREAL, OIMAG, OCLOSE, OPANIC: args = []*Node{call.Left} case OCOMPLEX, OCOPY: args = []*Node{call.Left, call.Right} default: Fatalf("unexpected call op: %v", call.Op) } static := fn != nil && fn.Op == ONAME && fn.Class() == PFUNC // Setup evaluation holes for each receiver/argument. var recvK EscHole var paramKs []EscHole if static && fn.Name.Defn != nil && fn.Name.Defn.Esc < EscFuncTagged { // Static call to function in same mutually recursive // group; incorporate into data flow graph. if fn.Name.Defn.Esc == EscFuncUnknown { Fatalf("graph inconsistency") } if ks != nil { for i, result := range fntype.Results().FieldSlice() { e.expr(ks[i], asNode(result.Nname)) } } if r := fntype.Recv(); r != nil { recvK = e.addr(asNode(r.Nname)) } for _, param := range fntype.Params().FieldSlice() { paramKs = append(paramKs, e.addr(asNode(param.Nname))) } } else if call.Op == OCALLFUNC || call.Op == OCALLMETH || call.Op == OCALLINTER { // Dynamic call, or call to previously tagged // function. Setup flows to heap and/or ks according // to parameter tags. if r := fntype.Recv(); r != nil { recvK = e.tagHole(ks, r, static) } for _, param := range fntype.Params().FieldSlice() { paramKs = append(paramKs, e.tagHole(ks, param, static)) } } else { // Handle escape analysis for builtins. // By default, we just discard everything. for range args { paramKs = append(paramKs, e.discardHole()) } switch call.Op { case OAPPEND: // Appendee slice may flow directly to the // result, if it has enough capacity. // Alternatively, a new heap slice might be // allocated, and all slice elements might // flow to heap. paramKs[0] = e.teeHole(paramKs[0], ks[0]) if types.Haspointers(args[0].Type.Elem()) { paramKs[0] = e.teeHole(paramKs[0], e.heapHole().deref(call, "appendee slice")) } if call.IsDDD() { if args[1].Type.IsSlice() && types.Haspointers(args[1].Type.Elem()) { paramKs[1] = e.teeHole(paramKs[1], e.heapHole().deref(call, "appended slice...")) } } else { for i := 1; i < len(args); i++ { paramKs[i] = e.heapHole() } } case OCOPY: if call.Right.Type.IsSlice() && types.Haspointers(call.Right.Type.Elem()) { paramKs[1] = e.teeHole(paramKs[1], e.heapHole().deref(call, "copied slice")) } case OPANIC: paramKs[0] = e.heapHole() } } if call.Op == OCALLFUNC { // Evaluate callee function expression. e.expr(e.augmentParamHole(e.discardHole(), where), call.Left) } if recv != nil { // TODO(mdempsky): Handle go:uintptrescapes here too? e.expr(e.augmentParamHole(recvK, where), recv) } // Apply augmentParamHole before ODDDARG so that it affects // the implicit slice allocation for variadic calls, if any. for i, paramK := range paramKs { paramKs[i] = e.augmentParamHole(paramK, where) } // TODO(mdempsky): Remove after early ddd-ification. if fntype != nil && fntype.IsVariadic() && !call.IsDDD() { vi := fntype.NumParams() - 1 elt := fntype.Params().Field(vi).Type.Elem() nva := call.List.Len() nva -= vi // Introduce ODDDARG node to represent ... allocation. ddd := nodl(call.Pos, ODDDARG, nil, nil) ddd.Type = types.NewPtr(types.NewArray(elt, int64(nva))) call.Right = ddd dddK := e.spill(paramKs[vi], ddd) paramKs = paramKs[:vi] for i := 0; i < nva; i++ { paramKs = append(paramKs, dddK) } } for i, arg := range args { // For arguments to go:uintptrescapes, peel // away an unsafe.Pointer->uintptr conversion, // if present. if static && arg.Op == OCONVNOP && arg.Type.Etype == TUINTPTR && arg.Left.Type.Etype == TUNSAFEPTR { x := i if fntype.IsVariadic() && x >= fntype.NumParams() { x = fntype.NumParams() - 1 } if fntype.Params().Field(x).Note == uintptrEscapesTag { arg = arg.Left } } // no augmentParamHole here; handled in loop before ODDDARG e.expr(paramKs[i], arg) } } // augmentParamHole augments parameter holes as necessary for use in // go/defer statements. func (e *Escape) augmentParamHole(k EscHole, where *Node) EscHole { if where == nil { return k } // Top level defers arguments don't escape to heap, but they // do need to last until end of function. Tee with a // non-transient location to avoid arguments from being // transiently allocated. if where.Op == ODEFER && e.loopDepth == 1 { where.Esc = EscNever // force stack allocation of defer record (see ssa.go) // TODO(mdempsky): Eliminate redundant EscLocation allocs. return e.teeHole(k, e.newLoc(nil, false).asHole()) } return e.heapHole() } // tagHole returns a hole for evaluating an argument passed to param. // ks should contain the holes representing where the function // callee's results flows; static indicates whether this is a static // call. func (e *Escape) tagHole(ks []EscHole, param *types.Field, static bool) EscHole { // If this is a dynamic call, we can't rely on param.Note. if !static { return e.heapHole() } esc := parsetag(param.Note) switch esc { case EscHeap, EscUnknown: return e.heapHole() } var tagKs []EscHole if esc&EscContentEscapes != 0 { tagKs = append(tagKs, e.heapHole().shift(1)) } if ks != nil { for i := 0; i < numEscReturns; i++ { if x := getEscReturn(esc, i); x >= 0 { tagKs = append(tagKs, ks[i].shift(x)) } } } return e.teeHole(tagKs...) } // An EscHole represents a context for evaluation a Go // expression. E.g., when evaluating p in "x = **p", we'd have a hole // with dst==x and derefs==2. type EscHole struct { dst *EscLocation derefs int // >= -1 } func (k EscHole) note(where *Node, why string) EscHole { // TODO(mdempsky): Keep a record of where/why for diagnostics. return k } func (k EscHole) shift(delta int) EscHole { k.derefs += delta if k.derefs < -1 { Fatalf("derefs underflow: %v", k.derefs) } return k } func (k EscHole) deref(where *Node, why string) EscHole { return k.shift(1).note(where, why) } func (k EscHole) addr(where *Node, why string) EscHole { return k.shift(-1).note(where, why) } func (k EscHole) dotType(t *types.Type, where *Node, why string) EscHole { if !t.IsInterface() && !isdirectiface(t) { k = k.shift(1) } return k.note(where, why) } // teeHole returns a new hole that flows into each hole of ks, // similar to the Unix tee(1) command. func (e *Escape) teeHole(ks ...EscHole) EscHole { if len(ks) == 0 { return e.discardHole() } if len(ks) == 1 { return ks[0] } // TODO(mdempsky): Optimize if there's only one non-discard hole? // Given holes "l1 = _", "l2 = **_", "l3 = *_", ..., create a // new temporary location ltmp, wire it into place, and return // a hole for "ltmp = _". loc := e.newLoc(nil, true) for _, k := range ks { // N.B., "p = &q" and "p = &tmp; tmp = q" are not // semantically equivalent. To combine holes like "l1 // = _" and "l2 = &_", we'd need to wire them as "l1 = // *ltmp" and "l2 = ltmp" and return "ltmp = &_" // instead. if k.derefs < 0 { Fatalf("teeHole: negative derefs") } e.flow(k, loc) } return loc.asHole() } func (e *Escape) dcl(n *Node) EscHole { loc := e.oldLoc(n) loc.loopDepth = e.loopDepth return loc.asHole() } func (e *Escape) spill(k EscHole, n *Node) EscHole { // TODO(mdempsky): Optimize. E.g., if k is the heap or blank, // then we already know whether n leaks, and we can return a // more optimized hole. loc := e.newLoc(n, true) e.flow(k.addr(n, "spill"), loc) return loc.asHole() } // canonicalNode returns the canonical *Node that n logically // represents. func canonicalNode(n *Node) *Node { if n != nil && n.IsClosureVar() { n = n.Name.Defn if n.IsClosureVar() { Fatalf("still closure var") } } return n } func (e *Escape) newLoc(n *Node, transient bool) *EscLocation { if e.curfn == nil { Fatalf("e.curfn isn't set") } n = canonicalNode(n) loc := &EscLocation{ n: n, curfn: e.curfn, loopDepth: e.loopDepth, transient: transient, } e.allLocs = append(e.allLocs, loc) if n != nil { if n.Op == ONAME && n.Name.Curfn != e.curfn { Fatalf("curfn mismatch: %v != %v", n.Name.Curfn, e.curfn) } if n.HasOpt() { Fatalf("%v already has a location", n) } n.SetOpt(loc) // TODO(mdempsky): Perhaps set n.Esc and then just return &HeapLoc? if mustHeapAlloc(n) && !loc.isName(PPARAM) && !loc.isName(PPARAMOUT) { e.flow(e.heapHole().addr(nil, ""), loc) } } return loc } func (e *Escape) oldLoc(n *Node) *EscLocation { n = canonicalNode(n) return n.Opt().(*EscLocation) } func (l *EscLocation) asHole() EscHole { return EscHole{dst: l} } func (e *Escape) flow(k EscHole, src *EscLocation) { dst := k.dst if dst == &e.blankLoc { return } if dst == src && k.derefs >= 0 { return } // TODO(mdempsky): More optimizations? // TODO(mdempsky): Deduplicate edges? dst.edges = append(dst.edges, EscEdge{src: src, derefs: k.derefs}) } func (e *Escape) heapHole() EscHole { return e.heapLoc.asHole() } func (e *Escape) discardHole() EscHole { return e.blankLoc.asHole() } // walkAll computes the minimal dereferences between all pairs of // locations. func (e *Escape) walkAll() { var walkgen uint32 for _, loc := range e.allLocs { walkgen++ e.walkOne(loc, walkgen) } // Walk the heap last so that we catch any edges to the heap // added during walkOne. walkgen++ e.walkOne(&e.heapLoc, walkgen) } // walkOne computes the minimal number of dereferences from root to // all other locations. func (e *Escape) walkOne(root *EscLocation, walkgen uint32) { // The data flow graph has negative edges (from addressing // operations), so we use the Bellman-Ford algorithm. However, // we don't have to worry about infinite negative cycles since // we bound intermediate dereference counts to 0. root.walkgen = walkgen root.derefs = 0 todo := []*EscLocation{root} for len(todo) > 0 { l := todo[len(todo)-1] todo = todo[:len(todo)-1] base := l.derefs // If l.derefs < 0, then l's address flows to root. addressOf := base < 0 if addressOf { // For a flow path like "root = &l; l = x", // l's address flows to root, but x's does // not. We recognize this by lower bounding // base at 0. base = 0 // If l's address flows to a non-transient // location, then l can't be transiently // allocated. if !root.transient { l.transient = false // TODO(mdempsky): Should we re-walk from l now? } } if e.outlives(root, l) { // If l's address flows somewhere that // outlives it, then l needs to be heap // allocated. if addressOf && !l.escapes { l.escapes = true // If l is heap allocated, then any // values stored into it flow to the // heap too. // TODO(mdempsky): Better way to handle this? if root != &e.heapLoc { e.flow(e.heapHole(), l) } } // l's value flows to root. If l is a function // parameter and root is the heap or a // corresponding result parameter, then record // that value flow for tagging the function // later. if l.isName(PPARAM) { l.leakTo(root, base) } } for _, edge := range l.edges { derefs := base + edge.derefs if edge.src.walkgen != walkgen || edge.src.derefs > derefs { edge.src.walkgen = walkgen edge.src.derefs = derefs todo = append(todo, edge.src) } } } } // outlives reports whether values stored in l may survive beyond // other's lifetime if stack allocated. func (e *Escape) outlives(l, other *EscLocation) bool { // The heap outlives everything. if l == &e.heapLoc { return true } // We don't know what callers do with returned values, so // pessimistically we need to assume they flow to the heap and // outlive everything too. if l.isName(PPARAMOUT) { // Exception: Directly called closures can return // locations allocated outside of them without forcing // them to the heap. For example: // // var u int // okay to stack allocate // *(func() *int { return &u }()) = 42 if containsClosure(other.curfn, l.curfn) && l.curfn.Func.Closure.Func.Top&ctxCallee != 0 { return false } return true } // If l and other are within the same function, then l // outlives other if it was declared outside other's loop // scope. For example: // // var l *int // for { // l = new(int) // } if l.curfn == other.curfn && l.loopDepth < other.loopDepth { return true } // If other is declared within a child closure of where l is // declared, then l outlives it. For example: // // var l *int // func() { // l = new(int) // } if containsClosure(l.curfn, other.curfn) { return true } return false } // containsClosure reports whether c is a closure contained within f. func containsClosure(f, c *Node) bool { if f.Op != ODCLFUNC || c.Op != ODCLFUNC { Fatalf("bad containsClosure: %v, %v", f, c) } // Common case. if f == c { return false } // Closures within function Foo are named like "Foo.funcN..." // TODO(mdempsky): Better way to recognize this. fn := f.Func.Nname.Sym.Name cn := c.Func.Nname.Sym.Name return len(cn) > len(fn) && cn[:len(fn)] == fn && cn[len(fn)] == '.' } // leak records that parameter l leaks to sink. func (l *EscLocation) leakTo(sink *EscLocation, derefs int) { // Short circuit if l already leaks to heap. if l.paramEsc == EscHeap { return } // If sink is a result parameter and we can fit return bits // into the escape analysis tag, then record a return leak. if sink.isName(PPARAMOUT) && sink.curfn == l.curfn { // TODO(mdempsky): Eliminate dependency on Vargen here. ri := int(sink.n.Name.Vargen) - 1 if ri < numEscReturns { // Leak to result parameter. if old := getEscReturn(l.paramEsc, ri); old < 0 || derefs < old { l.paramEsc = setEscReturn(l.paramEsc, ri, derefs) } return } } // Otherwise, record as heap leak. if derefs > 0 { l.paramEsc |= EscContentEscapes } else { l.paramEsc = EscHeap } } func (e *Escape) finish() { for _, loc := range e.allLocs { n := loc.n if n == nil { continue } n.SetOpt(nil) // Update n.Esc based on escape analysis results. // // TODO(mdempsky): Simplify once compatibility with // esc.go is no longer necessary. // // TODO(mdempsky): Describe path when Debug['m'] >= 2. if loc.escapes { if Debug['m'] != 0 && n.Op != ONAME { Warnl(n.Pos, "%S escapes to heap", n) } n.Esc = EscHeap addrescapes(n) } else if loc.isName(PPARAM) { n.Esc = finalizeEsc(loc.paramEsc) if Debug['m'] != 0 && types.Haspointers(n.Type) { if n.Esc == EscNone { Warnl(n.Pos, "%S %S does not escape", funcSym(loc.curfn), n) } else if n.Esc == EscHeap { Warnl(n.Pos, "leaking param: %S", n) } else { if n.Esc&EscContentEscapes != 0 { Warnl(n.Pos, "leaking param content: %S", n) } for i := 0; i < numEscReturns; i++ { if x := getEscReturn(n.Esc, i); x >= 0 { res := n.Name.Curfn.Type.Results().Field(i).Sym Warnl(n.Pos, "leaking param: %S to result %v level=%d", n, res, x) } } } } } else { n.Esc = EscNone if loc.transient { switch n.Op { case OCALLPART, OCLOSURE, ODDDARG, OARRAYLIT, OSLICELIT, OPTRLIT, OSTRUCTLIT: n.SetNoescape(true) } } if Debug['m'] != 0 && n.Op != ONAME && n.Op != OTYPESW && n.Op != ORANGE && n.Op != ODEFER { Warnl(n.Pos, "%S %S does not escape", funcSym(loc.curfn), n) } } } } func (l *EscLocation) isName(c Class) bool { return l.n != nil && l.n.Op == ONAME && l.n.Class() == c } func finalizeEsc(esc uint16) uint16 { esc = optimizeReturns(esc) if esc>>EscReturnBits != 0 { esc |= EscReturn } else if esc&EscMask == 0 { esc |= EscNone } return esc } func optimizeReturns(esc uint16) uint16 { if esc&EscContentEscapes != 0 { // EscContentEscapes represents a path of length 1 // from the heap. No point in keeping paths of equal // or longer length to result parameters. for i := 0; i < numEscReturns; i++ { if x := getEscReturn(esc, i); x >= 1 { esc = setEscReturn(esc, i, -1) } } } return esc } // Parameter tags. // // The escape bits saved for each analyzed parameter record the // minimal derefs (if any) from that parameter to the heap, or to any // of its function's (first numEscReturns) result parameters. // // Paths to the heap are encoded via EscHeap (length 0) or // EscContentEscapes (length 1); if neither of these are set, then // there's no path to the heap. // // Paths to the result parameters are encoded in the upper // bits. // // There are other values stored in the escape bits by esc.go for // vestigial reasons, and other special tag values used (e.g., // uintptrEscapesTag and unsafeUintptrTag). These could be simplified // once compatibility with esc.go is no longer a concern. const numEscReturns = (16 - EscReturnBits) / bitsPerOutputInTag func getEscReturn(esc uint16, i int) int { return int((esc>>escReturnShift(i))&bitsMaskForTag) - 1 } func setEscReturn(esc uint16, i, v int) uint16 { if v < -1 { Fatalf("invalid esc return value: %v", v) } if v > maxEncodedLevel { v = maxEncodedLevel } shift := escReturnShift(i) esc &^= bitsMaskForTag << shift esc |= uint16(v+1) << shift return esc } func escReturnShift(i int) uint { if uint(i) >= numEscReturns { Fatalf("esc return index out of bounds: %v", i) } return uint(EscReturnBits + i*bitsPerOutputInTag) }