solve.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/internal/src"
    12  	"fmt"
    13  	"strings"
    14  )
    15  
    16  // walkAll computes the minimal dereferences between all pairs of
    17  // locations.
    18  func (b *batch) walkAll() {
    19  	// We use a work queue to keep track of locations that we need
    20  	// to visit, and repeatedly walk until we reach a fixed point.
    21  	//
    22  	// We walk once from each location (including the heap), and
    23  	// then re-enqueue each location on its transition from
    24  	// transient->!transient and !escapes->escapes, which can each
    25  	// happen at most once. So we take Θ(len(e.allLocs)) walks.
    26  
    27  	// LIFO queue, has enough room for e.allLocs and e.heapLoc.
    28  	todo := make([]*location, 0, len(b.allLocs)+1)
    29  	enqueue := func(loc *location) {
    30  		if !loc.queued {
    31  			todo = append(todo, loc)
    32  			loc.queued = true
    33  		}
    34  	}
    35  
    36  	for _, loc := range b.allLocs {
    37  		enqueue(loc)
    38  	}
    39  	enqueue(&b.heapLoc)
    40  
    41  	var walkgen uint32
    42  	for len(todo) > 0 {
    43  		root := todo[len(todo)-1]
    44  		todo = todo[:len(todo)-1]
    45  		root.queued = false
    46  
    47  		walkgen++
    48  		b.walkOne(root, walkgen, enqueue)
    49  	}
    50  }
    51  
    52  // walkOne computes the minimal number of dereferences from root to
    53  // all other locations.
    54  func (b *batch) walkOne(root *location, walkgen uint32, enqueue func(*location)) {
    55  	// The data flow graph has negative edges (from addressing
    56  	// operations), so we use the Bellman-Ford algorithm. However,
    57  	// we don't have to worry about infinite negative cycles since
    58  	// we bound intermediate dereference counts to 0.
    59  
    60  	root.walkgen = walkgen
    61  	root.derefs = 0
    62  	root.dst = nil
    63  
    64  	todo := []*location{root} // LIFO queue
    65  	for len(todo) > 0 {
    66  		l := todo[len(todo)-1]
    67  		todo = todo[:len(todo)-1]
    68  
    69  		derefs := l.derefs
    70  
    71  		// If l.derefs < 0, then l's address flows to root.
    72  		addressOf := derefs < 0
    73  		if addressOf {
    74  			// For a flow path like "root = &l; l = x",
    75  			// l's address flows to root, but x's does
    76  			// not. We recognize this by lower bounding
    77  			// derefs at 0.
    78  			derefs = 0
    79  
    80  			// If l's address flows to a non-transient
    81  			// location, then l can't be transiently
    82  			// allocated.
    83  			if !root.transient && l.transient {
    84  				l.transient = false
    85  				enqueue(l)
    86  			}
    87  		}
    88  
    89  		if b.outlives(root, l) {
    90  			// l's value flows to root. If l is a function
    91  			// parameter and root is the heap or a
    92  			// corresponding result parameter, then record
    93  			// that value flow for tagging the function
    94  			// later.
    95  			if l.isName(ir.PPARAM) {
    96  				if (logopt.Enabled() || base.Flag.LowerM >= 2) && !l.escapes {
    97  					if base.Flag.LowerM >= 2 {
    98  						fmt.Printf("%s: parameter %v leaks to %s with derefs=%d:\n", base.FmtPos(l.n.Pos()), l.n, b.explainLoc(root), derefs)
    99  					}
   100  					explanation := b.explainPath(root, l)
   101  					if logopt.Enabled() {
   102  						var e_curfn *ir.Func // TODO(mdempsky): Fix.
   103  						logopt.LogOpt(l.n.Pos(), "leak", "escape", ir.FuncName(e_curfn),
   104  							fmt.Sprintf("parameter %v leaks to %s with derefs=%d", l.n, b.explainLoc(root), derefs), explanation)
   105  					}
   106  				}
   107  				l.leakTo(root, derefs)
   108  			}
   109  
   110  			// If l's address flows somewhere that
   111  			// outlives it, then l needs to be heap
   112  			// allocated.
   113  			if addressOf && !l.escapes {
   114  				if logopt.Enabled() || base.Flag.LowerM >= 2 {
   115  					if base.Flag.LowerM >= 2 {
   116  						fmt.Printf("%s: %v escapes to heap:\n", base.FmtPos(l.n.Pos()), l.n)
   117  					}
   118  					explanation := b.explainPath(root, l)
   119  					if logopt.Enabled() {
   120  						var e_curfn *ir.Func // TODO(mdempsky): Fix.
   121  						logopt.LogOpt(l.n.Pos(), "escape", "escape", ir.FuncName(e_curfn), fmt.Sprintf("%v escapes to heap", l.n), explanation)
   122  					}
   123  				}
   124  				l.escapes = true
   125  				enqueue(l)
   126  				continue
   127  			}
   128  		}
   129  
   130  		for i, edge := range l.edges {
   131  			if edge.src.escapes {
   132  				continue
   133  			}
   134  			d := derefs + edge.derefs
   135  			if edge.src.walkgen != walkgen || edge.src.derefs > d {
   136  				edge.src.walkgen = walkgen
   137  				edge.src.derefs = d
   138  				edge.src.dst = l
   139  				edge.src.dstEdgeIdx = i
   140  				todo = append(todo, edge.src)
   141  			}
   142  		}
   143  	}
   144  }
   145  
   146  // explainPath prints an explanation of how src flows to the walk root.
   147  func (b *batch) explainPath(root, src *location) []*logopt.LoggedOpt {
   148  	visited := make(map[*location]bool)
   149  	pos := base.FmtPos(src.n.Pos())
   150  	var explanation []*logopt.LoggedOpt
   151  	for {
   152  		// Prevent infinite loop.
   153  		if visited[src] {
   154  			if base.Flag.LowerM >= 2 {
   155  				fmt.Printf("%s:   warning: truncated explanation due to assignment cycle; see golang.org/issue/35518\n", pos)
   156  			}
   157  			break
   158  		}
   159  		visited[src] = true
   160  		dst := src.dst
   161  		edge := &dst.edges[src.dstEdgeIdx]
   162  		if edge.src != src {
   163  			base.Fatalf("path inconsistency: %v != %v", edge.src, src)
   164  		}
   165  
   166  		explanation = b.explainFlow(pos, dst, src, edge.derefs, edge.notes, explanation)
   167  
   168  		if dst == root {
   169  			break
   170  		}
   171  		src = dst
   172  	}
   173  
   174  	return explanation
   175  }
   176  
   177  func (b *batch) explainFlow(pos string, dst, srcloc *location, derefs int, notes *note, explanation []*logopt.LoggedOpt) []*logopt.LoggedOpt {
   178  	ops := "&"
   179  	if derefs >= 0 {
   180  		ops = strings.Repeat("*", derefs)
   181  	}
   182  	print := base.Flag.LowerM >= 2
   183  
   184  	flow := fmt.Sprintf("   flow: %s = %s%v:", b.explainLoc(dst), ops, b.explainLoc(srcloc))
   185  	if print {
   186  		fmt.Printf("%s:%s\n", pos, flow)
   187  	}
   188  	if logopt.Enabled() {
   189  		var epos src.XPos
   190  		if notes != nil {
   191  			epos = notes.where.Pos()
   192  		} else if srcloc != nil && srcloc.n != nil {
   193  			epos = srcloc.n.Pos()
   194  		}
   195  		var e_curfn *ir.Func // TODO(mdempsky): Fix.
   196  		explanation = append(explanation, logopt.NewLoggedOpt(epos, "escflow", "escape", ir.FuncName(e_curfn), flow))
   197  	}
   198  
   199  	for note := notes; note != nil; note = note.next {
   200  		if print {
   201  			fmt.Printf("%s:     from %v (%v) at %s\n", pos, note.where, note.why, base.FmtPos(note.where.Pos()))
   202  		}
   203  		if logopt.Enabled() {
   204  			var e_curfn *ir.Func // TODO(mdempsky): Fix.
   205  			explanation = append(explanation, logopt.NewLoggedOpt(note.where.Pos(), "escflow", "escape", ir.FuncName(e_curfn),
   206  				fmt.Sprintf("     from %v (%v)", note.where, note.why)))
   207  		}
   208  	}
   209  	return explanation
   210  }
   211  
   212  func (b *batch) explainLoc(l *location) string {
   213  	if l == &b.heapLoc {
   214  		return "{heap}"
   215  	}
   216  	if l.n == nil {
   217  		// TODO(mdempsky): Omit entirely.
   218  		return "{temp}"
   219  	}
   220  	if l.n.Op() == ir.ONAME {
   221  		return fmt.Sprintf("%v", l.n)
   222  	}
   223  	return fmt.Sprintf("{storage for %v}", l.n)
   224  }
   225  
   226  // outlives reports whether values stored in l may survive beyond
   227  // other's lifetime if stack allocated.
   228  func (b *batch) outlives(l, other *location) bool {
   229  	// The heap outlives everything.
   230  	if l.escapes {
   231  		return true
   232  	}
   233  
   234  	// We don't know what callers do with returned values, so
   235  	// pessimistically we need to assume they flow to the heap and
   236  	// outlive everything too.
   237  	if l.isName(ir.PPARAMOUT) {
   238  		// Exception: Directly called closures can return
   239  		// locations allocated outside of them without forcing
   240  		// them to the heap. For example:
   241  		//
   242  		//    var u int  // okay to stack allocate
   243  		//    *(func() *int { return &u }()) = 42
   244  		if containsClosure(other.curfn, l.curfn) && l.curfn.ClosureCalled() {
   245  			return false
   246  		}
   247  
   248  		return true
   249  	}
   250  
   251  	// If l and other are within the same function, then l
   252  	// outlives other if it was declared outside other's loop
   253  	// scope. For example:
   254  	//
   255  	//    var l *int
   256  	//    for {
   257  	//        l = new(int)
   258  	//    }
   259  	if l.curfn == other.curfn && l.loopDepth < other.loopDepth {
   260  		return true
   261  	}
   262  
   263  	// If other is declared within a child closure of where l is
   264  	// declared, then l outlives it. For example:
   265  	//
   266  	//    var l *int
   267  	//    func() {
   268  	//        l = new(int)
   269  	//    }
   270  	if containsClosure(l.curfn, other.curfn) {
   271  		return true
   272  	}
   273  
   274  	return false
   275  }
   276  
   277  // containsClosure reports whether c is a closure contained within f.
   278  func containsClosure(f, c *ir.Func) bool {
   279  	// Common case.
   280  	if f == c {
   281  		return false
   282  	}
   283  
   284  	// Closures within function Foo are named like "Foo.funcN..."
   285  	// TODO(mdempsky): Better way to recognize this.
   286  	fn := f.Sym().Name
   287  	cn := c.Sym().Name
   288  	return len(cn) > len(fn) && cn[:len(fn)] == fn && cn[len(fn)] == '.'
   289  }
   290
View as plain text