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.
7 // This file defines a naive Andersen-style solver for the inclusion
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)
22 func (a *analysis) solve() {
25 fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
31 // Add new constraints to the graph:
32 // static constraints from SSA on round 1,
33 // dynamic constraints from reflection thereafter.
34 a.processNewConstraints()
37 if !a.work.TakeMin(&x) {
42 fmt.Fprintf(a.log, "\tnode n%d\n", id)
47 // Difference propagation.
48 delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
53 fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
54 id, n.typ, &delta, &n.solve.prevPTS)
56 n.solve.prevPTS.Copy(&n.solve.pts.Sparse)
58 // Apply all resolution rules attached to n.
59 a.solveConstraints(n, &delta)
62 fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
66 if !a.nodes[0].solve.pts.IsEmpty() {
67 panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
70 // Release working state (but keep final PTS).
71 for _, n := range a.nodes {
73 n.solve.copyTo.Clear()
74 n.solve.prevPTS.Clear()
78 fmt.Fprintf(a.log, "Solver done\n")
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)
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.
95 func (a *analysis) processNewConstraints() {
96 // Take the slice of new constraints.
97 // (May grow during call to solveConstraints.)
98 constraints := a.constraints
101 // Initialize points-to sets from addr-of (base) constraints.
102 for _, c := range constraints {
103 if c, ok := c.(*addrConstraint); ok {
104 dst := a.nodes[c.dst]
105 dst.solve.pts.add(c.src)
107 // Populate the worklist with nodes that point to
108 // something initially (due to addrConstraints) and
109 // have other constraints attached.
110 // (A no-op in round 1.)
111 if !dst.solve.copyTo.IsEmpty() || len(dst.solve.complex) > 0 {
117 // Attach simple (copy) and complex constraints to nodes.
119 for _, c := range constraints {
121 switch c := c.(type) {
122 case *addrConstraint:
123 // base constraints handled in previous loop
125 case *copyConstraint:
126 // simple (copy) constraint
128 a.nodes[id].solve.copyTo.add(c.dst)
130 // complex constraint
132 solve := a.nodes[id].solve
133 solve.complex = append(solve.complex, c)
136 if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
137 if !n.solve.prevPTS.IsEmpty() {
143 // Apply new constraints to pre-existing PTS labels.
145 for _, id := range stale.AppendTo(space[:0]) {
146 n := a.nodes[nodeid(id)]
147 a.solveConstraints(n, &n.solve.prevPTS)
151 // solveConstraints applies each resolution rule attached to node n to
152 // the set of labels delta. It may generate new constraints in
155 func (a *analysis) solveConstraints(n *node, delta *nodeset) {
160 // Process complex constraints dependent on n.
161 for _, c := range n.solve.complex {
163 fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
168 // Process copy constraints.
170 for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
172 if copySeen.add(mid) {
173 if a.nodes[mid].solve.pts.addAll(delta) {
180 // addLabel adds label to the points-to set of ptr and reports whether the set grew.
181 func (a *analysis) addLabel(ptr, label nodeid) bool {
182 b := a.nodes[ptr].solve.pts.add(label)
183 if b && a.log != nil {
184 fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
189 func (a *analysis) addWork(id nodeid) {
190 a.work.Insert(int(id))
192 fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
196 // onlineCopy adds a copy edge. It is called online, i.e. during
197 // solving, so it adds edges and pts members directly rather than by
198 // instantiating a 'constraint'.
200 // The size of the copy is implicitly 1.
201 // It returns true if pts(dst) changed.
203 func (a *analysis) onlineCopy(dst, src nodeid) bool {
205 if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
207 fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
209 // TODO(adonovan): most calls to onlineCopy
210 // are followed by addWork, possibly batched
211 // via a 'changed' flag; see if there's a
212 // noticeable penalty to calling addWork here.
213 return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
220 // Implicitly adds nodes to worklist.
222 // TODO(adonovan): now that we support a.copy() during solving, we
223 // could eliminate onlineCopyN, but it's much slower. Investigate.
225 func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
226 for i := uint32(0); i < sizeof; i++ {
227 if a.onlineCopy(dst, src) {
236 func (c *loadConstraint) solve(a *analysis, delta *nodeset) {
238 for _, x := range delta.AppendTo(a.deltaSpace) {
240 koff := k + nodeid(c.offset)
241 if a.onlineCopy(c.dst, koff) {
250 func (c *storeConstraint) solve(a *analysis, delta *nodeset) {
251 for _, x := range delta.AppendTo(a.deltaSpace) {
253 koff := k + nodeid(c.offset)
254 if a.onlineCopy(koff, c.src) {
260 func (c *offsetAddrConstraint) solve(a *analysis, delta *nodeset) {
261 dst := a.nodes[c.dst]
262 for _, x := range delta.AppendTo(a.deltaSpace) {
264 if dst.solve.pts.add(k + nodeid(c.offset)) {
270 func (c *typeFilterConstraint) solve(a *analysis, delta *nodeset) {
271 for _, x := range delta.AppendTo(a.deltaSpace) {
272 ifaceObj := nodeid(x)
273 tDyn, _, indirect := a.taggedValue(ifaceObj)
275 // TODO(adonovan): we'll need to implement this
276 // when we start creating indirect tagged objects.
277 panic("indirect tagged object")
280 if types.AssignableTo(tDyn, c.typ) {
281 if a.addLabel(c.dst, ifaceObj) {
288 func (c *untagConstraint) solve(a *analysis, delta *nodeset) {
289 predicate := types.AssignableTo
291 predicate = types.Identical
293 for _, x := range delta.AppendTo(a.deltaSpace) {
294 ifaceObj := nodeid(x)
295 tDyn, v, indirect := a.taggedValue(ifaceObj)
297 // TODO(adonovan): we'll need to implement this
298 // when we start creating indirect tagged objects.
299 panic("indirect tagged object")
302 if predicate(tDyn, c.typ) {
303 // Copy payload sans tag to dst.
305 // TODO(adonovan): opt: if tDyn is
306 // nonpointerlike we can skip this entire
307 // constraint, perhaps. We only care about
308 // pointers among the fields.
309 a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
314 func (c *invokeConstraint) solve(a *analysis, delta *nodeset) {
315 for _, x := range delta.AppendTo(a.deltaSpace) {
316 ifaceObj := nodeid(x)
317 tDyn, v, indirect := a.taggedValue(ifaceObj)
319 // TODO(adonovan): we may need to implement this if
320 // we ever apply invokeConstraints to reflect.Value PTSs,
321 // e.g. for (reflect.Value).Call.
322 panic("indirect tagged object")
325 // Look up the concrete method.
326 fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
328 panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
332 fnObj := a.globalobj[fn] // dynamic calls use shared contour
334 // a.objectNode(fn) was not called during gen phase.
335 panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
338 // Make callsite's fn variable point to identity of
339 // concrete method. (There's no need to add it to
340 // worklist since it never has attached constraints.)
341 a.addLabel(c.params, fnObj)
343 // Extract value and connect to method's receiver.
344 // Copy payload to method's receiver param (arg0).
345 arg0 := a.funcParams(fnObj)
346 recvSize := a.sizeof(sig.Recv().Type())
347 a.onlineCopyN(arg0, v, recvSize)
349 src := c.params + 1 // skip past identity
350 dst := arg0 + nodeid(recvSize)
352 // Copy caller's argument block to method formal parameters.
353 paramsSize := a.sizeof(sig.Params())
354 a.onlineCopyN(dst, src, paramsSize)
355 src += nodeid(paramsSize)
356 dst += nodeid(paramsSize)
358 // Copy method results to caller's result block.
359 resultsSize := a.sizeof(sig.Results())
360 a.onlineCopyN(src, dst, resultsSize)
364 func (c *addrConstraint) solve(a *analysis, delta *nodeset) {
365 panic("addr is not a complex constraint")
368 func (c *copyConstraint) solve(a *analysis, delta *nodeset) {
369 panic("copy is not a complex constraint")