| // Copyright 2011 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/internal/obj" |
| "fmt" |
| "strings" |
| ) |
| |
| // Escape analysis. |
| |
| // Run analysis on minimal sets of mutually recursive functions |
| // or single non-recursive functions, bottom up. |
| // |
| // Finding these sets is finding strongly connected components |
| // in the static call graph. The algorithm for doing that is taken |
| // from Sedgewick, Algorithms, Second Edition, p. 482, with two |
| // adaptations. |
| // |
| // First, a hidden closure function (n->curfn != N) cannot be the |
| // root of a connected component. Refusing to use it as a root |
| // forces it into the component of the function in which it appears. |
| // The analysis assumes that closures and the functions in which they |
| // appear are analyzed together, so that the aliasing between their |
| // variables can be modeled more precisely. |
| // |
| // Second, each function becomes two virtual nodes in the graph, |
| // with numbers n and n+1. We record the function's node number as n |
| // but search from node n+1. If the search tells us that the component |
| // number (min) is n+1, we know that this is a trivial component: one function |
| // plus its closures. If the search tells us that the component number is |
| // n, then there was a path from node n+1 back to node n, meaning that |
| // the function set is mutually recursive. The escape analysis can be |
| // more precise when analyzing a single non-recursive function than |
| // when analyzing a set of mutually recursive functions. |
| |
| var stack *NodeList |
| |
| var visitgen uint32 |
| |
| const ( |
| EscFuncUnknown = 0 + iota |
| EscFuncPlanned |
| EscFuncStarted |
| EscFuncTagged |
| ) |
| |
| func escapes(all *NodeList) { |
| var l *NodeList |
| |
| for l = all; l != nil; l = l.Next { |
| l.N.Walkgen = 0 |
| } |
| |
| visitgen = 0 |
| for l = all; l != nil; l = l.Next { |
| if l.N.Op == ODCLFUNC && l.N.Curfn == nil { |
| visit(l.N) |
| } |
| } |
| |
| for l = all; l != nil; l = l.Next { |
| l.N.Walkgen = 0 |
| } |
| } |
| |
| func visit(n *Node) uint32 { |
| var min uint32 |
| var recursive bool |
| var l *NodeList |
| var block *NodeList |
| |
| if n.Walkgen > 0 { |
| // already visited |
| return n.Walkgen |
| } |
| |
| visitgen++ |
| n.Walkgen = visitgen |
| visitgen++ |
| min = visitgen |
| |
| l = new(NodeList) |
| l.Next = stack |
| l.N = n |
| stack = l |
| min = visitcodelist(n.Nbody, min) |
| if (min == n.Walkgen || min == n.Walkgen+1) && n.Curfn == nil { |
| // This node is the root of a strongly connected component. |
| |
| // The original min passed to visitcodelist was n->walkgen+1. |
| // If visitcodelist found its way back to n->walkgen, then this |
| // block is a set of mutually recursive functions. |
| // Otherwise it's just a lone function that does not recurse. |
| recursive = min == n.Walkgen |
| |
| // Remove connected component from stack. |
| // Mark walkgen so that future visits return a large number |
| // so as not to affect the caller's min. |
| block = stack |
| |
| for l = stack; l.N != n; l = l.Next { |
| l.N.Walkgen = ^uint32(0) |
| } |
| n.Walkgen = ^uint32(0) |
| stack = l.Next |
| l.Next = nil |
| |
| // Run escape analysis on this set of functions. |
| analyze(block, recursive) |
| } |
| |
| return min |
| } |
| |
| func visitcodelist(l *NodeList, min uint32) uint32 { |
| for ; l != nil; l = l.Next { |
| min = visitcode(l.N, min) |
| } |
| return min |
| } |
| |
| func visitcode(n *Node, min uint32) uint32 { |
| var fn *Node |
| var m uint32 |
| |
| if n == nil { |
| return min |
| } |
| |
| min = visitcodelist(n.Ninit, min) |
| min = visitcode(n.Left, min) |
| min = visitcode(n.Right, min) |
| min = visitcodelist(n.List, min) |
| min = visitcode(n.Ntest, min) |
| min = visitcode(n.Nincr, min) |
| min = visitcodelist(n.Nbody, min) |
| min = visitcodelist(n.Nelse, min) |
| min = visitcodelist(n.Rlist, min) |
| |
| if n.Op == OCALLFUNC || n.Op == OCALLMETH { |
| fn = n.Left |
| if n.Op == OCALLMETH { |
| fn = n.Left.Right.Sym.Def |
| } |
| if fn != nil && fn.Op == ONAME && fn.Class == PFUNC && fn.Defn != nil { |
| m = visit(fn.Defn) |
| if m < min { |
| min = m |
| } |
| } |
| } |
| |
| if n.Op == OCLOSURE { |
| m = visit(n.Closure) |
| if m < min { |
| min = m |
| } |
| } |
| |
| return min |
| } |
| |
| // An escape analysis pass for a set of functions. |
| // |
| // First escfunc, esc and escassign recurse over the ast of each |
| // function to dig out flow(dst,src) edges between any |
| // pointer-containing nodes and store them in dst->escflowsrc. For |
| // variables assigned to a variable in an outer scope or used as a |
| // return value, they store a flow(theSink, src) edge to a fake node |
| // 'the Sink'. For variables referenced in closures, an edge |
| // flow(closure, &var) is recorded and the flow of a closure itself to |
| // an outer scope is tracked the same way as other variables. |
| // |
| // Then escflood walks the graph starting at theSink and tags all |
| // variables of it can reach an & node as escaping and all function |
| // parameters it can reach as leaking. |
| // |
| // If a value's address is taken but the address does not escape, |
| // then the value can stay on the stack. If the value new(T) does |
| // not escape, then new(T) can be rewritten into a stack allocation. |
| // The same is true of slice literals. |
| // |
| // If optimizations are disabled (-N), this code is not used. |
| // Instead, the compiler assumes that any value whose address |
| // is taken without being immediately dereferenced |
| // needs to be moved to the heap, and new(T) and slice |
| // literals are always real allocations. |
| |
| type EscState struct { |
| theSink Node |
| funcParam Node |
| dsts *NodeList |
| loopdepth int |
| pdepth int |
| dstcount int |
| edgecount int |
| noesc *NodeList |
| recursive bool |
| } |
| |
| var tags [16]*Strlit |
| |
| func mktag(mask int) *Strlit { |
| var s *Strlit |
| var buf string |
| |
| switch mask & EscMask { |
| case EscNone, |
| EscReturn: |
| break |
| |
| default: |
| Fatal("escape mktag") |
| } |
| |
| mask >>= EscBits |
| |
| if mask < len(tags) && tags[mask] != nil { |
| return tags[mask] |
| } |
| |
| buf = fmt.Sprintf("esc:0x%x", mask) |
| s = newstrlit(buf) |
| if mask < len(tags) { |
| tags[mask] = s |
| } |
| return s |
| } |
| |
| func parsetag(note *Strlit) int { |
| var em int |
| |
| if note == nil { |
| return EscUnknown |
| } |
| if !strings.HasPrefix(note.S, "esc:") { |
| return EscUnknown |
| } |
| em = atoi(note.S[4:]) |
| if em == 0 { |
| return EscNone |
| } |
| return EscReturn | em<<EscBits |
| } |
| |
| func analyze(all *NodeList, recursive bool) { |
| var l *NodeList |
| var es EscState |
| var e *EscState |
| |
| es = EscState{} |
| e = &es |
| e.theSink.Op = ONAME |
| e.theSink.Orig = &e.theSink |
| e.theSink.Class = PEXTERN |
| e.theSink.Sym = Lookup(".sink") |
| e.theSink.Escloopdepth = -1 |
| e.recursive = recursive |
| |
| e.funcParam.Op = ONAME |
| e.funcParam.Orig = &e.funcParam |
| e.funcParam.Class = PAUTO |
| e.funcParam.Sym = Lookup(".param") |
| e.funcParam.Escloopdepth = 10000000 |
| |
| for l = all; l != nil; l = l.Next { |
| if l.N.Op == ODCLFUNC { |
| l.N.Esc = EscFuncPlanned |
| } |
| } |
| |
| // flow-analyze functions |
| for l = all; l != nil; l = l.Next { |
| if l.N.Op == ODCLFUNC { |
| escfunc(e, l.N) |
| } |
| } |
| |
| // print("escapes: %d e->dsts, %d edges\n", e->dstcount, e->edgecount); |
| |
| // visit the upstream of each dst, mark address nodes with |
| // addrescapes, mark parameters unsafe |
| for l = e.dsts; l != nil; l = l.Next { |
| escflood(e, l.N) |
| } |
| |
| // for all top level functions, tag the typenodes corresponding to the param nodes |
| for l = all; l != nil; l = l.Next { |
| if l.N.Op == ODCLFUNC { |
| esctag(e, l.N) |
| } |
| } |
| |
| if Debug['m'] != 0 { |
| for l = e.noesc; l != nil; l = l.Next { |
| if l.N.Esc == EscNone { |
| var tmp *Sym |
| if l.N.Curfn != nil && l.N.Curfn.Nname != nil { |
| tmp = l.N.Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| Warnl(int(l.N.Lineno), "%v %v does not escape", Sconv(tmp, 0), Nconv(l.N, obj.FmtShort)) |
| } |
| } |
| } |
| } |
| |
| func escfunc(e *EscState, func_ *Node) { |
| var savefn *Node |
| var ll *NodeList |
| var saveld int |
| |
| // print("escfunc %N %s\n", func->nname, e->recursive?"(recursive)":""); |
| |
| if func_.Esc != 1 { |
| Fatal("repeat escfunc %v", Nconv(func_.Nname, 0)) |
| } |
| func_.Esc = EscFuncStarted |
| |
| saveld = e.loopdepth |
| e.loopdepth = 1 |
| savefn = Curfn |
| Curfn = func_ |
| |
| for ll = Curfn.Dcl; ll != nil; ll = ll.Next { |
| if ll.N.Op != ONAME { |
| continue |
| } |
| switch ll.N.Class { |
| // out params are in a loopdepth between the sink and all local variables |
| case PPARAMOUT: |
| ll.N.Escloopdepth = 0 |
| |
| case PPARAM: |
| ll.N.Escloopdepth = 1 |
| if ll.N.Type != nil && !haspointers(ll.N.Type) { |
| break |
| } |
| if Curfn.Nbody == nil && !Curfn.Noescape { |
| ll.N.Esc = EscHeap |
| } else { |
| ll.N.Esc = EscNone // prime for escflood later |
| } |
| e.noesc = list(e.noesc, ll.N) |
| } |
| } |
| |
| // in a mutually recursive group we lose track of the return values |
| if e.recursive { |
| for ll = Curfn.Dcl; ll != nil; ll = ll.Next { |
| if ll.N.Op == ONAME && ll.N.Class == PPARAMOUT { |
| escflows(e, &e.theSink, ll.N) |
| } |
| } |
| } |
| |
| escloopdepthlist(e, Curfn.Nbody) |
| esclist(e, Curfn.Nbody, Curfn) |
| Curfn = savefn |
| e.loopdepth = saveld |
| } |
| |
| // Mark labels that have no backjumps to them as not increasing e->loopdepth. |
| // Walk hasn't generated (goto|label)->left->sym->label yet, so we'll cheat |
| // and set it to one of the following two. Then in esc we'll clear it again. |
| var looping Label |
| |
| var nonlooping Label |
| |
| func escloopdepthlist(e *EscState, l *NodeList) { |
| for ; l != nil; l = l.Next { |
| escloopdepth(e, l.N) |
| } |
| } |
| |
| func escloopdepth(e *EscState, n *Node) { |
| if n == nil { |
| return |
| } |
| |
| escloopdepthlist(e, n.Ninit) |
| |
| switch n.Op { |
| case OLABEL: |
| if n.Left == nil || n.Left.Sym == nil { |
| Fatal("esc:label without label: %v", Nconv(n, obj.FmtSign)) |
| } |
| |
| // Walk will complain about this label being already defined, but that's not until |
| // after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc |
| // if(n->left->sym->label != nil) |
| // fatal("escape analysis messed up analyzing label: %+N", n); |
| n.Left.Sym.Label = &nonlooping |
| |
| case OGOTO: |
| if n.Left == nil || n.Left.Sym == nil { |
| Fatal("esc:goto without label: %v", Nconv(n, obj.FmtSign)) |
| } |
| |
| // If we come past one that's uninitialized, this must be a (harmless) forward jump |
| // but if it's set to nonlooping the label must have preceded this goto. |
| if n.Left.Sym.Label == &nonlooping { |
| n.Left.Sym.Label = &looping |
| } |
| } |
| |
| escloopdepth(e, n.Left) |
| escloopdepth(e, n.Right) |
| escloopdepthlist(e, n.List) |
| escloopdepth(e, n.Ntest) |
| escloopdepth(e, n.Nincr) |
| escloopdepthlist(e, n.Nbody) |
| escloopdepthlist(e, n.Nelse) |
| escloopdepthlist(e, n.Rlist) |
| } |
| |
| func esclist(e *EscState, l *NodeList, up *Node) { |
| for ; l != nil; l = l.Next { |
| esc(e, l.N, up) |
| } |
| } |
| |
| func esc(e *EscState, n *Node, up *Node) { |
| var lno int |
| var ll *NodeList |
| var lr *NodeList |
| var a *Node |
| var v *Node |
| |
| if n == nil { |
| return |
| } |
| |
| lno = int(setlineno(n)) |
| |
| // ninit logically runs at a different loopdepth than the rest of the for loop. |
| esclist(e, n.Ninit, n) |
| |
| if n.Op == OFOR || n.Op == ORANGE { |
| e.loopdepth++ |
| } |
| |
| // type switch variables have no ODCL. |
| // process type switch as declaration. |
| // must happen before processing of switch body, |
| // so before recursion. |
| if n.Op == OSWITCH && n.Ntest != nil && n.Ntest.Op == OTYPESW { |
| for ll = n.List; ll != nil; ll = ll.Next { // cases |
| |
| // ll->n->nname is the variable per case |
| if ll.N.Nname != nil { |
| ll.N.Nname.Escloopdepth = e.loopdepth |
| } |
| } |
| } |
| |
| esc(e, n.Left, n) |
| esc(e, n.Right, n) |
| esc(e, n.Ntest, n) |
| esc(e, n.Nincr, n) |
| esclist(e, n.Nbody, n) |
| esclist(e, n.Nelse, n) |
| esclist(e, n.List, n) |
| esclist(e, n.Rlist, n) |
| |
| if n.Op == OFOR || n.Op == ORANGE { |
| e.loopdepth-- |
| } |
| |
| if Debug['m'] > 1 { |
| var tmp *Sym |
| if Curfn != nil && Curfn.Nname != nil { |
| tmp = Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| fmt.Printf("%v:[%d] %v esc: %v\n", Ctxt.Line(int(lineno)), e.loopdepth, Sconv(tmp, 0), Nconv(n, 0)) |
| } |
| |
| switch n.Op { |
| // Record loop depth at declaration. |
| case ODCL: |
| if n.Left != nil { |
| n.Left.Escloopdepth = e.loopdepth |
| } |
| |
| case OLABEL: |
| if n.Left.Sym.Label == &nonlooping { |
| if Debug['m'] > 1 { |
| fmt.Printf("%v:%v non-looping label\n", Ctxt.Line(int(lineno)), Nconv(n, 0)) |
| } |
| } else if n.Left.Sym.Label == &looping { |
| if Debug['m'] > 1 { |
| fmt.Printf("%v: %v looping label\n", Ctxt.Line(int(lineno)), Nconv(n, 0)) |
| } |
| e.loopdepth++ |
| } |
| |
| // See case OLABEL in escloopdepth above |
| // else if(n->left->sym->label == nil) |
| // fatal("escape analysis missed or messed up a label: %+N", n); |
| |
| n.Left.Sym.Label = nil |
| |
| // Everything but fixed array is a dereference. |
| case ORANGE: |
| if Isfixedarray(n.Type) && n.List != nil && n.List.Next != nil { |
| escassign(e, n.List.Next.N, n.Right) |
| } |
| |
| case OSWITCH: |
| if n.Ntest != nil && n.Ntest.Op == OTYPESW { |
| for ll = n.List; ll != nil; ll = ll.Next { // cases |
| |
| // ntest->right is the argument of the .(type), |
| // ll->n->nname is the variable per case |
| escassign(e, ll.N.Nname, n.Ntest.Right) |
| } |
| } |
| |
| // Filter out the following special case. |
| // |
| // func (b *Buffer) Foo() { |
| // n, m := ... |
| // b.buf = b.buf[n:m] |
| // } |
| // |
| // This assignment is a no-op for escape analysis, |
| // it does not store any new pointers into b that were not already there. |
| // However, without this special case b will escape, because we assign to OIND/ODOTPTR. |
| case OAS, |
| OASOP: |
| if (n.Left.Op == OIND || n.Left.Op == ODOTPTR) && n.Left.Left.Op == ONAME && (n.Right.Op == OSLICE || n.Right.Op == OSLICE3 || n.Right.Op == OSLICESTR) && (n.Right.Left.Op == OIND || n.Right.Left.Op == ODOTPTR) && n.Right.Left.Left.Op == ONAME && n.Left.Left == n.Right.Left.Left { // dst is ONAME dereference // src is slice operation // slice is applied to ONAME dereference // dst and src reference the same base ONAME |
| |
| // Here we also assume that the statement will not contain calls, |
| // that is, that order will move any calls to init. |
| // Otherwise base ONAME value could change between the moments |
| // when we evaluate it for dst and for src. |
| // |
| // Note, this optimization does not apply to OSLICEARR, |
| // because it does introduce a new pointer into b that was not already there |
| // (pointer to b itself). After such assignment, if b contents escape, |
| // b escapes as well. If we ignore such OSLICEARR, we will conclude |
| // that b does not escape when b contents do. |
| if Debug['m'] != 0 { |
| var tmp *Sym |
| if n.Curfn != nil && n.Curfn.Nname != nil { |
| tmp = n.Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| Warnl(int(n.Lineno), "%v ignoring self-assignment to %v", Sconv(tmp, 0), Nconv(n.Left, obj.FmtShort)) |
| } |
| |
| break |
| } |
| |
| escassign(e, n.Left, n.Right) |
| |
| case OAS2: // x,y = a,b |
| if count(n.List) == count(n.Rlist) { |
| ll = n.List |
| lr = n.Rlist |
| for ; ll != nil; (func() { ll = ll.Next; lr = lr.Next })() { |
| escassign(e, ll.N, lr.N) |
| } |
| } |
| |
| case OAS2RECV, // v, ok = <-ch |
| OAS2MAPR, // v, ok = m[k] |
| OAS2DOTTYPE: // v, ok = x.(type) |
| escassign(e, n.List.N, n.Rlist.N) |
| |
| case OSEND: // ch <- x |
| escassign(e, &e.theSink, n.Right) |
| |
| case ODEFER: |
| if e.loopdepth == 1 { // top level |
| break |
| } |
| fallthrough |
| |
| // go f(x) - f and x escape |
| // arguments leak out of scope |
| // TODO: leak to a dummy node instead |
| // fallthrough |
| case OPROC: |
| escassign(e, &e.theSink, n.Left.Left) |
| |
| escassign(e, &e.theSink, n.Left.Right) // ODDDARG for call |
| for ll = n.Left.List; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N) |
| } |
| |
| case OCALLMETH, |
| OCALLFUNC, |
| OCALLINTER: |
| esccall(e, n, up) |
| |
| // esccall already done on n->rlist->n. tie it's escretval to n->list |
| case OAS2FUNC: // x,y = f() |
| lr = n.Rlist.N.Escretval |
| |
| for ll = n.List; lr != nil && ll != nil; (func() { lr = lr.Next; ll = ll.Next })() { |
| escassign(e, ll.N, lr.N) |
| } |
| if lr != nil || ll != nil { |
| Fatal("esc oas2func") |
| } |
| |
| case ORETURN: |
| ll = n.List |
| if count(n.List) == 1 && Curfn.Type.Outtuple > 1 { |
| // OAS2FUNC in disguise |
| // esccall already done on n->list->n |
| // tie n->list->n->escretval to curfn->dcl PPARAMOUT's |
| ll = n.List.N.Escretval |
| } |
| |
| for lr = Curfn.Dcl; lr != nil && ll != nil; lr = lr.Next { |
| if lr.N.Op != ONAME || lr.N.Class != PPARAMOUT { |
| continue |
| } |
| escassign(e, lr.N, ll.N) |
| ll = ll.Next |
| } |
| |
| if ll != nil { |
| Fatal("esc return list") |
| } |
| |
| // Argument could leak through recover. |
| case OPANIC: |
| escassign(e, &e.theSink, n.Left) |
| |
| case OAPPEND: |
| if n.Isddd == 0 { |
| for ll = n.List.Next; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N) // lose track of assign to dereference |
| } |
| } |
| |
| case OCONV, |
| OCONVNOP, |
| OCONVIFACE: |
| escassign(e, n, n.Left) |
| |
| case OARRAYLIT: |
| if Isslice(n.Type) { |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| n.Escloopdepth = e.loopdepth |
| |
| // Values make it to memory, lose track. |
| for ll = n.List; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N.Right) |
| } |
| } else { |
| // Link values to array. |
| for ll = n.List; ll != nil; ll = ll.Next { |
| escassign(e, n, ll.N.Right) |
| } |
| } |
| |
| // Link values to struct. |
| case OSTRUCTLIT: |
| for ll = n.List; ll != nil; ll = ll.Next { |
| escassign(e, n, ll.N.Right) |
| } |
| |
| case OPTRLIT: |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| n.Escloopdepth = e.loopdepth |
| |
| // Link OSTRUCTLIT to OPTRLIT; if OPTRLIT escapes, OSTRUCTLIT elements do too. |
| escassign(e, n, n.Left) |
| |
| case OCALLPART: |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| n.Escloopdepth = e.loopdepth |
| |
| // Contents make it to memory, lose track. |
| escassign(e, &e.theSink, n.Left) |
| |
| case OMAPLIT: |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| n.Escloopdepth = e.loopdepth |
| |
| // Keys and values make it to memory, lose track. |
| for ll = n.List; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N.Left) |
| escassign(e, &e.theSink, ll.N.Right) |
| } |
| |
| // Link addresses of captured variables to closure. |
| case OCLOSURE: |
| for ll = n.Cvars; ll != nil; ll = ll.Next { |
| v = ll.N |
| if v.Op == OXXX { // unnamed out argument; see dcl.c:/^funcargs |
| continue |
| } |
| a = v.Closure |
| if v.Byval == 0 { |
| a = Nod(OADDR, a, nil) |
| a.Lineno = v.Lineno |
| a.Escloopdepth = e.loopdepth |
| typecheck(&a, Erv) |
| } |
| |
| escassign(e, n, a) |
| } |
| fallthrough |
| |
| // fallthrough |
| case OMAKECHAN, |
| OMAKEMAP, |
| OMAKESLICE, |
| ONEW, |
| OARRAYRUNESTR, |
| OARRAYBYTESTR, |
| OSTRARRAYRUNE, |
| OSTRARRAYBYTE, |
| ORUNESTR: |
| n.Escloopdepth = e.loopdepth |
| |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| |
| case OADDSTR: |
| n.Escloopdepth = e.loopdepth |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| |
| // Arguments of OADDSTR do not escape. |
| |
| case OADDR: |
| n.Esc = EscNone // until proven otherwise |
| e.noesc = list(e.noesc, n) |
| |
| // current loop depth is an upper bound on actual loop depth |
| // of addressed value. |
| n.Escloopdepth = e.loopdepth |
| |
| // for &x, use loop depth of x if known. |
| // it should always be known, but if not, be conservative |
| // and keep the current loop depth. |
| if n.Left.Op == ONAME { |
| switch n.Left.Class { |
| case PAUTO: |
| if n.Left.Escloopdepth != 0 { |
| n.Escloopdepth = n.Left.Escloopdepth |
| } |
| |
| // PPARAM is loop depth 1 always. |
| // PPARAMOUT is loop depth 0 for writes |
| // but considered loop depth 1 for address-of, |
| // so that writing the address of one result |
| // to another (or the same) result makes the |
| // first result move to the heap. |
| case PPARAM, |
| PPARAMOUT: |
| n.Escloopdepth = 1 |
| } |
| } |
| } |
| |
| lineno = int32(lno) |
| } |
| |
| // Assert that expr somehow gets assigned to dst, if non nil. for |
| // dst==nil, any name node expr still must be marked as being |
| // evaluated in curfn. For expr==nil, dst must still be examined for |
| // evaluations inside it (e.g *f(x) = y) |
| func escassign(e *EscState, dst *Node, src *Node) { |
| var lno int |
| var ll *NodeList |
| |
| if isblank(dst) || dst == nil || src == nil || src.Op == ONONAME || src.Op == OXXX { |
| return |
| } |
| |
| if Debug['m'] > 1 { |
| var tmp *Sym |
| if Curfn != nil && Curfn.Nname != nil { |
| tmp = Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| fmt.Printf("%v:[%d] %v escassign: %v(%v) = %v(%v)\n", Ctxt.Line(int(lineno)), e.loopdepth, Sconv(tmp, 0), Nconv(dst, obj.FmtShort), Jconv(dst, obj.FmtShort), Nconv(src, obj.FmtShort), Jconv(src, obj.FmtShort)) |
| } |
| |
| setlineno(dst) |
| |
| // Analyze lhs of assignment. |
| // Replace dst with e->theSink if we can't track it. |
| switch dst.Op { |
| default: |
| Dump("dst", dst) |
| Fatal("escassign: unexpected dst") |
| |
| case OARRAYLIT, |
| OCLOSURE, |
| OCONV, |
| OCONVIFACE, |
| OCONVNOP, |
| OMAPLIT, |
| OSTRUCTLIT, |
| OPTRLIT, |
| OCALLPART: |
| break |
| |
| case ONAME: |
| if dst.Class == PEXTERN { |
| dst = &e.theSink |
| } |
| |
| case ODOT: // treat "dst.x = src" as "dst = src" |
| escassign(e, dst.Left, src) |
| |
| return |
| |
| case OINDEX: |
| if Isfixedarray(dst.Left.Type) { |
| escassign(e, dst.Left, src) |
| return |
| } |
| |
| dst = &e.theSink // lose track of dereference |
| |
| case OIND, |
| ODOTPTR: |
| dst = &e.theSink // lose track of dereference |
| |
| // lose track of key and value |
| case OINDEXMAP: |
| escassign(e, &e.theSink, dst.Right) |
| |
| dst = &e.theSink |
| } |
| |
| lno = int(setlineno(src)) |
| e.pdepth++ |
| |
| switch src.Op { |
| case OADDR, // dst = &x |
| OIND, // dst = *x |
| ODOTPTR, // dst = (*x).f |
| ONAME, |
| OPARAM, |
| ODDDARG, |
| OPTRLIT, |
| OARRAYLIT, |
| OMAPLIT, |
| OSTRUCTLIT, |
| OMAKECHAN, |
| OMAKEMAP, |
| OMAKESLICE, |
| OARRAYRUNESTR, |
| OARRAYBYTESTR, |
| OSTRARRAYRUNE, |
| OSTRARRAYBYTE, |
| OADDSTR, |
| ONEW, |
| OCLOSURE, |
| OCALLPART, |
| ORUNESTR: |
| escflows(e, dst, src) |
| |
| // Flowing multiple returns to a single dst happens when |
| // analyzing "go f(g())": here g() flows to sink (issue 4529). |
| case OCALLMETH, |
| OCALLFUNC, |
| OCALLINTER: |
| for ll = src.Escretval; ll != nil; ll = ll.Next { |
| escflows(e, dst, ll.N) |
| } |
| |
| // A non-pointer escaping from a struct does not concern us. |
| case ODOT: |
| if src.Type != nil && !haspointers(src.Type) { |
| break |
| } |
| fallthrough |
| |
| // Conversions, field access, slice all preserve the input value. |
| // fallthrough |
| case OCONV, |
| OCONVIFACE, |
| OCONVNOP, |
| ODOTMETH, |
| // treat recv.meth as a value with recv in it, only happens in ODEFER and OPROC |
| // iface.method already leaks iface in esccall, no need to put in extra ODOTINTER edge here |
| ODOTTYPE, |
| ODOTTYPE2, |
| OSLICE, |
| OSLICE3, |
| OSLICEARR, |
| OSLICE3ARR, |
| OSLICESTR: |
| escassign(e, dst, src.Left) |
| |
| // Append returns first argument. |
| case OAPPEND: |
| escassign(e, dst, src.List.N) |
| |
| // Index of array preserves input value. |
| case OINDEX: |
| if Isfixedarray(src.Left.Type) { |
| escassign(e, dst, src.Left) |
| } |
| |
| // Might be pointer arithmetic, in which case |
| // the operands flow into the result. |
| // TODO(rsc): Decide what the story is here. This is unsettling. |
| case OADD, |
| OSUB, |
| OOR, |
| OXOR, |
| OMUL, |
| ODIV, |
| OMOD, |
| OLSH, |
| ORSH, |
| OAND, |
| OANDNOT, |
| OPLUS, |
| OMINUS, |
| OCOM: |
| escassign(e, dst, src.Left) |
| |
| escassign(e, dst, src.Right) |
| } |
| |
| e.pdepth-- |
| lineno = int32(lno) |
| } |
| |
| func escassignfromtag(e *EscState, note *Strlit, dsts *NodeList, src *Node) int { |
| var em int |
| var em0 int |
| |
| em = parsetag(note) |
| |
| if em == EscUnknown { |
| escassign(e, &e.theSink, src) |
| return em |
| } |
| |
| if em == EscNone { |
| return em |
| } |
| |
| // If content inside parameter (reached via indirection) |
| // escapes back to results, mark as such. |
| if em&EscContentEscapes != 0 { |
| escassign(e, &e.funcParam, src) |
| } |
| |
| em0 = em |
| for em >>= EscReturnBits; em != 0 && dsts != nil; (func() { em >>= 1; dsts = dsts.Next })() { |
| if em&1 != 0 { |
| escassign(e, dsts.N, src) |
| } |
| } |
| |
| if em != 0 && dsts == nil { |
| Fatal("corrupt esc tag %v or messed up escretval list\n", Zconv(note, 0)) |
| } |
| return em0 |
| } |
| |
| // This is a bit messier than fortunate, pulled out of esc's big |
| // switch for clarity. We either have the paramnodes, which may be |
| // connected to other things through flows or we have the parameter type |
| // nodes, which may be marked "noescape". Navigating the ast is slightly |
| // different for methods vs plain functions and for imported vs |
| // this-package |
| func esccall(e *EscState, n *Node, up *Node) { |
| var ll *NodeList |
| var lr *NodeList |
| var a *Node |
| var fn *Node |
| var src *Node |
| var t *Type |
| var fntype *Type |
| var buf string |
| var i int |
| |
| fn = nil |
| switch n.Op { |
| default: |
| Fatal("esccall") |
| |
| case OCALLFUNC: |
| fn = n.Left |
| fntype = fn.Type |
| |
| case OCALLMETH: |
| fn = n.Left.Right.Sym.Def |
| if fn != nil { |
| fntype = fn.Type |
| } else { |
| fntype = n.Left.Type |
| } |
| |
| case OCALLINTER: |
| fntype = n.Left.Type |
| } |
| |
| ll = n.List |
| if n.List != nil && n.List.Next == nil { |
| a = n.List.N |
| if a.Type.Etype == TSTRUCT && a.Type.Funarg != 0 { // f(g()). |
| ll = a.Escretval |
| } |
| } |
| |
| if fn != nil && fn.Op == ONAME && fn.Class == PFUNC && fn.Defn != nil && fn.Defn.Nbody != nil && fn.Ntype != nil && fn.Defn.Esc < EscFuncTagged { |
| // function in same mutually recursive group. Incorporate into flow graph. |
| // print("esc local fn: %N\n", fn->ntype); |
| if fn.Defn.Esc == EscFuncUnknown || n.Escretval != nil { |
| Fatal("graph inconsistency") |
| } |
| |
| // set up out list on this call node |
| for lr = fn.Ntype.Rlist; lr != nil; lr = lr.Next { |
| n.Escretval = list(n.Escretval, lr.N.Left) // type.rlist -> dclfield -> ONAME (PPARAMOUT) |
| } |
| |
| // Receiver. |
| if n.Op != OCALLFUNC { |
| escassign(e, fn.Ntype.Left.Left, n.Left.Left) |
| } |
| |
| for lr = fn.Ntype.List; ll != nil && lr != nil; (func() { ll = ll.Next; lr = lr.Next })() { |
| src = ll.N |
| if lr.N.Isddd != 0 && n.Isddd == 0 { |
| // Introduce ODDDARG node to represent ... allocation. |
| src = Nod(ODDDARG, nil, nil) |
| |
| src.Type = typ(TARRAY) |
| src.Type.Type = lr.N.Type.Type |
| src.Type.Bound = int64(count(ll)) |
| src.Type = Ptrto(src.Type) // make pointer so it will be tracked |
| src.Escloopdepth = e.loopdepth |
| src.Lineno = n.Lineno |
| src.Esc = EscNone // until we find otherwise |
| e.noesc = list(e.noesc, src) |
| n.Right = src |
| } |
| |
| if lr.N.Left != nil { |
| escassign(e, lr.N.Left, src) |
| } |
| if src != ll.N { |
| break |
| } |
| } |
| |
| // "..." arguments are untracked |
| for ; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N) |
| } |
| |
| return |
| } |
| |
| // Imported or completely analyzed function. Use the escape tags. |
| if n.Escretval != nil { |
| Fatal("esc already decorated call %v\n", Nconv(n, obj.FmtSign)) |
| } |
| |
| // set up out list on this call node with dummy auto ONAMES in the current (calling) function. |
| i = 0 |
| |
| for t = getoutargx(fntype).Type; t != nil; t = t.Down { |
| src = Nod(ONAME, nil, nil) |
| buf = fmt.Sprintf(".dum%d", i) |
| i++ |
| src.Sym = Lookup(buf) |
| src.Type = t.Type |
| src.Class = PAUTO |
| src.Curfn = Curfn |
| src.Escloopdepth = e.loopdepth |
| src.Used = 1 |
| src.Lineno = n.Lineno |
| n.Escretval = list(n.Escretval, src) |
| } |
| |
| // print("esc analyzed fn: %#N (%+T) returning (%+H)\n", fn, fntype, n->escretval); |
| |
| // Receiver. |
| if n.Op != OCALLFUNC { |
| t = getthisx(fntype).Type |
| src = n.Left.Left |
| if haspointers(t.Type) { |
| escassignfromtag(e, t.Note, n.Escretval, src) |
| } |
| } |
| |
| for t = getinargx(fntype).Type; ll != nil; ll = ll.Next { |
| src = ll.N |
| if t.Isddd != 0 && n.Isddd == 0 { |
| // Introduce ODDDARG node to represent ... allocation. |
| src = Nod(ODDDARG, nil, nil) |
| |
| src.Escloopdepth = e.loopdepth |
| src.Lineno = n.Lineno |
| src.Type = typ(TARRAY) |
| src.Type.Type = t.Type.Type |
| src.Type.Bound = int64(count(ll)) |
| src.Type = Ptrto(src.Type) // make pointer so it will be tracked |
| src.Esc = EscNone // until we find otherwise |
| e.noesc = list(e.noesc, src) |
| n.Right = src |
| } |
| |
| if haspointers(t.Type) { |
| if escassignfromtag(e, t.Note, n.Escretval, src) == EscNone && up.Op != ODEFER && up.Op != OPROC { |
| a = src |
| for a.Op == OCONVNOP { |
| a = a.Left |
| } |
| switch a.Op { |
| // The callee has already been analyzed, so its arguments have esc tags. |
| // The argument is marked as not escaping at all. |
| // Record that fact so that any temporary used for |
| // synthesizing this expression can be reclaimed when |
| // the function returns. |
| // This 'noescape' is even stronger than the usual esc == EscNone. |
| // src->esc == EscNone means that src does not escape the current function. |
| // src->noescape = 1 here means that src does not escape this statement |
| // in the current function. |
| case OCALLPART, |
| OCLOSURE, |
| ODDDARG, |
| OARRAYLIT, |
| OPTRLIT, |
| OSTRUCTLIT: |
| a.Noescape = true |
| } |
| } |
| } |
| |
| if src != ll.N { |
| break |
| } |
| t = t.Down |
| } |
| |
| // "..." arguments are untracked |
| for ; ll != nil; ll = ll.Next { |
| escassign(e, &e.theSink, ll.N) |
| } |
| } |
| |
| // Store the link src->dst in dst, throwing out some quick wins. |
| func escflows(e *EscState, dst *Node, src *Node) { |
| if dst == nil || src == nil || dst == src { |
| return |
| } |
| |
| // Don't bother building a graph for scalars. |
| if src.Type != nil && !haspointers(src.Type) { |
| return |
| } |
| |
| if Debug['m'] > 2 { |
| fmt.Printf("%v::flows:: %v <- %v\n", Ctxt.Line(int(lineno)), Nconv(dst, obj.FmtShort), Nconv(src, obj.FmtShort)) |
| } |
| |
| if dst.Escflowsrc == nil { |
| e.dsts = list(e.dsts, dst) |
| e.dstcount++ |
| } |
| |
| e.edgecount++ |
| |
| dst.Escflowsrc = list(dst.Escflowsrc, src) |
| } |
| |
| // Whenever we hit a reference node, the level goes up by one, and whenever |
| // we hit an OADDR, the level goes down by one. as long as we're on a level > 0 |
| // finding an OADDR just means we're following the upstream of a dereference, |
| // so this address doesn't leak (yet). |
| // If level == 0, it means the /value/ of this node can reach the root of this flood. |
| // so if this node is an OADDR, it's argument should be marked as escaping iff |
| // it's currfn/e->loopdepth are different from the flood's root. |
| // Once an object has been moved to the heap, all of it's upstream should be considered |
| // escaping to the global scope. |
| func escflood(e *EscState, dst *Node) { |
| var l *NodeList |
| |
| switch dst.Op { |
| case ONAME, |
| OCLOSURE: |
| break |
| |
| default: |
| return |
| } |
| |
| if Debug['m'] > 1 { |
| var tmp *Sym |
| if dst.Curfn != nil && dst.Curfn.Nname != nil { |
| tmp = dst.Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| fmt.Printf("\nescflood:%d: dst %v scope:%v[%d]\n", walkgen, Nconv(dst, obj.FmtShort), Sconv(tmp, 0), dst.Escloopdepth) |
| } |
| |
| for l = dst.Escflowsrc; l != nil; l = l.Next { |
| walkgen++ |
| escwalk(e, 0, dst, l.N) |
| } |
| } |
| |
| // There appear to be some loops in the escape graph, causing |
| // arbitrary recursion into deeper and deeper levels. |
| // Cut this off safely by making minLevel sticky: once you |
| // get that deep, you cannot go down any further but you also |
| // cannot go up any further. This is a conservative fix. |
| // Making minLevel smaller (more negative) would handle more |
| // complex chains of indirections followed by address-of operations, |
| // at the cost of repeating the traversal once for each additional |
| // allowed level when a loop is encountered. Using -2 suffices to |
| // pass all the tests we have written so far, which we assume matches |
| // the level of complexity we want the escape analysis code to handle. |
| const ( |
| MinLevel = -2 |
| ) |
| |
| func escwalk(e *EscState, level int, dst *Node, src *Node) { |
| var ll *NodeList |
| var leaks bool |
| var newlevel int |
| |
| if src.Walkgen == walkgen && src.Esclevel <= int32(level) { |
| return |
| } |
| src.Walkgen = walkgen |
| src.Esclevel = int32(level) |
| |
| if Debug['m'] > 1 { |
| var tmp *Sym |
| if src.Curfn != nil && src.Curfn.Nname != nil { |
| tmp = src.Curfn.Nname.Sym |
| } else { |
| tmp = nil |
| } |
| fmt.Printf("escwalk: level:%d depth:%d %.*s %v(%v) scope:%v[%d]\n", level, e.pdepth, e.pdepth, "\t\t\t\t\t\t\t\t\t\t", Nconv(src, obj.FmtShort), Jconv(src, obj.FmtShort), Sconv(tmp, 0), src.Escloopdepth) |
| } |
| |
| e.pdepth++ |
| |
| // Input parameter flowing to output parameter? |
| if dst.Op == ONAME && dst.Class == PPARAMOUT && dst.Vargen <= 20 { |
| if src.Op == ONAME && src.Class == PPARAM && src.Curfn == dst.Curfn && src.Esc != EscScope && src.Esc != EscHeap { |
| if level == 0 { |
| if Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "leaking param: %v to result %v", Nconv(src, obj.FmtShort), Sconv(dst.Sym, 0)) |
| } |
| if src.Esc&EscMask != EscReturn { |
| src.Esc = EscReturn |
| } |
| src.Esc |= 1 << uint((dst.Vargen-1)+EscReturnBits) |
| goto recurse |
| } else if level > 0 { |
| if Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "%v leaking param %v content to result %v", Nconv(src.Curfn.Nname, 0), Nconv(src, obj.FmtShort), Sconv(dst.Sym, 0)) |
| } |
| if src.Esc&EscMask != EscReturn { |
| src.Esc = EscReturn |
| } |
| src.Esc |= EscContentEscapes |
| goto recurse |
| } |
| } |
| } |
| |
| // The second clause is for values pointed at by an object passed to a call |
| // that returns something reached via indirect from the object. |
| // We don't know which result it is or how many indirects, so we treat it as leaking. |
| leaks = level <= 0 && dst.Escloopdepth < src.Escloopdepth || level < 0 && dst == &e.funcParam && haspointers(src.Type) |
| |
| switch src.Op { |
| case ONAME: |
| if src.Class == PPARAM && (leaks || dst.Escloopdepth < 0) && src.Esc != EscHeap { |
| src.Esc = EscScope |
| if Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "leaking param: %v", Nconv(src, obj.FmtShort)) |
| } |
| } |
| |
| // Treat a PPARAMREF closure variable as equivalent to the |
| // original variable. |
| if src.Class == PPARAMREF { |
| if leaks && Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "leaking closure reference %v", Nconv(src, obj.FmtShort)) |
| } |
| escwalk(e, level, dst, src.Closure) |
| } |
| |
| case OPTRLIT, |
| OADDR: |
| if leaks { |
| src.Esc = EscHeap |
| addrescapes(src.Left) |
| if Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "%v escapes to heap", Nconv(src, obj.FmtShort)) |
| } |
| } |
| |
| newlevel = level |
| if level > MinLevel { |
| newlevel-- |
| } |
| escwalk(e, newlevel, dst, src.Left) |
| |
| case OARRAYLIT: |
| if Isfixedarray(src.Type) { |
| break |
| } |
| fallthrough |
| |
| // fall through |
| case ODDDARG, |
| OMAKECHAN, |
| OMAKEMAP, |
| OMAKESLICE, |
| OARRAYRUNESTR, |
| OARRAYBYTESTR, |
| OSTRARRAYRUNE, |
| OSTRARRAYBYTE, |
| OADDSTR, |
| OMAPLIT, |
| ONEW, |
| OCLOSURE, |
| OCALLPART, |
| ORUNESTR: |
| if leaks { |
| src.Esc = EscHeap |
| if Debug['m'] != 0 { |
| Warnl(int(src.Lineno), "%v escapes to heap", Nconv(src, obj.FmtShort)) |
| } |
| } |
| |
| case ODOT, |
| OSLICE, |
| OSLICEARR, |
| OSLICE3, |
| OSLICE3ARR, |
| OSLICESTR: |
| escwalk(e, level, dst, src.Left) |
| |
| case OINDEX: |
| if Isfixedarray(src.Left.Type) { |
| escwalk(e, level, dst, src.Left) |
| break |
| } |
| fallthrough |
| |
| // fall through |
| case ODOTPTR, |
| OINDEXMAP, |
| OIND: |
| newlevel = level |
| |
| if level > MinLevel { |
| newlevel++ |
| } |
| escwalk(e, newlevel, dst, src.Left) |
| } |
| |
| recurse: |
| for ll = src.Escflowsrc; ll != nil; ll = ll.Next { |
| escwalk(e, level, dst, ll.N) |
| } |
| |
| e.pdepth-- |
| } |
| |
| func esctag(e *EscState, func_ *Node) { |
| var savefn *Node |
| var ll *NodeList |
| var t *Type |
| |
| func_.Esc = EscFuncTagged |
| |
| // External functions are assumed unsafe, |
| // unless //go:noescape is given before the declaration. |
| if func_.Nbody == nil { |
| if func_.Noescape { |
| for t = getinargx(func_.Type).Type; t != nil; t = t.Down { |
| if haspointers(t.Type) { |
| t.Note = mktag(EscNone) |
| } |
| } |
| } |
| |
| return |
| } |
| |
| savefn = Curfn |
| Curfn = func_ |
| |
| for ll = Curfn.Dcl; ll != nil; ll = ll.Next { |
| if ll.N.Op != ONAME || ll.N.Class != PPARAM { |
| continue |
| } |
| |
| switch ll.N.Esc & EscMask { |
| case EscNone, // not touched by escflood |
| EscReturn: |
| if haspointers(ll.N.Type) { // don't bother tagging for scalars |
| ll.N.Paramfld.Note = mktag(int(ll.N.Esc)) |
| } |
| |
| case EscHeap, // touched by escflood, moved to heap |
| EscScope: // touched by escflood, value leaves scope |
| break |
| } |
| } |
| |
| Curfn = savefn |
| } |
