go/pointer/solve.go - tools - Git at Google

 // Copyright 2013 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 pointer

 // This file defines a naive Andersen-style solver for the inclusion
 // constraint system.

 import (
 	"fmt"
 	"go/types"
 )

 type solverState struct {
 	complex []constraint // complex constraints attached to this node
 	copyTo  nodeset      // simple copy constraint edges
 	pts     nodeset      // points-to set of this node
 	prevPTS nodeset      // pts(n) in previous iteration (for difference propagation)
 }

 func (a *analysis) solve() {
 	start("Solving")
 	if a.log != nil {
 		fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
 	}

 	// Solver main loop.
 	var delta nodeset
 	for {
 		// Add new constraints to the graph:
 		// static constraints from SSA on round 1,
 		// dynamic constraints from reflection thereafter.
 		a.processNewConstraints()

 		var x int
 		if !a.work.TakeMin(&x) {
 			break // empty
 		}
 		id := nodeid(x)
 		if a.log != nil {
 			fmt.Fprintf(a.log, "\tnode n%d\n", id)
 		}

 		n := a.nodes[id]

 		// Difference propagation.
 		delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
 		if delta.IsEmpty() {
 			continue
 		}
 		if a.log != nil {
 			fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
 				id, n.typ, &delta, &n.solve.prevPTS)
 		}
 		n.solve.prevPTS.Copy(&n.solve.pts.Sparse)

 		// Apply all resolution rules attached to n.
 		a.solveConstraints(n, &delta)

 		if a.log != nil {
 			fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
 		}
 	}

 	if !a.nodes[0].solve.pts.IsEmpty() {
 		panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
 	}

 	// Release working state (but keep final PTS).
 	for _, n := range a.nodes {
 		n.solve.complex = nil
 		n.solve.copyTo.Clear()
 		n.solve.prevPTS.Clear()
 	}

 	if a.log != nil {
 		fmt.Fprintf(a.log, "Solver done\n")

 		// Dump solution.
 		for i, n := range a.nodes {
 			if !n.solve.pts.IsEmpty() {
 				fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, &n.solve.pts, n.typ)
 			}
 		}
 	}
 	stop("Solving")
 }

 // processNewConstraints takes the new constraints from a.constraints
 // and adds them to the graph, ensuring
 // that new constraints are applied to pre-existing labels and
 // that pre-existing constraints are applied to new labels.
 //
 func (a *analysis) processNewConstraints() {
 	// Take the slice of new constraints.
 	// (May grow during call to solveConstraints.)
 	constraints := a.constraints
 	a.constraints = nil

 	// Initialize points-to sets from addr-of (base) constraints.
 	for _, c := range constraints {
 		if c, ok := c.(*addrConstraint); ok {
 			dst := a.nodes[c.dst]
 			dst.solve.pts.add(c.src)

 			// Populate the worklist with nodes that point to
 			// something initially (due to addrConstraints) and
 			// have other constraints attached.
 			// (A no-op in round 1.)
 			if !dst.solve.copyTo.IsEmpty() || len(dst.solve.complex) > 0 {
 				a.addWork(c.dst)
 			}
 		}
 	}

 	// Attach simple (copy) and complex constraints to nodes.
 	var stale nodeset
 	for _, c := range constraints {
 		var id nodeid
 		switch c := c.(type) {
 		case *addrConstraint:
 			// base constraints handled in previous loop
 			continue
 		case *copyConstraint:
 			// simple (copy) constraint
 			id = c.src
 			a.nodes[id].solve.copyTo.add(c.dst)
 		default:
 			// complex constraint
 			id = c.ptr()
 			solve := a.nodes[id].solve
 			solve.complex = append(solve.complex, c)
 		}

 		if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
 			if !n.solve.prevPTS.IsEmpty() {
 				stale.add(id)
 			}
 			a.addWork(id)
 		}
 	}
 	// Apply new constraints to pre-existing PTS labels.
 	var space [50]int
 	for _, id := range stale.AppendTo(space[:0]) {
 		n := a.nodes[nodeid(id)]
 		a.solveConstraints(n, &n.solve.prevPTS)
 	}
 }

 // solveConstraints applies each resolution rule attached to node n to
 // the set of labels delta.  It may generate new constraints in
 // a.constraints.
 //
 func (a *analysis) solveConstraints(n *node, delta *nodeset) {
 	if delta.IsEmpty() {
 		return
 	}

 	// Process complex constraints dependent on n.
 	for _, c := range n.solve.complex {
 		if a.log != nil {
 			fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
 		}
 		c.solve(a, delta)
 	}

 	// Process copy constraints.
 	var copySeen nodeset
 	for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
 		mid := nodeid(x)
 		if copySeen.add(mid) {
 			if a.nodes[mid].solve.pts.addAll(delta) {
 				a.addWork(mid)
 			}
 		}
 	}
 }

 // addLabel adds label to the points-to set of ptr and reports whether the set grew.
 func (a *analysis) addLabel(ptr, label nodeid) bool {
 	b := a.nodes[ptr].solve.pts.add(label)
 	if b && a.log != nil {
 		fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
 	}
 	return b
 }

 func (a *analysis) addWork(id nodeid) {
 	a.work.Insert(int(id))
 	if a.log != nil {
 		fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
 	}
 }

 // onlineCopy adds a copy edge.  It is called online, i.e. during
 // solving, so it adds edges and pts members directly rather than by
 // instantiating a 'constraint'.
 //
 // The size of the copy is implicitly 1.
 // It returns true if pts(dst) changed.
 //
 func (a *analysis) onlineCopy(dst, src nodeid) bool {
 	if dst != src {
 		if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
 			if a.log != nil {
 				fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
 			}
 			// TODO(adonovan): most calls to onlineCopy
 			// are followed by addWork, possibly batched
 			// via a 'changed' flag; see if there's a
 			// noticeable penalty to calling addWork here.
 			return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
 		}
 	}
 	return false
 }

 // Returns sizeof.
 // Implicitly adds nodes to worklist.
 //
 // TODO(adonovan): now that we support a.copy() during solving, we
 // could eliminate onlineCopyN, but it's much slower.  Investigate.
 //
 func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
 	for i := uint32(0); i < sizeof; i++ {
 		if a.onlineCopy(dst, src) {
 			a.addWork(dst)
 		}
 		src++
 		dst++
 	}
 	return sizeof
 }

 func (c *loadConstraint) solve(a *analysis, delta *nodeset) {
 	var changed bool
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		k := nodeid(x)
 		koff := k + nodeid(c.offset)
 		if a.onlineCopy(c.dst, koff) {
 			changed = true
 		}
 	}
 	if changed {
 		a.addWork(c.dst)
 	}
 }

 func (c *storeConstraint) solve(a *analysis, delta *nodeset) {
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		k := nodeid(x)
 		koff := k + nodeid(c.offset)
 		if a.onlineCopy(koff, c.src) {
 			a.addWork(koff)
 		}
 	}
 }

 func (c *offsetAddrConstraint) solve(a *analysis, delta *nodeset) {
 	dst := a.nodes[c.dst]
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		k := nodeid(x)
 		if dst.solve.pts.add(k + nodeid(c.offset)) {
 			a.addWork(c.dst)
 		}
 	}
 }

 func (c *typeFilterConstraint) solve(a *analysis, delta *nodeset) {
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		ifaceObj := nodeid(x)
 		tDyn, _, indirect := a.taggedValue(ifaceObj)
 		if indirect {
 			// TODO(adonovan): we'll need to implement this
 			// when we start creating indirect tagged objects.
 			panic("indirect tagged object")
 		}

 		if types.AssignableTo(tDyn, c.typ) {
 			if a.addLabel(c.dst, ifaceObj) {
 				a.addWork(c.dst)
 			}
 		}
 	}
 }

 func (c *untagConstraint) solve(a *analysis, delta *nodeset) {
 	predicate := types.AssignableTo
 	if c.exact {
 		predicate = types.Identical
 	}
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		ifaceObj := nodeid(x)
 		tDyn, v, indirect := a.taggedValue(ifaceObj)
 		if indirect {
 			// TODO(adonovan): we'll need to implement this
 			// when we start creating indirect tagged objects.
 			panic("indirect tagged object")
 		}

 		if predicate(tDyn, c.typ) {
 			// Copy payload sans tag to dst.
 			//
 			// TODO(adonovan): opt: if tDyn is
 			// nonpointerlike we can skip this entire
 			// constraint, perhaps.  We only care about
 			// pointers among the fields.
 			a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
 		}
 	}
 }

 func (c *invokeConstraint) solve(a *analysis, delta *nodeset) {
 	for _, x := range delta.AppendTo(a.deltaSpace) {
 		ifaceObj := nodeid(x)
 		tDyn, v, indirect := a.taggedValue(ifaceObj)
 		if indirect {
 			// TODO(adonovan): we may need to implement this if
 			// we ever apply invokeConstraints to reflect.Value PTSs,
 			// e.g. for (reflect.Value).Call.
 			panic("indirect tagged object")
 		}

 		// Look up the concrete method.
 		fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
 		if fn == nil {
 			panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
 		}
 		sig := fn.Signature

 		fnObj := a.globalobj[fn] // dynamic calls use shared contour
 		if fnObj == 0 {
 			// a.objectNode(fn) was not called during gen phase.
 			panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
 		}

 		// Make callsite's fn variable point to identity of
 		// concrete method.  (There's no need to add it to
 		// worklist since it never has attached constraints.)
 		a.addLabel(c.params, fnObj)

 		// Extract value and connect to method's receiver.
 		// Copy payload to method's receiver param (arg0).
 		arg0 := a.funcParams(fnObj)
 		recvSize := a.sizeof(sig.Recv().Type())
 		a.onlineCopyN(arg0, v, recvSize)

 		src := c.params + 1 // skip past identity
 		dst := arg0 + nodeid(recvSize)

 		// Copy caller's argument block to method formal parameters.
 		paramsSize := a.sizeof(sig.Params())
 		a.onlineCopyN(dst, src, paramsSize)
 		src += nodeid(paramsSize)
 		dst += nodeid(paramsSize)

 		// Copy method results to caller's result block.
 		resultsSize := a.sizeof(sig.Results())
 		a.onlineCopyN(src, dst, resultsSize)
 	}
 }

 func (c *addrConstraint) solve(a *analysis, delta *nodeset) {
 	panic("addr is not a complex constraint")
 }

 func (c *copyConstraint) solve(a *analysis, delta *nodeset) {
 	panic("copy is not a complex constraint")
 }
	// Copyright 2013 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 pointer

	// This file defines a naive Andersen-style solver for the inclusion
	// constraint system.

	import (
	"fmt"
	"go/types"
	)

	type solverState struct {
	complex []constraint // complex constraints attached to this node
	copyTo nodeset // simple copy constraint edges
	pts nodeset // points-to set of this node
	prevPTS nodeset // pts(n) in previous iteration (for difference propagation)
	}

	func (a *analysis) solve() {
	start("Solving")
	if a.log != nil {
	fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
	}

	// Solver main loop.
	var delta nodeset
	for {
	// Add new constraints to the graph:
	// static constraints from SSA on round 1,
	// dynamic constraints from reflection thereafter.
	a.processNewConstraints()

	var x int
	if !a.work.TakeMin(&x) {
	break // empty
	}
	id := nodeid(x)
	if a.log != nil {
	fmt.Fprintf(a.log, "\tnode n%d\n", id)
	}

	n := a.nodes[id]

	// Difference propagation.
	delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
	if delta.IsEmpty() {
	continue
	}
	if a.log != nil {
	fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
	id, n.typ, &delta, &n.solve.prevPTS)
	}
	n.solve.prevPTS.Copy(&n.solve.pts.Sparse)

	// Apply all resolution rules attached to n.
	a.solveConstraints(n, &delta)

	if a.log != nil {
	fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
	}
	}

	if !a.nodes[0].solve.pts.IsEmpty() {
	panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
	}

	// Release working state (but keep final PTS).
	for _, n := range a.nodes {
	n.solve.complex = nil
	n.solve.copyTo.Clear()
	n.solve.prevPTS.Clear()
	}

	if a.log != nil {
	fmt.Fprintf(a.log, "Solver done\n")

	// Dump solution.
	for i, n := range a.nodes {
	if !n.solve.pts.IsEmpty() {
	fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, &n.solve.pts, n.typ)
	}
	}
	}
	stop("Solving")
	}

	// processNewConstraints takes the new constraints from a.constraints
	// and adds them to the graph, ensuring
	// that new constraints are applied to pre-existing labels and
	// that pre-existing constraints are applied to new labels.
	//
	func (a *analysis) processNewConstraints() {
	// Take the slice of new constraints.
	// (May grow during call to solveConstraints.)
	constraints := a.constraints
	a.constraints = nil

	// Initialize points-to sets from addr-of (base) constraints.
	for _, c := range constraints {
	if c, ok := c.(*addrConstraint); ok {
	dst := a.nodes[c.dst]
	dst.solve.pts.add(c.src)

	// Populate the worklist with nodes that point to
	// something initially (due to addrConstraints) and
	// have other constraints attached.
	// (A no-op in round 1.)
	if !dst.solve.copyTo.IsEmpty() \|\| len(dst.solve.complex) > 0 {
	a.addWork(c.dst)
	}
	}
	}

	// Attach simple (copy) and complex constraints to nodes.
	var stale nodeset
	for _, c := range constraints {
	var id nodeid
	switch c := c.(type) {
	case *addrConstraint:
	// base constraints handled in previous loop
	continue
	case *copyConstraint:
	// simple (copy) constraint
	id = c.src
	a.nodes[id].solve.copyTo.add(c.dst)
	default:
	// complex constraint
	id = c.ptr()
	solve := a.nodes[id].solve
	solve.complex = append(solve.complex, c)
	}

	if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
	if !n.solve.prevPTS.IsEmpty() {
	stale.add(id)
	}
	a.addWork(id)
	}
	}
	// Apply new constraints to pre-existing PTS labels.
	var space [50]int
	for _, id := range stale.AppendTo(space[:0]) {
	n := a.nodes[nodeid(id)]
	a.solveConstraints(n, &n.solve.prevPTS)
	}
	}

	// solveConstraints applies each resolution rule attached to node n to
	// the set of labels delta. It may generate new constraints in
	// a.constraints.
	//
	func (a analysis) solveConstraints(n node, delta *nodeset) {
	if delta.IsEmpty() {
	return
	}

	// Process complex constraints dependent on n.
	for _, c := range n.solve.complex {
	if a.log != nil {
	fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
	}
	c.solve(a, delta)
	}

	// Process copy constraints.
	var copySeen nodeset
	for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
	mid := nodeid(x)
	if copySeen.add(mid) {
	if a.nodes[mid].solve.pts.addAll(delta) {
	a.addWork(mid)
	}
	}
	}
	}

	// addLabel adds label to the points-to set of ptr and reports whether the set grew.
	func (a *analysis) addLabel(ptr, label nodeid) bool {
	b := a.nodes[ptr].solve.pts.add(label)
	if b && a.log != nil {
	fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
	}
	return b
	}

	func (a *analysis) addWork(id nodeid) {
	a.work.Insert(int(id))
	if a.log != nil {
	fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
	}
	}

	// onlineCopy adds a copy edge. It is called online, i.e. during
	// solving, so it adds edges and pts members directly rather than by
	// instantiating a 'constraint'.
	//
	// The size of the copy is implicitly 1.
	// It returns true if pts(dst) changed.
	//
	func (a *analysis) onlineCopy(dst, src nodeid) bool {
	if dst != src {
	if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
	if a.log != nil {
	fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
	}
	// TODO(adonovan): most calls to onlineCopy
	// are followed by addWork, possibly batched
	// via a 'changed' flag; see if there's a
	// noticeable penalty to calling addWork here.
	return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
	}
	}
	return false
	}

	// Returns sizeof.
	// Implicitly adds nodes to worklist.
	//
	// TODO(adonovan): now that we support a.copy() during solving, we
	// could eliminate onlineCopyN, but it's much slower. Investigate.
	//
	func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
	for i := uint32(0); i < sizeof; i++ {
	if a.onlineCopy(dst, src) {
	a.addWork(dst)
	}
	src++
	dst++
	}
	return sizeof
	}

	func (c loadConstraint) solve(a analysis, delta *nodeset) {
	var changed bool
	for _, x := range delta.AppendTo(a.deltaSpace) {
	k := nodeid(x)
	koff := k + nodeid(c.offset)
	if a.onlineCopy(c.dst, koff) {
	changed = true
	}
	}
	if changed {
	a.addWork(c.dst)
	}
	}

	func (c storeConstraint) solve(a analysis, delta *nodeset) {
	for _, x := range delta.AppendTo(a.deltaSpace) {
	k := nodeid(x)
	koff := k + nodeid(c.offset)
	if a.onlineCopy(koff, c.src) {
	a.addWork(koff)
	}
	}
	}

	func (c offsetAddrConstraint) solve(a analysis, delta *nodeset) {
	dst := a.nodes[c.dst]
	for _, x := range delta.AppendTo(a.deltaSpace) {
	k := nodeid(x)
	if dst.solve.pts.add(k + nodeid(c.offset)) {
	a.addWork(c.dst)
	}
	}
	}

	func (c typeFilterConstraint) solve(a analysis, delta *nodeset) {
	for _, x := range delta.AppendTo(a.deltaSpace) {
	ifaceObj := nodeid(x)
	tDyn, _, indirect := a.taggedValue(ifaceObj)
	if indirect {
	// TODO(adonovan): we'll need to implement this
	// when we start creating indirect tagged objects.
	panic("indirect tagged object")
	}

	if types.AssignableTo(tDyn, c.typ) {
	if a.addLabel(c.dst, ifaceObj) {
	a.addWork(c.dst)
	}
	}
	}
	}

	func (c untagConstraint) solve(a analysis, delta *nodeset) {
	predicate := types.AssignableTo
	if c.exact {
	predicate = types.Identical
	}
	for _, x := range delta.AppendTo(a.deltaSpace) {
	ifaceObj := nodeid(x)
	tDyn, v, indirect := a.taggedValue(ifaceObj)
	if indirect {
	// TODO(adonovan): we'll need to implement this
	// when we start creating indirect tagged objects.
	panic("indirect tagged object")
	}

	if predicate(tDyn, c.typ) {
	// Copy payload sans tag to dst.
	//
	// TODO(adonovan): opt: if tDyn is
	// nonpointerlike we can skip this entire
	// constraint, perhaps. We only care about
	// pointers among the fields.
	a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
	}
	}
	}

	func (c invokeConstraint) solve(a analysis, delta *nodeset) {
	for _, x := range delta.AppendTo(a.deltaSpace) {
	ifaceObj := nodeid(x)
	tDyn, v, indirect := a.taggedValue(ifaceObj)
	if indirect {
	// TODO(adonovan): we may need to implement this if
	// we ever apply invokeConstraints to reflect.Value PTSs,
	// e.g. for (reflect.Value).Call.
	panic("indirect tagged object")
	}

	// Look up the concrete method.
	fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
	if fn == nil {
	panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
	}
	sig := fn.Signature

	fnObj := a.globalobj[fn] // dynamic calls use shared contour
	if fnObj == 0 {
	// a.objectNode(fn) was not called during gen phase.
	panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
	}

	// Make callsite's fn variable point to identity of
	// concrete method. (There's no need to add it to
	// worklist since it never has attached constraints.)
	a.addLabel(c.params, fnObj)

	// Extract value and connect to method's receiver.
	// Copy payload to method's receiver param (arg0).
	arg0 := a.funcParams(fnObj)
	recvSize := a.sizeof(sig.Recv().Type())
	a.onlineCopyN(arg0, v, recvSize)

	src := c.params + 1 // skip past identity
	dst := arg0 + nodeid(recvSize)

	// Copy caller's argument block to method formal parameters.
	paramsSize := a.sizeof(sig.Params())
	a.onlineCopyN(dst, src, paramsSize)
	src += nodeid(paramsSize)
	dst += nodeid(paramsSize)

	// Copy method results to caller's result block.
	resultsSize := a.sizeof(sig.Results())
	a.onlineCopyN(src, dst, resultsSize)
	}
	}

	func (c addrConstraint) solve(a analysis, delta *nodeset) {
	panic("addr is not a complex constraint")
	}

	func (c copyConstraint) solve(a analysis, delta *nodeset) {
	panic("copy is not a complex constraint")
	}