blob: 0fdd098b0127ab600f5504343aef87f788e99933 [file] [log] [blame]
// 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")
}