graph.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  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/logopt"
    11  	"cmd/compile/internal/types"
    12  	"fmt"
    13  )
    14  
    15  // Below we implement the methods for walking the AST and recording
    16  // data flow edges. Note that because a sub-expression might have
    17  // side-effects, it's important to always visit the entire AST.
    18  //
    19  // For example, write either:
    20  //
    21  //     if x {
    22  //         e.discard(n.Left)
    23  //     } else {
    24  //         e.value(k, n.Left)
    25  //     }
    26  //
    27  // or
    28  //
    29  //     if x {
    30  //         k = e.discardHole()
    31  //     }
    32  //     e.value(k, n.Left)
    33  //
    34  // Do NOT write:
    35  //
    36  //    // BAD: possibly loses side-effects within n.Left
    37  //    if !x {
    38  //        e.value(k, n.Left)
    39  //    }
    40  
    41  // A location represents an abstract location that stores a Go
    42  // variable.
    43  type location struct {
    44  	n         ir.Node  // represented variable or expression, if any
    45  	curfn     *ir.Func // enclosing function
    46  	edges     []edge   // incoming edges
    47  	loopDepth int      // loopDepth at declaration
    48  
    49  	// resultIndex records the tuple index (starting at 1) for
    50  	// PPARAMOUT variables within their function's result type.
    51  	// For non-PPARAMOUT variables it's 0.
    52  	resultIndex int
    53  
    54  	// derefs and walkgen are used during walkOne to track the
    55  	// minimal dereferences from the walk root.
    56  	derefs  int // >= -1
    57  	walkgen uint32
    58  
    59  	// dst and dstEdgeindex track the next immediate assignment
    60  	// destination location during walkone, along with the index
    61  	// of the edge pointing back to this location.
    62  	dst        *location
    63  	dstEdgeIdx int
    64  
    65  	// queuedWalkAll is used by walkAll to track whether this location is
    66  	// in its work queue.
    67  	queuedWalkAll bool
    68  
    69  	// queuedWalkOne is used by walkOne to track whether this location is
    70  	// in its work queue. The value is the walkgen when this location was
    71  	// last queued for walkOne, or 0 if it's not currently queued.
    72  	queuedWalkOne uint32
    73  
    74  	// attrs is a bitset of location attributes.
    75  	attrs locAttr
    76  
    77  	// paramEsc records the represented parameter's leak set.
    78  	paramEsc leaks
    79  
    80  	captured   bool // has a closure captured this variable?
    81  	reassigned bool // has this variable been reassigned?
    82  	addrtaken  bool // has this variable's address been taken?
    83  	param      bool // is this variable a parameter (ONAME of class ir.PPARAM)?
    84  	paramOut   bool // is this variable an out parameter (ONAME of class ir.PPARAMOUT)?
    85  }
    86  
    87  type locAttr uint8
    88  
    89  const (
    90  	// attrEscapes indicates whether the represented variable's address
    91  	// escapes; that is, whether the variable must be heap allocated.
    92  	attrEscapes locAttr = 1 << iota
    93  
    94  	// attrPersists indicates whether the represented expression's
    95  	// address outlives the statement; that is, whether its storage
    96  	// cannot be immediately reused.
    97  	attrPersists
    98  
    99  	// attrMutates indicates whether pointers that are reachable from
   100  	// this location may have their addressed memory mutated. This is
   101  	// used to detect string->[]byte conversions that can be safely
   102  	// optimized away.
   103  	attrMutates
   104  
   105  	// attrCalls indicates whether closures that are reachable from this
   106  	// location may be called without tracking their results. This is
   107  	// used to better optimize indirect closure calls.
   108  	attrCalls
   109  )
   110  
   111  func (l *location) hasAttr(attr locAttr) bool { return l.attrs&attr != 0 }
   112  
   113  // An edge represents an assignment edge between two Go variables.
   114  type edge struct {
   115  	src    *location
   116  	derefs int // >= -1
   117  	notes  *note
   118  }
   119  
   120  func (l *location) asHole() hole {
   121  	return hole{dst: l}
   122  }
   123  
   124  // leak records that parameter l leaks to sink.
   125  func (l *location) leakTo(sink *location, derefs int) {
   126  	// If sink is a result parameter that doesn't escape (#44614)
   127  	// and we can fit return bits into the escape analysis tag,
   128  	// then record as a result leak.
   129  	if !sink.hasAttr(attrEscapes) && sink.isName(ir.PPARAMOUT) && sink.curfn == l.curfn {
   130  		ri := sink.resultIndex - 1
   131  		if ri < numEscResults {
   132  			// Leak to result parameter.
   133  			l.paramEsc.AddResult(ri, derefs)
   134  			return
   135  		}
   136  	}
   137  
   138  	// Otherwise, record as heap leak.
   139  	l.paramEsc.AddHeap(derefs)
   140  }
   141  
   142  func (l *location) isName(c ir.Class) bool {
   143  	return l.n != nil && l.n.Op() == ir.ONAME && l.n.(*ir.Name).Class == c
   144  }
   145  
   146  // A hole represents a context for evaluation of a Go
   147  // expression. E.g., when evaluating p in "x = **p", we'd have a hole
   148  // with dst==x and derefs==2.
   149  type hole struct {
   150  	dst    *location
   151  	derefs int // >= -1
   152  	notes  *note
   153  
   154  	// addrtaken indicates whether this context is taking the address of
   155  	// the expression, independent of whether the address will actually
   156  	// be stored into a variable.
   157  	addrtaken bool
   158  }
   159  
   160  type note struct {
   161  	next  *note
   162  	where ir.Node
   163  	why   string
   164  }
   165  
   166  func (k hole) note(where ir.Node, why string) hole {
   167  	if where == nil || why == "" {
   168  		base.Fatalf("note: missing where/why")
   169  	}
   170  	if base.Flag.LowerM >= 2 || logopt.Enabled() {
   171  		k.notes = &note{
   172  			next:  k.notes,
   173  			where: where,
   174  			why:   why,
   175  		}
   176  	}
   177  	return k
   178  }
   179  
   180  func (k hole) shift(delta int) hole {
   181  	k.derefs += delta
   182  	if k.derefs < -1 {
   183  		base.Fatalf("derefs underflow: %v", k.derefs)
   184  	}
   185  	k.addrtaken = delta < 0
   186  	return k
   187  }
   188  
   189  func (k hole) deref(where ir.Node, why string) hole { return k.shift(1).note(where, why) }
   190  func (k hole) addr(where ir.Node, why string) hole  { return k.shift(-1).note(where, why) }
   191  
   192  func (k hole) dotType(t *types.Type, where ir.Node, why string) hole {
   193  	if !t.IsInterface() && !types.IsDirectIface(t) {
   194  		k = k.shift(1)
   195  	}
   196  	return k.note(where, why)
   197  }
   198  
   199  func (b *batch) flow(k hole, src *location) {
   200  	if k.addrtaken {
   201  		src.addrtaken = true
   202  	}
   203  
   204  	dst := k.dst
   205  	if dst == &b.blankLoc {
   206  		return
   207  	}
   208  	if dst == src && k.derefs >= 0 { // dst = dst, dst = *dst, ...
   209  		return
   210  	}
   211  	if dst.hasAttr(attrEscapes) && k.derefs < 0 { // dst = &src
   212  		if base.Flag.LowerM >= 2 || logopt.Enabled() {
   213  			pos := base.FmtPos(src.n.Pos())
   214  			if base.Flag.LowerM >= 2 {
   215  				fmt.Printf("%s: %v escapes to heap in %v:\n", pos, src.n, ir.FuncName(src.curfn))
   216  			}
   217  			explanation := b.explainFlow(pos, dst, src, k.derefs, k.notes, []*logopt.LoggedOpt{})
   218  			if logopt.Enabled() {
   219  				var e_curfn *ir.Func // TODO(mdempsky): Fix.
   220  				logopt.LogOpt(src.n.Pos(), "escapes", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", src.n), explanation)
   221  			}
   222  
   223  		}
   224  		src.attrs |= attrEscapes | attrPersists | attrMutates | attrCalls
   225  		return
   226  	}
   227  
   228  	// TODO(mdempsky): Deduplicate edges?
   229  	dst.edges = append(dst.edges, edge{src: src, derefs: k.derefs, notes: k.notes})
   230  }
   231  
   232  func (b *batch) heapHole() hole    { return b.heapLoc.asHole() }
   233  func (b *batch) mutatorHole() hole { return b.mutatorLoc.asHole() }
   234  func (b *batch) calleeHole() hole  { return b.calleeLoc.asHole() }
   235  func (b *batch) discardHole() hole { return b.blankLoc.asHole() }
   236  
   237  func (b *batch) oldLoc(n *ir.Name) *location {
   238  	if n.Canonical().Opt == nil {
   239  		base.FatalfAt(n.Pos(), "%v has no location", n)
   240  	}
   241  	return n.Canonical().Opt.(*location)
   242  }
   243  
   244  func (e *escape) newLoc(n ir.Node, persists bool) *location {
   245  	if e.curfn == nil {
   246  		base.Fatalf("e.curfn isn't set")
   247  	}
   248  	if n != nil && n.Type() != nil && n.Type().NotInHeap() {
   249  		base.ErrorfAt(n.Pos(), 0, "%v is incomplete (or unallocatable); stack allocation disallowed", n.Type())
   250  	}
   251  
   252  	if n != nil && n.Op() == ir.ONAME {
   253  		if canon := n.(*ir.Name).Canonical(); n != canon {
   254  			base.FatalfAt(n.Pos(), "newLoc on non-canonical %v (canonical is %v)", n, canon)
   255  		}
   256  	}
   257  	loc := &location{
   258  		n:         n,
   259  		curfn:     e.curfn,
   260  		loopDepth: e.loopDepth,
   261  	}
   262  	if loc.isName(ir.PPARAM) {
   263  		loc.param = true
   264  	} else if loc.isName(ir.PPARAMOUT) {
   265  		loc.paramOut = true
   266  	}
   267  
   268  	if persists {
   269  		loc.attrs |= attrPersists
   270  	}
   271  	e.allLocs = append(e.allLocs, loc)
   272  	if n != nil {
   273  		if n.Op() == ir.ONAME {
   274  			n := n.(*ir.Name)
   275  			if n.Class == ir.PPARAM && n.Curfn == nil {
   276  				// ok; hidden parameter
   277  			} else if n.Curfn != e.curfn {
   278  				base.FatalfAt(n.Pos(), "curfn mismatch: %v != %v for %v", n.Curfn, e.curfn, n)
   279  			}
   280  
   281  			if n.Opt != nil {
   282  				base.FatalfAt(n.Pos(), "%v already has a location", n)
   283  			}
   284  			n.Opt = loc
   285  		}
   286  	}
   287  	return loc
   288  }
   289  
   290  // teeHole returns a new hole that flows into each hole of ks,
   291  // similar to the Unix tee(1) command.
   292  func (e *escape) teeHole(ks ...hole) hole {
   293  	if len(ks) == 0 {
   294  		return e.discardHole()
   295  	}
   296  	if len(ks) == 1 {
   297  		return ks[0]
   298  	}
   299  	// TODO(mdempsky): Optimize if there's only one non-discard hole?
   300  
   301  	// Given holes "l1 = _", "l2 = **_", "l3 = *_", ..., create a
   302  	// new temporary location ltmp, wire it into place, and return
   303  	// a hole for "ltmp = _".
   304  	loc := e.newLoc(nil, false)
   305  	for _, k := range ks {
   306  		// N.B., "p = &q" and "p = &tmp; tmp = q" are not
   307  		// semantically equivalent. To combine holes like "l1
   308  		// = _" and "l2 = &_", we'd need to wire them as "l1 =
   309  		// *ltmp" and "l2 = ltmp" and return "ltmp = &_"
   310  		// instead.
   311  		if k.derefs < 0 {
   312  			base.Fatalf("teeHole: negative derefs")
   313  		}
   314  
   315  		e.flow(k, loc)
   316  	}
   317  	return loc.asHole()
   318  }
   319  
   320  // later returns a new hole that flows into k, but some time later.
   321  // Its main effect is to prevent immediate reuse of temporary
   322  // variables introduced during Order.
   323  func (e *escape) later(k hole) hole {
   324  	loc := e.newLoc(nil, true)
   325  	e.flow(k, loc)
   326  	return loc.asHole()
   327  }
   328  
   329  // Fmt is called from node printing to print information about escape analysis results.
   330  func Fmt(n ir.Node) string {
   331  	text := ""
   332  	switch n.Esc() {
   333  	case ir.EscUnknown:
   334  		break
   335  
   336  	case ir.EscHeap:
   337  		text = "esc(h)"
   338  
   339  	case ir.EscNone:
   340  		text = "esc(no)"
   341  
   342  	case ir.EscNever:
   343  		text = "esc(N)"
   344  
   345  	default:
   346  		text = fmt.Sprintf("esc(%d)", n.Esc())
   347  	}
   348  
   349  	if n.Op() == ir.ONAME {
   350  		n := n.(*ir.Name)
   351  		if loc, ok := n.Opt.(*location); ok && loc.loopDepth != 0 {
   352  			if text != "" {
   353  				text += " "
   354  			}
   355  			text += fmt.Sprintf("ld(%d)", loc.loopDepth)
   356  		}
   357  	}
   358  
   359  	return text
   360  }
   361
View as plain text