src/cmd/compile/internal/escape/graph.go - go - Git at Google

 // 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 escape

 import (
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/ir"
 	"cmd/compile/internal/logopt"
 	"cmd/compile/internal/types"
 	"fmt"
 )

 // 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)
 //    }

 // An location represents an abstract location that stores a Go
 // variable.
 type location struct {
 	n         ir.Node  // represented variable or expression, if any
 	curfn     *ir.Func // enclosing function
 	edges     []edge   // incoming edges
 	loopDepth int      // loopDepth at declaration

 	// resultIndex records the tuple index (starting at 1) for
 	// PPARAMOUT variables within their function's result type.
 	// For non-PPARAMOUT variables it's 0.
 	resultIndex int

 	// derefs and walkgen are used during walkOne to track the
 	// minimal dereferences from the walk root.
 	derefs  int // >= -1
 	walkgen uint32

 	// dst and dstEdgeindex track the next immediate assignment
 	// destination location during walkone, along with the index
 	// of the edge pointing back to this location.
 	dst        *location
 	dstEdgeIdx int

 	// queued is used by walkAll to track whether this location is
 	// in the walk queue.
 	queued bool

 	// 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 leak set.
 	paramEsc leaks

 	captured   bool // has a closure captured this variable?
 	reassigned bool // has this variable been reassigned?
 	addrtaken  bool // has this variable's address been taken?
 }

 // An edge represents an assignment edge between two Go variables.
 type edge struct {
 	src    *location
 	derefs int // >= -1
 	notes  *note
 }

 func (l *location) asHole() hole {
 	return hole{dst: l}
 }

 // leak records that parameter l leaks to sink.
 func (l *location) leakTo(sink *location, derefs int) {
 	// If sink is a result parameter that doesn't escape (#44614)
 	// and we can fit return bits into the escape analysis tag,
 	// then record as a result leak.
 	if !sink.escapes && sink.isName(ir.PPARAMOUT) && sink.curfn == l.curfn {
 		ri := sink.resultIndex - 1
 		if ri < numEscResults {
 			// Leak to result parameter.
 			l.paramEsc.AddResult(ri, derefs)
 			return
 		}
 	}

 	// Otherwise, record as heap leak.
 	l.paramEsc.AddHeap(derefs)
 }

 func (l *location) isName(c ir.Class) bool {
 	return l.n != nil && l.n.Op() == ir.ONAME && l.n.(*ir.Name).Class == c
 }

 // A hole represents a context for evaluation of a Go
 // expression. E.g., when evaluating p in "x = **p", we'd have a hole
 // with dst==x and derefs==2.
 type hole struct {
 	dst    *location
 	derefs int // >= -1
 	notes  *note

 	// addrtaken indicates whether this context is taking the address of
 	// the expression, independent of whether the address will actually
 	// be stored into a variable.
 	addrtaken bool
 }

 type note struct {
 	next  *note
 	where ir.Node
 	why   string
 }

 func (k hole) note(where ir.Node, why string) hole {
 	if where == nil || why == "" {
 		base.Fatalf("note: missing where/why")
 	}
 	if base.Flag.LowerM >= 2 || logopt.Enabled() {
 		k.notes = &note{
 			next:  k.notes,
 			where: where,
 			why:   why,
 		}
 	}
 	return k
 }

 func (k hole) shift(delta int) hole {
 	k.derefs += delta
 	if k.derefs < -1 {
 		base.Fatalf("derefs underflow: %v", k.derefs)
 	}
 	k.addrtaken = delta < 0
 	return k
 }

 func (k hole) deref(where ir.Node, why string) hole { return k.shift(1).note(where, why) }
 func (k hole) addr(where ir.Node, why string) hole  { return k.shift(-1).note(where, why) }

 func (k hole) dotType(t *types.Type, where ir.Node, why string) hole {
 	if !t.IsInterface() && !types.IsDirectIface(t) {
 		k = k.shift(1)
 	}
 	return k.note(where, why)
 }

 func (b *batch) flow(k hole, src *location) {
 	if k.addrtaken {
 		src.addrtaken = true
 	}

 	dst := k.dst
 	if dst == &b.blankLoc {
 		return
 	}
 	if dst == src && k.derefs >= 0 { // dst = dst, dst = *dst, ...
 		return
 	}
 	if dst.escapes && k.derefs < 0 { // dst = &src
 		if base.Flag.LowerM >= 2 || logopt.Enabled() {
 			pos := base.FmtPos(src.n.Pos())
 			if base.Flag.LowerM >= 2 {
 				fmt.Printf("%s: %v escapes to heap:\n", pos, src.n)
 			}
 			explanation := b.explainFlow(pos, dst, src, k.derefs, k.notes, []*logopt.LoggedOpt{})
 			if logopt.Enabled() {
 				var e_curfn *ir.Func // TODO(mdempsky): Fix.
 				logopt.LogOpt(src.n.Pos(), "escapes", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", src.n), explanation)
 			}

 		}
 		src.escapes = true
 		return
 	}

 	// TODO(mdempsky): Deduplicate edges?
 	dst.edges = append(dst.edges, edge{src: src, derefs: k.derefs, notes: k.notes})
 }

 func (b *batch) heapHole() hole    { return b.heapLoc.asHole() }
 func (b *batch) discardHole() hole { return b.blankLoc.asHole() }

 func (b *batch) oldLoc(n *ir.Name) *location {
 	if n.Canonical().Opt == nil {
 		base.Fatalf("%v has no location", n)
 	}
 	return n.Canonical().Opt.(*location)
 }

 func (e *escape) newLoc(n ir.Node, transient bool) *location {
 	if e.curfn == nil {
 		base.Fatalf("e.curfn isn't set")
 	}
 	if n != nil && n.Type() != nil && n.Type().NotInHeap() {
 		base.ErrorfAt(n.Pos(), 0, "%v is incomplete (or unallocatable); stack allocation disallowed", n.Type())
 	}

 	if n != nil && n.Op() == ir.ONAME {
 		if canon := n.(*ir.Name).Canonical(); n != canon {
 			base.Fatalf("newLoc on non-canonical %v (canonical is %v)", n, canon)
 		}
 	}
 	loc := &location{
 		n:         n,
 		curfn:     e.curfn,
 		loopDepth: e.loopDepth,
 		transient: transient,
 	}
 	e.allLocs = append(e.allLocs, loc)
 	if n != nil {
 		if n.Op() == ir.ONAME {
 			n := n.(*ir.Name)
 			if n.Class == ir.PPARAM && n.Curfn == nil {
 				// ok; hidden parameter
 			} else if n.Curfn != e.curfn {
 				base.Fatalf("curfn mismatch: %v != %v for %v", n.Curfn, e.curfn, n)
 			}

 			if n.Opt != nil {
 				base.Fatalf("%v already has a location", n)
 			}
 			n.Opt = loc
 		}
 	}
 	return loc
 }

 // teeHole returns a new hole that flows into each hole of ks,
 // similar to the Unix tee(1) command.
 func (e *escape) teeHole(ks ...hole) hole {
 	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 {
 			base.Fatalf("teeHole: negative derefs")
 		}

 		e.flow(k, loc)
 	}
 	return loc.asHole()
 }

 // later returns a new hole that flows into k, but some time later.
 // Its main effect is to prevent immediate reuse of temporary
 // variables introduced during Order.
 func (e *escape) later(k hole) hole {
 	loc := e.newLoc(nil, false)
 	e.flow(k, loc)
 	return loc.asHole()
 }

 // Fmt is called from node printing to print information about escape analysis results.
 func Fmt(n ir.Node) string {
 	text := ""
 	switch n.Esc() {
 	case ir.EscUnknown:
 		break

 	case ir.EscHeap:
 		text = "esc(h)"

 	case ir.EscNone:
 		text = "esc(no)"

 	case ir.EscNever:
 		text = "esc(N)"

 	default:
 		text = fmt.Sprintf("esc(%d)", n.Esc())
 	}

 	if n.Op() == ir.ONAME {
 		n := n.(*ir.Name)
 		if loc, ok := n.Opt.(*location); ok && loc.loopDepth != 0 {
 			if text != "" {
 				text += " "
 			}
 			text += fmt.Sprintf("ld(%d)", loc.loopDepth)
 		}
 	}

 	return text
 }
	// 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 escape

	import (
	"cmd/compile/internal/base"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/logopt"
	"cmd/compile/internal/types"
	"fmt"
	)

	// 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)
	// }

	// An location represents an abstract location that stores a Go
	// variable.
	type location struct {
	n ir.Node // represented variable or expression, if any
	curfn *ir.Func // enclosing function
	edges []edge // incoming edges
	loopDepth int // loopDepth at declaration

	// resultIndex records the tuple index (starting at 1) for
	// PPARAMOUT variables within their function's result type.
	// For non-PPARAMOUT variables it's 0.
	resultIndex int

	// derefs and walkgen are used during walkOne to track the
	// minimal dereferences from the walk root.
	derefs int // >= -1
	walkgen uint32

	// dst and dstEdgeindex track the next immediate assignment
	// destination location during walkone, along with the index
	// of the edge pointing back to this location.
	dst *location
	dstEdgeIdx int

	// queued is used by walkAll to track whether this location is
	// in the walk queue.
	queued bool

	// 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 leak set.
	paramEsc leaks

	captured bool // has a closure captured this variable?
	reassigned bool // has this variable been reassigned?
	addrtaken bool // has this variable's address been taken?
	}

	// An edge represents an assignment edge between two Go variables.
	type edge struct {
	src *location
	derefs int // >= -1
	notes *note
	}

	func (l *location) asHole() hole {
	return hole{dst: l}
	}

	// leak records that parameter l leaks to sink.
	func (l location) leakTo(sink location, derefs int) {
	// If sink is a result parameter that doesn't escape (#44614)
	// and we can fit return bits into the escape analysis tag,
	// then record as a result leak.
	if !sink.escapes && sink.isName(ir.PPARAMOUT) && sink.curfn == l.curfn {
	ri := sink.resultIndex - 1
	if ri < numEscResults {
	// Leak to result parameter.
	l.paramEsc.AddResult(ri, derefs)
	return
	}
	}

	// Otherwise, record as heap leak.
	l.paramEsc.AddHeap(derefs)
	}

	func (l *location) isName(c ir.Class) bool {
	return l.n != nil && l.n.Op() == ir.ONAME && l.n.(*ir.Name).Class == c
	}

	// A hole represents a context for evaluation of a Go
	// expression. E.g., when evaluating p in "x = **p", we'd have a hole
	// with dst==x and derefs==2.
	type hole struct {
	dst *location
	derefs int // >= -1
	notes *note

	// addrtaken indicates whether this context is taking the address of
	// the expression, independent of whether the address will actually
	// be stored into a variable.
	addrtaken bool
	}

	type note struct {
	next *note
	where ir.Node
	why string
	}

	func (k hole) note(where ir.Node, why string) hole {
	if where == nil \|\| why == "" {
	base.Fatalf("note: missing where/why")
	}
	if base.Flag.LowerM >= 2 \|\| logopt.Enabled() {
	k.notes = &note{
	next: k.notes,
	where: where,
	why: why,
	}
	}
	return k
	}

	func (k hole) shift(delta int) hole {
	k.derefs += delta
	if k.derefs < -1 {
	base.Fatalf("derefs underflow: %v", k.derefs)
	}
	k.addrtaken = delta < 0
	return k
	}

	func (k hole) deref(where ir.Node, why string) hole { return k.shift(1).note(where, why) }
	func (k hole) addr(where ir.Node, why string) hole { return k.shift(-1).note(where, why) }

	func (k hole) dotType(t *types.Type, where ir.Node, why string) hole {
	if !t.IsInterface() && !types.IsDirectIface(t) {
	k = k.shift(1)
	}
	return k.note(where, why)
	}

	func (b batch) flow(k hole, src location) {
	if k.addrtaken {
	src.addrtaken = true
	}

	dst := k.dst
	if dst == &b.blankLoc {
	return
	}
	if dst == src && k.derefs >= 0 { // dst = dst, dst = *dst, ...
	return
	}
	if dst.escapes && k.derefs < 0 { // dst = &src
	if base.Flag.LowerM >= 2 \|\| logopt.Enabled() {
	pos := base.FmtPos(src.n.Pos())
	if base.Flag.LowerM >= 2 {
	fmt.Printf("%s: %v escapes to heap:\n", pos, src.n)
	}
	explanation := b.explainFlow(pos, dst, src, k.derefs, k.notes, []*logopt.LoggedOpt{})
	if logopt.Enabled() {
	var e_curfn *ir.Func // TODO(mdempsky): Fix.
	logopt.LogOpt(src.n.Pos(), "escapes", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", src.n), explanation)
	}

	}
	src.escapes = true
	return
	}

	// TODO(mdempsky): Deduplicate edges?
	dst.edges = append(dst.edges, edge{src: src, derefs: k.derefs, notes: k.notes})
	}

	func (b *batch) heapHole() hole { return b.heapLoc.asHole() }
	func (b *batch) discardHole() hole { return b.blankLoc.asHole() }

	func (b batch) oldLoc(n ir.Name) *location {
	if n.Canonical().Opt == nil {
	base.Fatalf("%v has no location", n)
	}
	return n.Canonical().Opt.(*location)
	}

	func (e escape) newLoc(n ir.Node, transient bool) location {
	if e.curfn == nil {
	base.Fatalf("e.curfn isn't set")
	}
	if n != nil && n.Type() != nil && n.Type().NotInHeap() {
	base.ErrorfAt(n.Pos(), 0, "%v is incomplete (or unallocatable); stack allocation disallowed", n.Type())
	}

	if n != nil && n.Op() == ir.ONAME {
	if canon := n.(*ir.Name).Canonical(); n != canon {
	base.Fatalf("newLoc on non-canonical %v (canonical is %v)", n, canon)
	}
	}
	loc := &location{
	n: n,
	curfn: e.curfn,
	loopDepth: e.loopDepth,
	transient: transient,
	}
	e.allLocs = append(e.allLocs, loc)
	if n != nil {
	if n.Op() == ir.ONAME {
	n := n.(*ir.Name)
	if n.Class == ir.PPARAM && n.Curfn == nil {
	// ok; hidden parameter
	} else if n.Curfn != e.curfn {
	base.Fatalf("curfn mismatch: %v != %v for %v", n.Curfn, e.curfn, n)
	}

	if n.Opt != nil {
	base.Fatalf("%v already has a location", n)
	}
	n.Opt = loc
	}
	}
	return loc
	}

	// teeHole returns a new hole that flows into each hole of ks,
	// similar to the Unix tee(1) command.
	func (e *escape) teeHole(ks ...hole) hole {
	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 {
	base.Fatalf("teeHole: negative derefs")
	}

	e.flow(k, loc)
	}
	return loc.asHole()
	}

	// later returns a new hole that flows into k, but some time later.
	// Its main effect is to prevent immediate reuse of temporary
	// variables introduced during Order.
	func (e *escape) later(k hole) hole {
	loc := e.newLoc(nil, false)
	e.flow(k, loc)
	return loc.asHole()
	}

	// Fmt is called from node printing to print information about escape analysis results.
	func Fmt(n ir.Node) string {
	text := ""
	switch n.Esc() {
	case ir.EscUnknown:
	break

	case ir.EscHeap:
	text = "esc(h)"

	case ir.EscNone:
	text = "esc(no)"

	case ir.EscNever:
	text = "esc(N)"

	default:
	text = fmt.Sprintf("esc(%d)", n.Esc())
	}

	if n.Op() == ir.ONAME {
	n := n.(*ir.Name)
	if loc, ok := n.Opt.(*location); ok && loc.loopDepth != 0 {
	if text != "" {
	text += " "
	}
	text += fmt.Sprintf("ld(%d)", loc.loopDepth)
	}
	}

	return text
	}