solve.go

Documentation: golang.org/x/tools/go/pointer

     1  // Copyright 2013 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 pointer
     6  
     7  // This file defines a naive Andersen-style solver for the inclusion
     8  // constraint system.
     9  
    10  import (
    11  	"fmt"
    12  	"go/types"
    13  )
    14  
    15  type solverState struct {
    16  	complex []constraint // complex constraints attached to this node
    17  	copyTo  nodeset      // simple copy constraint edges
    18  	pts     nodeset      // points-to set of this node
    19  	prevPTS nodeset      // pts(n) in previous iteration (for difference propagation)
    20  }
    21  
    22  func (a *analysis) solve() {
    23  	start("Solving")
    24  	if a.log != nil {
    25  		fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
    26  	}
    27  
    28  	// Solver main loop.
    29  	var delta nodeset
    30  	for {
    31  		// Add new constraints to the graph:
    32  		// static constraints from SSA on round 1,
    33  		// dynamic constraints from reflection thereafter.
    34  		a.processNewConstraints()
    35  
    36  		var x int
    37  		if !a.work.TakeMin(&x) {
    38  			break // empty
    39  		}
    40  		id := nodeid(x)
    41  		if a.log != nil {
    42  			fmt.Fprintf(a.log, "\tnode n%d\n", id)
    43  		}
    44  
    45  		n := a.nodes[id]
    46  
    47  		// Difference propagation.
    48  		delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
    49  		if delta.IsEmpty() {
    50  			continue
    51  		}
    52  		if a.log != nil {
    53  			fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
    54  				id, n.typ, &delta, &n.solve.prevPTS)
    55  		}
    56  		n.solve.prevPTS.Copy(&n.solve.pts.Sparse)
    57  
    58  		// Apply all resolution rules attached to n.
    59  		a.solveConstraints(n, &delta)
    60  
    61  		if a.log != nil {
    62  			fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
    63  		}
    64  	}
    65  
    66  	if !a.nodes[0].solve.pts.IsEmpty() {
    67  		panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
    68  	}
    69  
    70  	// Release working state (but keep final PTS).
    71  	for _, n := range a.nodes {
    72  		n.solve.complex = nil
    73  		n.solve.copyTo.Clear()
    74  		n.solve.prevPTS.Clear()
    75  	}
    76  
    77  	if a.log != nil {
    78  		fmt.Fprintf(a.log, "Solver done\n")
    79  
    80  		// Dump solution.
    81  		for i, n := range a.nodes {
    82  			if !n.solve.pts.IsEmpty() {
    83  				fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, &n.solve.pts, n.typ)
    84  			}
    85  		}
    86  	}
    87  	stop("Solving")
    88  }
    89  
    90  // processNewConstraints takes the new constraints from a.constraints
    91  // and adds them to the graph, ensuring
    92  // that new constraints are applied to pre-existing labels and
    93  // that pre-existing constraints are applied to new labels.
    94  func (a *analysis) processNewConstraints() {
    95  	// Take the slice of new constraints.
    96  	// (May grow during call to solveConstraints.)
    97  	constraints := a.constraints
    98  	a.constraints = nil
    99  
   100  	// Initialize points-to sets from addr-of (base) constraints.
   101  	for _, c := range constraints {
   102  		if c, ok := c.(*addrConstraint); ok {
   103  			dst := a.nodes[c.dst]
   104  			dst.solve.pts.add(c.src)
   105  
   106  			// Populate the worklist with nodes that point to
   107  			// something initially (due to addrConstraints) and
   108  			// have other constraints attached.
   109  			// (A no-op in round 1.)
   110  			if !dst.solve.copyTo.IsEmpty() || len(dst.solve.complex) > 0 {
   111  				a.addWork(c.dst)
   112  			}
   113  		}
   114  	}
   115  
   116  	// Attach simple (copy) and complex constraints to nodes.
   117  	var stale nodeset
   118  	for _, c := range constraints {
   119  		var id nodeid
   120  		switch c := c.(type) {
   121  		case *addrConstraint:
   122  			// base constraints handled in previous loop
   123  			continue
   124  		case *copyConstraint:
   125  			// simple (copy) constraint
   126  			id = c.src
   127  			a.nodes[id].solve.copyTo.add(c.dst)
   128  		default:
   129  			// complex constraint
   130  			id = c.ptr()
   131  			solve := a.nodes[id].solve
   132  			solve.complex = append(solve.complex, c)
   133  		}
   134  
   135  		if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
   136  			if !n.solve.prevPTS.IsEmpty() {
   137  				stale.add(id)
   138  			}
   139  			a.addWork(id)
   140  		}
   141  	}
   142  	// Apply new constraints to pre-existing PTS labels.
   143  	var space [50]int
   144  	for _, id := range stale.AppendTo(space[:0]) {
   145  		n := a.nodes[nodeid(id)]
   146  		a.solveConstraints(n, &n.solve.prevPTS)
   147  	}
   148  }
   149  
   150  // solveConstraints applies each resolution rule attached to node n to
   151  // the set of labels delta.  It may generate new constraints in
   152  // a.constraints.
   153  func (a *analysis) solveConstraints(n *node, delta *nodeset) {
   154  	if delta.IsEmpty() {
   155  		return
   156  	}
   157  
   158  	// Process complex constraints dependent on n.
   159  	for _, c := range n.solve.complex {
   160  		if a.log != nil {
   161  			fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
   162  		}
   163  		c.solve(a, delta)
   164  	}
   165  
   166  	// Process copy constraints.
   167  	var copySeen nodeset
   168  	for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
   169  		mid := nodeid(x)
   170  		if copySeen.add(mid) {
   171  			if a.nodes[mid].solve.pts.addAll(delta) {
   172  				a.addWork(mid)
   173  			}
   174  		}
   175  	}
   176  }
   177  
   178  // addLabel adds label to the points-to set of ptr and reports whether the set grew.
   179  func (a *analysis) addLabel(ptr, label nodeid) bool {
   180  	b := a.nodes[ptr].solve.pts.add(label)
   181  	if b && a.log != nil {
   182  		fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
   183  	}
   184  	return b
   185  }
   186  
   187  func (a *analysis) addWork(id nodeid) {
   188  	a.work.Insert(int(id))
   189  	if a.log != nil {
   190  		fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
   191  	}
   192  }
   193  
   194  // onlineCopy adds a copy edge.  It is called online, i.e. during
   195  // solving, so it adds edges and pts members directly rather than by
   196  // instantiating a 'constraint'.
   197  //
   198  // The size of the copy is implicitly 1.
   199  // It returns true if pts(dst) changed.
   200  func (a *analysis) onlineCopy(dst, src nodeid) bool {
   201  	if dst != src {
   202  		if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
   203  			if a.log != nil {
   204  				fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
   205  			}
   206  			// TODO(adonovan): most calls to onlineCopy
   207  			// are followed by addWork, possibly batched
   208  			// via a 'changed' flag; see if there's a
   209  			// noticeable penalty to calling addWork here.
   210  			return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
   211  		}
   212  	}
   213  	return false
   214  }
   215  
   216  // Returns sizeof.
   217  // Implicitly adds nodes to worklist.
   218  //
   219  // TODO(adonovan): now that we support a.copy() during solving, we
   220  // could eliminate onlineCopyN, but it's much slower.  Investigate.
   221  func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
   222  	for i := uint32(0); i < sizeof; i++ {
   223  		if a.onlineCopy(dst, src) {
   224  			a.addWork(dst)
   225  		}
   226  		src++
   227  		dst++
   228  	}
   229  	return sizeof
   230  }
   231  
   232  func (c *loadConstraint) solve(a *analysis, delta *nodeset) {
   233  	var changed bool
   234  	for _, x := range delta.AppendTo(a.deltaSpace) {
   235  		k := nodeid(x)
   236  		koff := k + nodeid(c.offset)
   237  		if a.onlineCopy(c.dst, koff) {
   238  			changed = true
   239  		}
   240  	}
   241  	if changed {
   242  		a.addWork(c.dst)
   243  	}
   244  }
   245  
   246  func (c *storeConstraint) solve(a *analysis, delta *nodeset) {
   247  	for _, x := range delta.AppendTo(a.deltaSpace) {
   248  		k := nodeid(x)
   249  		koff := k + nodeid(c.offset)
   250  		if a.onlineCopy(koff, c.src) {
   251  			a.addWork(koff)
   252  		}
   253  	}
   254  }
   255  
   256  func (c *offsetAddrConstraint) solve(a *analysis, delta *nodeset) {
   257  	dst := a.nodes[c.dst]
   258  	for _, x := range delta.AppendTo(a.deltaSpace) {
   259  		k := nodeid(x)
   260  		if dst.solve.pts.add(k + nodeid(c.offset)) {
   261  			a.addWork(c.dst)
   262  		}
   263  	}
   264  }
   265  
   266  func (c *typeFilterConstraint) solve(a *analysis, delta *nodeset) {
   267  	for _, x := range delta.AppendTo(a.deltaSpace) {
   268  		ifaceObj := nodeid(x)
   269  		tDyn, _, indirect := a.taggedValue(ifaceObj)
   270  		if indirect {
   271  			// TODO(adonovan): we'll need to implement this
   272  			// when we start creating indirect tagged objects.
   273  			panic("indirect tagged object")
   274  		}
   275  
   276  		if types.AssignableTo(tDyn, c.typ) {
   277  			if a.addLabel(c.dst, ifaceObj) {
   278  				a.addWork(c.dst)
   279  			}
   280  		}
   281  	}
   282  }
   283  
   284  func (c *untagConstraint) solve(a *analysis, delta *nodeset) {
   285  	predicate := types.AssignableTo
   286  	if c.exact {
   287  		predicate = types.Identical
   288  	}
   289  	for _, x := range delta.AppendTo(a.deltaSpace) {
   290  		ifaceObj := nodeid(x)
   291  		tDyn, v, indirect := a.taggedValue(ifaceObj)
   292  		if indirect {
   293  			// TODO(adonovan): we'll need to implement this
   294  			// when we start creating indirect tagged objects.
   295  			panic("indirect tagged object")
   296  		}
   297  
   298  		if predicate(tDyn, c.typ) {
   299  			// Copy payload sans tag to dst.
   300  			//
   301  			// TODO(adonovan): opt: if tDyn is
   302  			// nonpointerlike we can skip this entire
   303  			// constraint, perhaps.  We only care about
   304  			// pointers among the fields.
   305  			a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
   306  		}
   307  	}
   308  }
   309  
   310  func (c *invokeConstraint) solve(a *analysis, delta *nodeset) {
   311  	for _, x := range delta.AppendTo(a.deltaSpace) {
   312  		ifaceObj := nodeid(x)
   313  		tDyn, v, indirect := a.taggedValue(ifaceObj)
   314  		if indirect {
   315  			// TODO(adonovan): we may need to implement this if
   316  			// we ever apply invokeConstraints to reflect.Value PTSs,
   317  			// e.g. for (reflect.Value).Call.
   318  			panic("indirect tagged object")
   319  		}
   320  
   321  		// Look up the concrete method.
   322  		fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
   323  		if fn == nil {
   324  			panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
   325  		}
   326  		sig := fn.Signature
   327  
   328  		fnObj := a.globalobj[fn] // dynamic calls use shared contour
   329  		if fnObj == 0 {
   330  			// a.objectNode(fn) was not called during gen phase.
   331  			panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
   332  		}
   333  
   334  		// Make callsite's fn variable point to identity of
   335  		// concrete method.  (There's no need to add it to
   336  		// worklist since it never has attached constraints.)
   337  		a.addLabel(c.params, fnObj)
   338  
   339  		// Extract value and connect to method's receiver.
   340  		// Copy payload to method's receiver param (arg0).
   341  		arg0 := a.funcParams(fnObj)
   342  		recvSize := a.sizeof(sig.Recv().Type())
   343  		a.onlineCopyN(arg0, v, recvSize)
   344  
   345  		src := c.params + 1 // skip past identity
   346  		dst := arg0 + nodeid(recvSize)
   347  
   348  		// Copy caller's argument block to method formal parameters.
   349  		paramsSize := a.sizeof(sig.Params())
   350  		a.onlineCopyN(dst, src, paramsSize)
   351  		src += nodeid(paramsSize)
   352  		dst += nodeid(paramsSize)
   353  
   354  		// Copy method results to caller's result block.
   355  		resultsSize := a.sizeof(sig.Results())
   356  		a.onlineCopyN(src, dst, resultsSize)
   357  	}
   358  }
   359  
   360  func (c *addrConstraint) solve(a *analysis, delta *nodeset) {
   361  	panic("addr is not a complex constraint")
   362  }
   363  
   364  func (c *copyConstraint) solve(a *analysis, delta *nodeset) {
   365  	panic("copy is not a complex constraint")
   366  }
   367
View as plain text