| 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 |
Members