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