| 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 implements Hash-Value Numbering (HVN), a pre-solver |
| 8 | // constraint optimization described in Hardekopf & Lin, SAS'07 (see |
| 9 | // doc.go) that analyses the graph topology to determine which sets of |
| 10 | // variables are "pointer equivalent" (PE), i.e. must have identical |
| 11 | // points-to sets in the solution. |
| 12 | // |
| 13 | // A separate ("offline") graph is constructed. Its nodes are those of |
| 14 | // the main-graph, plus an additional node *X for each pointer node X. |
| 15 | // With this graph we can reason about the unknown points-to set of |
| 16 | // dereferenced pointers. (We do not generalize this to represent |
| 17 | // unknown fields x->f, perhaps because such fields would be numerous, |
| 18 | // though it might be worth an experiment.) |
| 19 | // |
| 20 | // Nodes whose points-to relations are not entirely captured by the |
| 21 | // graph are marked as "indirect": the *X nodes, the parameters of |
| 22 | // address-taken functions (which includes all functions in method |
| 23 | // sets), or nodes updated by the solver rules for reflection, etc. |
| 24 | // |
| 25 | // All addr (y=&x) nodes are initially assigned a pointer-equivalence |
| 26 | // (PE) label equal to x's nodeid in the main graph. (These are the |
| 27 | // only PE labels that are less than len(a.nodes).) |
| 28 | // |
| 29 | // All offsetAddr (y=&x.f) constraints are initially assigned a PE |
| 30 | // label; such labels are memoized, keyed by (x, f), so that equivalent |
| 31 | // nodes y as assigned the same label. |
| 32 | // |
| 33 | // Then we process each strongly connected component (SCC) of the graph |
| 34 | // in topological order, assigning it a PE label based on the set P of |
| 35 | // PE labels that flow to it from its immediate dependencies. |
| 36 | // |
| 37 | // If any node in P is "indirect", the entire SCC is assigned a fresh PE |
| 38 | // label. Otherwise: |
| 39 | // |
| 40 | // |P|=0 if P is empty, all nodes in the SCC are non-pointers (e.g. |
| 41 | // uninitialized variables, or formal params of dead functions) |
| 42 | // and the SCC is assigned the PE label of zero. |
| 43 | // |
| 44 | // |P|=1 if P is a singleton, the SCC is assigned the same label as the |
| 45 | // sole element of P. |
| 46 | // |
| 47 | // |P|>1 if P contains multiple labels, a unique label representing P is |
| 48 | // invented and recorded in an hash table, so that other |
| 49 | // equivalent SCCs may also be assigned this label, akin to |
| 50 | // conventional hash-value numbering in a compiler. |
| 51 | // |
| 52 | // Finally, a renumbering is computed such that each node is replaced by |
| 53 | // the lowest-numbered node with the same PE label. All constraints are |
| 54 | // renumbered, and any resulting duplicates are eliminated. |
| 55 | // |
| 56 | // The only nodes that are not renumbered are the objects x in addr |
| 57 | // (y=&x) constraints, since the ids of these nodes (and fields derived |
| 58 | // from them via offsetAddr rules) are the elements of all points-to |
| 59 | // sets, so they must remain as they are if we want the same solution. |
| 60 | // |
| 61 | // The solverStates (node.solve) for nodes in the same equivalence class |
| 62 | // are linked together so that all nodes in the class have the same |
| 63 | // solution. This avoids the need to renumber nodeids buried in |
| 64 | // Queries, cgnodes, etc (like (*analysis).renumber() does) since only |
| 65 | // the solution is needed. |
| 66 | // |
| 67 | // The result of HVN is that the number of distinct nodes and |
| 68 | // constraints is reduced, but the solution is identical (almost---see |
| 69 | // CROSS-CHECK below). In particular, both linear and cyclic chains of |
| 70 | // copies are each replaced by a single node. |
| 71 | // |
| 72 | // Nodes and constraints created "online" (e.g. while solving reflection |
| 73 | // constraints) are not subject to this optimization. |
| 74 | // |
| 75 | // PERFORMANCE |
| 76 | // |
| 77 | // In two benchmarks (guru and godoc), HVN eliminates about two thirds |
| 78 | // of nodes, the majority accounted for by non-pointers: nodes of |
| 79 | // non-pointer type, pointers that remain nil, formal parameters of dead |
| 80 | // functions, nodes of untracked types, etc. It also reduces the number |
| 81 | // of constraints, also by about two thirds, and the solving time by |
| 82 | // 30--42%, although we must pay about 15% for the running time of HVN |
| 83 | // itself. The benefit is greater for larger applications. |
| 84 | // |
| 85 | // There are many possible optimizations to improve the performance: |
| 86 | // * Use fewer than 1:1 onodes to main graph nodes: many of the onodes |
| 87 | // we create are not needed. |
| 88 | // * HU (HVN with Union---see paper): coalesce "union" peLabels when |
| 89 | // their expanded-out sets are equal. |
| 90 | // * HR (HVN with deReference---see paper): this will require that we |
| 91 | // apply HVN until fixed point, which may need more bookkeeping of the |
| 92 | // correspondence of main nodes to onodes. |
| 93 | // * Location Equivalence (see paper): have points-to sets contain not |
| 94 | // locations but location-equivalence class labels, each representing |
| 95 | // a set of locations. |
| 96 | // * HVN with field-sensitive ref: model each of the fields of a |
| 97 | // pointer-to-struct. |
| 98 | // |
| 99 | // CROSS-CHECK |
| 100 | // |
| 101 | // To verify the soundness of the optimization, when the |
| 102 | // debugHVNCrossCheck option is enabled, we run the solver twice, once |
| 103 | // before and once after running HVN, dumping the solution to disk, and |
| 104 | // then we compare the results. If they are not identical, the analysis |
| 105 | // panics. |
| 106 | // |
| 107 | // The solution dumped to disk includes only the N*N submatrix of the |
| 108 | // complete solution where N is the number of nodes after generation. |
| 109 | // In other words, we ignore pointer variables and objects created by |
| 110 | // the solver itself, since their numbering depends on the solver order, |
| 111 | // which is affected by the optimization. In any case, that's the only |
| 112 | // part the client cares about. |
| 113 | // |
| 114 | // The cross-check is too strict and may fail spuriously. Although the |
| 115 | // H&L paper describing HVN states that the solutions obtained should be |
| 116 | // identical, this is not the case in practice because HVN can collapse |
| 117 | // cycles involving *p even when pts(p)={}. Consider this example |
| 118 | // distilled from testdata/hello.go: |
| 119 | // |
| 120 | // var x T |
| 121 | // func f(p **T) { |
| 122 | // t0 = *p |
| 123 | // ... |
| 124 | // t1 = φ(t0, &x) |
| 125 | // *p = t1 |
| 126 | // } |
| 127 | // |
| 128 | // If f is dead code, we get: |
| 129 | // unoptimized: pts(p)={} pts(t0)={} pts(t1)={&x} |
| 130 | // optimized: pts(p)={} pts(t0)=pts(t1)=pts(*p)={&x} |
| 131 | // |
| 132 | // It's hard to argue that this is a bug: the result is sound and the |
| 133 | // loss of precision is inconsequential---f is dead code, after all. |
| 134 | // But unfortunately it limits the usefulness of the cross-check since |
| 135 | // failures must be carefully analyzed. Ben Hardekopf suggests (in |
| 136 | // personal correspondence) some approaches to mitigating it: |
| 137 | // |
| 138 | // If there is a node with an HVN points-to set that is a superset |
| 139 | // of the NORM points-to set, then either it's a bug or it's a |
| 140 | // result of this issue. If it's a result of this issue, then in |
| 141 | // the offline constraint graph there should be a REF node inside |
| 142 | // some cycle that reaches this node, and in the NORM solution the |
| 143 | // pointer being dereferenced by that REF node should be the empty |
| 144 | // set. If that isn't true then this is a bug. If it is true, then |
| 145 | // you can further check that in the NORM solution the "extra" |
| 146 | // points-to info in the HVN solution does in fact come from that |
| 147 | // purported cycle (if it doesn't, then this is still a bug). If |
| 148 | // you're doing the further check then you'll need to do it for |
| 149 | // each "extra" points-to element in the HVN points-to set. |
| 150 | // |
| 151 | // There are probably ways to optimize these checks by taking |
| 152 | // advantage of graph properties. For example, extraneous points-to |
| 153 | // info will flow through the graph and end up in many |
| 154 | // nodes. Rather than checking every node with extra info, you |
| 155 | // could probably work out the "origin point" of the extra info and |
| 156 | // just check there. Note that the check in the first bullet is |
| 157 | // looking for soundness bugs, while the check in the second bullet |
| 158 | // is looking for precision bugs; depending on your needs, you may |
| 159 | // care more about one than the other. |
| 160 | // |
| 161 | // which we should evaluate. The cross-check is nonetheless invaluable |
| 162 | // for all but one of the programs in the pointer_test suite. |
| 163 | |
| 164 | import ( |
| 165 | "fmt" |
| 166 | "go/types" |
| 167 | "io" |
| 168 | "reflect" |
| 169 | |
| 170 | "golang.org/x/tools/container/intsets" |
| 171 | ) |
| 172 | |
| 173 | // A peLabel is a pointer-equivalence label: two nodes with the same |
| 174 | // peLabel have identical points-to solutions. |
| 175 | // |
| 176 | // The numbers are allocated consecutively like so: |
| 177 | // |
| 178 | // 0 not a pointer |
| 179 | // 1..N-1 addrConstraints (equals the constraint's .src field, hence sparse) |
| 180 | // ... offsetAddr constraints |
| 181 | // ... SCCs (with indirect nodes or multiple inputs) |
| 182 | // |
| 183 | // Each PE label denotes a set of pointers containing a single addr, a |
| 184 | // single offsetAddr, or some set of other PE labels. |
| 185 | type peLabel int |
| 186 | |
| 187 | type hvn struct { |
| 188 | a *analysis |
| 189 | N int // len(a.nodes) immediately after constraint generation |
| 190 | log io.Writer // (optional) log of HVN lemmas |
| 191 | onodes []*onode // nodes of the offline graph |
| 192 | label peLabel // the next available PE label |
| 193 | hvnLabel map[string]peLabel // hash-value numbering (PE label) for each set of onodeids |
| 194 | stack []onodeid // DFS stack |
| 195 | index int32 // next onode.index, from Tarjan's SCC algorithm |
| 196 | |
| 197 | // For each distinct offsetAddrConstraint (src, offset) pair, |
| 198 | // offsetAddrLabels records a unique PE label >= N. |
| 199 | offsetAddrLabels map[offsetAddr]peLabel |
| 200 | } |
| 201 | |
| 202 | // The index of an node in the offline graph. |
| 203 | // (Currently the first N align with the main nodes, |
| 204 | // but this may change with HRU.) |
| 205 | type onodeid uint32 |
| 206 | |
| 207 | // An onode is a node in the offline constraint graph. |
| 208 | // (Where ambiguous, members of analysis.nodes are referred to as |
| 209 | // "main graph" nodes.) |
| 210 | // |
| 211 | // Edges in the offline constraint graph (edges and implicit) point to |
| 212 | // the source, i.e. against the flow of values: they are dependencies. |
| 213 | // Implicit edges are used for SCC computation, but not for gathering |
| 214 | // incoming labels. |
| 215 | type onode struct { |
| 216 | rep onodeid // index of representative of SCC in offline constraint graph |
| 217 | |
| 218 | edges intsets.Sparse // constraint edges X-->Y (this onode is X) |
| 219 | implicit intsets.Sparse // implicit edges *X-->*Y (this onode is X) |
| 220 | peLabels intsets.Sparse // set of peLabels are pointer-equivalent to this one |
| 221 | indirect bool // node has points-to relations not represented in graph |
| 222 | |
| 223 | // Tarjan's SCC algorithm |
| 224 | index, lowlink int32 // Tarjan numbering |
| 225 | scc int32 // -ve => on stack; 0 => unvisited; +ve => node is root of a found SCC |
| 226 | } |
| 227 | |
| 228 | type offsetAddr struct { |
| 229 | ptr nodeid |
| 230 | offset uint32 |
| 231 | } |
| 232 | |
| 233 | // nextLabel issues the next unused pointer-equivalence label. |
| 234 | func (h *hvn) nextLabel() peLabel { |
| 235 | h.label++ |
| 236 | return h.label |
| 237 | } |
| 238 | |
| 239 | // ref(X) returns the index of the onode for *X. |
| 240 | func (h *hvn) ref(id onodeid) onodeid { |
| 241 | return id + onodeid(len(h.a.nodes)) |
| 242 | } |
| 243 | |
| 244 | // hvn computes pointer-equivalence labels (peLabels) using the Hash-based |
| 245 | // Value Numbering (HVN) algorithm described in Hardekopf & Lin, SAS'07. |
| 246 | func (a *analysis) hvn() { |
| 247 | start("HVN") |
| 248 | |
| 249 | if a.log != nil { |
| 250 | fmt.Fprintf(a.log, "\n\n==== Pointer equivalence optimization\n\n") |
| 251 | } |
| 252 | |
| 253 | h := hvn{ |
| 254 | a: a, |
| 255 | N: len(a.nodes), |
| 256 | log: a.log, |
| 257 | hvnLabel: make(map[string]peLabel), |
| 258 | offsetAddrLabels: make(map[offsetAddr]peLabel), |
| 259 | } |
| 260 | |
| 261 | if h.log != nil { |
| 262 | fmt.Fprintf(h.log, "\nCreating offline graph nodes...\n") |
| 263 | } |
| 264 | |
| 265 | // Create offline nodes. The first N nodes correspond to main |
| 266 | // graph nodes; the next N are their corresponding ref() nodes. |
| 267 | h.onodes = make([]*onode, 2*h.N) |
| 268 | for id := range a.nodes { |
| 269 | id := onodeid(id) |
| 270 | h.onodes[id] = &onode{} |
| 271 | h.onodes[h.ref(id)] = &onode{indirect: true} |
| 272 | } |
| 273 | |
| 274 | // Each node initially represents just itself. |
| 275 | for id, o := range h.onodes { |
| 276 | o.rep = onodeid(id) |
| 277 | } |
| 278 | |
| 279 | h.markIndirectNodes() |
| 280 | |
| 281 | // Reserve the first N PE labels for addrConstraints. |
| 282 | h.label = peLabel(h.N) |
| 283 | |
| 284 | // Add offline constraint edges. |
| 285 | if h.log != nil { |
| 286 | fmt.Fprintf(h.log, "\nAdding offline graph edges...\n") |
| 287 | } |
| 288 | for _, c := range a.constraints { |
| 289 | if debugHVNVerbose && h.log != nil { |
| 290 | fmt.Fprintf(h.log, "; %s\n", c) |
| 291 | } |
| 292 | c.presolve(&h) |
| 293 | } |
| 294 | |
| 295 | // Find and collapse SCCs. |
| 296 | if h.log != nil { |
| 297 | fmt.Fprintf(h.log, "\nFinding SCCs...\n") |
| 298 | } |
| 299 | h.index = 1 |
| 300 | for id, o := range h.onodes { |
| 301 | if id > 0 && o.index == 0 { |
| 302 | // Start depth-first search at each unvisited node. |
| 303 | h.visit(onodeid(id)) |
| 304 | } |
| 305 | } |
| 306 | |
| 307 | // Dump the solution |
| 308 | // (NB: somewhat redundant with logging from simplify().) |
| 309 | if debugHVNVerbose && h.log != nil { |
| 310 | fmt.Fprintf(h.log, "\nPointer equivalences:\n") |
| 311 | for id, o := range h.onodes { |
| 312 | if id == 0 { |
| 313 | continue |
| 314 | } |
| 315 | if id == int(h.N) { |
| 316 | fmt.Fprintf(h.log, "---\n") |
| 317 | } |
| 318 | fmt.Fprintf(h.log, "o%d\t", id) |
| 319 | if o.rep != onodeid(id) { |
| 320 | fmt.Fprintf(h.log, "rep=o%d", o.rep) |
| 321 | } else { |
| 322 | fmt.Fprintf(h.log, "p%d", o.peLabels.Min()) |
| 323 | if o.indirect { |
| 324 | fmt.Fprint(h.log, " indirect") |
| 325 | } |
| 326 | } |
| 327 | fmt.Fprintln(h.log) |
| 328 | } |
| 329 | } |
| 330 | |
| 331 | // Simplify the main constraint graph |
| 332 | h.simplify() |
| 333 | |
| 334 | a.showCounts() |
| 335 | |
| 336 | stop("HVN") |
| 337 | } |
| 338 | |
| 339 | // ---- constraint-specific rules ---- |
| 340 | |
| 341 | // dst := &src |
| 342 | func (c *addrConstraint) presolve(h *hvn) { |
| 343 | // Each object (src) is an initial PE label. |
| 344 | label := peLabel(c.src) // label < N |
| 345 | if debugHVNVerbose && h.log != nil { |
| 346 | // duplicate log messages are possible |
| 347 | fmt.Fprintf(h.log, "\tcreate p%d: {&n%d}\n", label, c.src) |
| 348 | } |
| 349 | odst := onodeid(c.dst) |
| 350 | osrc := onodeid(c.src) |
| 351 | |
| 352 | // Assign dst this label. |
| 353 | h.onodes[odst].peLabels.Insert(int(label)) |
| 354 | if debugHVNVerbose && h.log != nil { |
| 355 | fmt.Fprintf(h.log, "\to%d has p%d\n", odst, label) |
| 356 | } |
| 357 | |
| 358 | h.addImplicitEdge(h.ref(odst), osrc) // *dst ~~> src. |
| 359 | } |
| 360 | |
| 361 | // dst = src |
| 362 | func (c *copyConstraint) presolve(h *hvn) { |
| 363 | odst := onodeid(c.dst) |
| 364 | osrc := onodeid(c.src) |
| 365 | h.addEdge(odst, osrc) // dst --> src |
| 366 | h.addImplicitEdge(h.ref(odst), h.ref(osrc)) // *dst ~~> *src |
| 367 | } |
| 368 | |
| 369 | // dst = *src + offset |
| 370 | func (c *loadConstraint) presolve(h *hvn) { |
| 371 | odst := onodeid(c.dst) |
| 372 | osrc := onodeid(c.src) |
| 373 | if c.offset == 0 { |
| 374 | h.addEdge(odst, h.ref(osrc)) // dst --> *src |
| 375 | } else { |
| 376 | // We don't interpret load-with-offset, e.g. results |
| 377 | // of map value lookup, R-block of dynamic call, slice |
| 378 | // copy/append, reflection. |
| 379 | h.markIndirect(odst, "load with offset") |
| 380 | } |
| 381 | } |
| 382 | |
| 383 | // *dst + offset = src |
| 384 | func (c *storeConstraint) presolve(h *hvn) { |
| 385 | odst := onodeid(c.dst) |
| 386 | osrc := onodeid(c.src) |
| 387 | if c.offset == 0 { |
| 388 | h.onodes[h.ref(odst)].edges.Insert(int(osrc)) // *dst --> src |
| 389 | if debugHVNVerbose && h.log != nil { |
| 390 | fmt.Fprintf(h.log, "\to%d --> o%d\n", h.ref(odst), osrc) |
| 391 | } |
| 392 | } |
| 393 | // We don't interpret store-with-offset. |
| 394 | // See discussion of soundness at markIndirectNodes. |
| 395 | } |
| 396 | |
| 397 | // dst = &src.offset |
| 398 | func (c *offsetAddrConstraint) presolve(h *hvn) { |
| 399 | // Give each distinct (addr, offset) pair a fresh PE label. |
| 400 | // The cache performs CSE, effectively. |
| 401 | key := offsetAddr{c.src, c.offset} |
| 402 | label, ok := h.offsetAddrLabels[key] |
| 403 | if !ok { |
| 404 | label = h.nextLabel() |
| 405 | h.offsetAddrLabels[key] = label |
| 406 | if debugHVNVerbose && h.log != nil { |
| 407 | fmt.Fprintf(h.log, "\tcreate p%d: {&n%d.#%d}\n", |
| 408 | label, c.src, c.offset) |
| 409 | } |
| 410 | } |
| 411 | |
| 412 | // Assign dst this label. |
| 413 | h.onodes[c.dst].peLabels.Insert(int(label)) |
| 414 | if debugHVNVerbose && h.log != nil { |
| 415 | fmt.Fprintf(h.log, "\to%d has p%d\n", c.dst, label) |
| 416 | } |
| 417 | } |
| 418 | |
| 419 | // dst = src.(typ) where typ is an interface |
| 420 | func (c *typeFilterConstraint) presolve(h *hvn) { |
| 421 | h.markIndirect(onodeid(c.dst), "typeFilter result") |
| 422 | } |
| 423 | |
| 424 | // dst = src.(typ) where typ is concrete |
| 425 | func (c *untagConstraint) presolve(h *hvn) { |
| 426 | odst := onodeid(c.dst) |
| 427 | for end := odst + onodeid(h.a.sizeof(c.typ)); odst < end; odst++ { |
| 428 | h.markIndirect(odst, "untag result") |
| 429 | } |
| 430 | } |
| 431 | |
| 432 | // dst = src.method(c.params...) |
| 433 | func (c *invokeConstraint) presolve(h *hvn) { |
| 434 | // All methods are address-taken functions, so |
| 435 | // their formal P-blocks were already marked indirect. |
| 436 | |
| 437 | // Mark the caller's targets node as indirect. |
| 438 | sig := c.method.Type().(*types.Signature) |
| 439 | id := c.params |
| 440 | h.markIndirect(onodeid(c.params), "invoke targets node") |
| 441 | id++ |
| 442 | |
| 443 | id += nodeid(h.a.sizeof(sig.Params())) |
| 444 | |
| 445 | // Mark the caller's R-block as indirect. |
| 446 | end := id + nodeid(h.a.sizeof(sig.Results())) |
| 447 | for id < end { |
| 448 | h.markIndirect(onodeid(id), "invoke R-block") |
| 449 | id++ |
| 450 | } |
| 451 | } |
| 452 | |
| 453 | // markIndirectNodes marks as indirect nodes whose points-to relations |
| 454 | // are not entirely captured by the offline graph, including: |
| 455 | // |
| 456 | // (a) All address-taken nodes (including the following nodes within |
| 457 | // the same object). This is described in the paper. |
| 458 | // |
| 459 | // The most subtle cause of indirect nodes is the generation of |
| 460 | // store-with-offset constraints since the offline graph doesn't |
| 461 | // represent them. A global audit of constraint generation reveals the |
| 462 | // following uses of store-with-offset: |
| 463 | // |
| 464 | // (b) genDynamicCall, for P-blocks of dynamically called functions, |
| 465 | // to which dynamic copy edges will be added to them during |
| 466 | // solving: from storeConstraint for standalone functions, |
| 467 | // and from invokeConstraint for methods. |
| 468 | // All such P-blocks must be marked indirect. |
| 469 | // (c) MakeUpdate, to update the value part of a map object. |
| 470 | // All MakeMap objects's value parts must be marked indirect. |
| 471 | // (d) copyElems, to update the destination array. |
| 472 | // All array elements must be marked indirect. |
| 473 | // |
| 474 | // Not all indirect marking happens here. ref() nodes are marked |
| 475 | // indirect at construction, and each constraint's presolve() method may |
| 476 | // mark additional nodes. |
| 477 | func (h *hvn) markIndirectNodes() { |
| 478 | // (a) all address-taken nodes, plus all nodes following them |
| 479 | // within the same object, since these may be indirectly |
| 480 | // stored or address-taken. |
| 481 | for _, c := range h.a.constraints { |
| 482 | if c, ok := c.(*addrConstraint); ok { |
| 483 | start := h.a.enclosingObj(c.src) |
| 484 | end := start + nodeid(h.a.nodes[start].obj.size) |
| 485 | for id := c.src; id < end; id++ { |
| 486 | h.markIndirect(onodeid(id), "A-T object") |
| 487 | } |
| 488 | } |
| 489 | } |
| 490 | |
| 491 | // (b) P-blocks of all address-taken functions. |
| 492 | for id := 0; id < h.N; id++ { |
| 493 | obj := h.a.nodes[id].obj |
| 494 | |
| 495 | // TODO(adonovan): opt: if obj.cgn.fn is a method and |
| 496 | // obj.cgn is not its shared contour, this is an |
| 497 | // "inlined" static method call. We needn't consider it |
| 498 | // address-taken since no invokeConstraint will affect it. |
| 499 | |
| 500 | if obj != nil && obj.flags&otFunction != 0 && h.a.atFuncs[obj.cgn.fn] { |
| 501 | // address-taken function |
| 502 | if debugHVNVerbose && h.log != nil { |
| 503 | fmt.Fprintf(h.log, "n%d is address-taken: %s\n", id, obj.cgn.fn) |
| 504 | } |
| 505 | h.markIndirect(onodeid(id), "A-T func identity") |
| 506 | id++ |
| 507 | sig := obj.cgn.fn.Signature |
| 508 | psize := h.a.sizeof(sig.Params()) |
| 509 | if sig.Recv() != nil { |
| 510 | psize += h.a.sizeof(sig.Recv().Type()) |
| 511 | } |
| 512 | for end := id + int(psize); id < end; id++ { |
| 513 | h.markIndirect(onodeid(id), "A-T func P-block") |
| 514 | } |
| 515 | id-- |
| 516 | continue |
| 517 | } |
| 518 | } |
| 519 | |
| 520 | // (c) all map objects' value fields. |
| 521 | for _, id := range h.a.mapValues { |
| 522 | h.markIndirect(onodeid(id), "makemap.value") |
| 523 | } |
| 524 | |
| 525 | // (d) all array element objects. |
| 526 | // TODO(adonovan): opt: can we do better? |
| 527 | for id := 0; id < h.N; id++ { |
| 528 | // Identity node for an object of array type? |
| 529 | if tArray, ok := h.a.nodes[id].typ.(*types.Array); ok { |
| 530 | // Mark the array element nodes indirect. |
| 531 | // (Skip past the identity field.) |
| 532 | for range h.a.flatten(tArray.Elem()) { |
| 533 | id++ |
| 534 | h.markIndirect(onodeid(id), "array elem") |
| 535 | } |
| 536 | } |
| 537 | } |
| 538 | } |
| 539 | |
| 540 | func (h *hvn) markIndirect(oid onodeid, comment string) { |
| 541 | h.onodes[oid].indirect = true |
| 542 | if debugHVNVerbose && h.log != nil { |
| 543 | fmt.Fprintf(h.log, "\to%d is indirect: %s\n", oid, comment) |
| 544 | } |
| 545 | } |
| 546 | |
| 547 | // Adds an edge dst-->src. |
| 548 | // Note the unusual convention: edges are dependency (contraflow) edges. |
| 549 | func (h *hvn) addEdge(odst, osrc onodeid) { |
| 550 | h.onodes[odst].edges.Insert(int(osrc)) |
| 551 | if debugHVNVerbose && h.log != nil { |
| 552 | fmt.Fprintf(h.log, "\to%d --> o%d\n", odst, osrc) |
| 553 | } |
| 554 | } |
| 555 | |
| 556 | func (h *hvn) addImplicitEdge(odst, osrc onodeid) { |
| 557 | h.onodes[odst].implicit.Insert(int(osrc)) |
| 558 | if debugHVNVerbose && h.log != nil { |
| 559 | fmt.Fprintf(h.log, "\to%d ~~> o%d\n", odst, osrc) |
| 560 | } |
| 561 | } |
| 562 | |
| 563 | // visit implements the depth-first search of Tarjan's SCC algorithm. |
| 564 | // Precondition: x is canonical. |
| 565 | func (h *hvn) visit(x onodeid) { |
| 566 | h.checkCanonical(x) |
| 567 | xo := h.onodes[x] |
| 568 | xo.index = h.index |
| 569 | xo.lowlink = h.index |
| 570 | h.index++ |
| 571 | |
| 572 | h.stack = append(h.stack, x) // push |
| 573 | assert(xo.scc == 0, "node revisited") |
| 574 | xo.scc = -1 |
| 575 | |
| 576 | var deps []int |
| 577 | deps = xo.edges.AppendTo(deps) |
| 578 | deps = xo.implicit.AppendTo(deps) |
| 579 | |
| 580 | for _, y := range deps { |
| 581 | // Loop invariant: x is canonical. |
| 582 | |
| 583 | y := h.find(onodeid(y)) |
| 584 | |
| 585 | if x == y { |
| 586 | continue // nodes already coalesced |
| 587 | } |
| 588 | |
| 589 | xo := h.onodes[x] |
| 590 | yo := h.onodes[y] |
| 591 | |
| 592 | switch { |
| 593 | case yo.scc > 0: |
| 594 | // y is already a collapsed SCC |
| 595 | |
| 596 | case yo.scc < 0: |
| 597 | // y is on the stack, and thus in the current SCC. |
| 598 | if yo.index < xo.lowlink { |
| 599 | xo.lowlink = yo.index |
| 600 | } |
| 601 | |
| 602 | default: |
| 603 | // y is unvisited; visit it now. |
| 604 | h.visit(y) |
| 605 | // Note: x and y are now non-canonical. |
| 606 | |
| 607 | x = h.find(onodeid(x)) |
| 608 | |
| 609 | if yo.lowlink < xo.lowlink { |
| 610 | xo.lowlink = yo.lowlink |
| 611 | } |
| 612 | } |
| 613 | } |
| 614 | h.checkCanonical(x) |
| 615 | |
| 616 | // Is x the root of an SCC? |
| 617 | if xo.lowlink == xo.index { |
| 618 | // Coalesce all nodes in the SCC. |
| 619 | if debugHVNVerbose && h.log != nil { |
| 620 | fmt.Fprintf(h.log, "scc o%d\n", x) |
| 621 | } |
| 622 | for { |
| 623 | // Pop y from stack. |
| 624 | i := len(h.stack) - 1 |
| 625 | y := h.stack[i] |
| 626 | h.stack = h.stack[:i] |
| 627 | |
| 628 | h.checkCanonical(x) |
| 629 | xo := h.onodes[x] |
| 630 | h.checkCanonical(y) |
| 631 | yo := h.onodes[y] |
| 632 | |
| 633 | if xo == yo { |
| 634 | // SCC is complete. |
| 635 | xo.scc = 1 |
| 636 | h.labelSCC(x) |
| 637 | break |
| 638 | } |
| 639 | h.coalesce(x, y) |
| 640 | } |
| 641 | } |
| 642 | } |
| 643 | |
| 644 | // Precondition: x is canonical. |
| 645 | func (h *hvn) labelSCC(x onodeid) { |
| 646 | h.checkCanonical(x) |
| 647 | xo := h.onodes[x] |
| 648 | xpe := &xo.peLabels |
| 649 | |
| 650 | // All indirect nodes get new labels. |
| 651 | if xo.indirect { |
| 652 | label := h.nextLabel() |
| 653 | if debugHVNVerbose && h.log != nil { |
| 654 | fmt.Fprintf(h.log, "\tcreate p%d: indirect SCC\n", label) |
| 655 | fmt.Fprintf(h.log, "\to%d has p%d\n", x, label) |
| 656 | } |
| 657 | |
| 658 | // Remove pre-labeling, in case a direct pre-labeled node was |
| 659 | // merged with an indirect one. |
| 660 | xpe.Clear() |
| 661 | xpe.Insert(int(label)) |
| 662 | |
| 663 | return |
| 664 | } |
| 665 | |
| 666 | // Invariant: all peLabels sets are non-empty. |
| 667 | // Those that are logically empty contain zero as their sole element. |
| 668 | // No other sets contains zero. |
| 669 | |
| 670 | // Find all labels coming in to the coalesced SCC node. |
| 671 | for _, y := range xo.edges.AppendTo(nil) { |
| 672 | y := h.find(onodeid(y)) |
| 673 | if y == x { |
| 674 | continue // already coalesced |
| 675 | } |
| 676 | ype := &h.onodes[y].peLabels |
| 677 | if debugHVNVerbose && h.log != nil { |
| 678 | fmt.Fprintf(h.log, "\tedge from o%d = %s\n", y, ype) |
| 679 | } |
| 680 | |
| 681 | if ype.IsEmpty() { |
| 682 | if debugHVNVerbose && h.log != nil { |
| 683 | fmt.Fprintf(h.log, "\tnode has no PE label\n") |
| 684 | } |
| 685 | } |
| 686 | assert(!ype.IsEmpty(), "incoming node has no PE label") |
| 687 | |
| 688 | if ype.Has(0) { |
| 689 | // {0} represents a non-pointer. |
| 690 | assert(ype.Len() == 1, "PE set contains {0, ...}") |
| 691 | } else { |
| 692 | xpe.UnionWith(ype) |
| 693 | } |
| 694 | } |
| 695 | |
| 696 | switch xpe.Len() { |
| 697 | case 0: |
| 698 | // SCC has no incoming non-zero PE labels: it is a non-pointer. |
| 699 | xpe.Insert(0) |
| 700 | |
| 701 | case 1: |
| 702 | // already a singleton |
| 703 | |
| 704 | default: |
| 705 | // SCC has multiple incoming non-zero PE labels. |
| 706 | // Find the canonical label representing this set. |
| 707 | // We use String() as a fingerprint consistent with Equals(). |
| 708 | key := xpe.String() |
| 709 | label, ok := h.hvnLabel[key] |
| 710 | if !ok { |
| 711 | label = h.nextLabel() |
| 712 | if debugHVNVerbose && h.log != nil { |
| 713 | fmt.Fprintf(h.log, "\tcreate p%d: union %s\n", label, xpe.String()) |
| 714 | } |
| 715 | h.hvnLabel[key] = label |
| 716 | } |
| 717 | xpe.Clear() |
| 718 | xpe.Insert(int(label)) |
| 719 | } |
| 720 | |
| 721 | if debugHVNVerbose && h.log != nil { |
| 722 | fmt.Fprintf(h.log, "\to%d has p%d\n", x, xpe.Min()) |
| 723 | } |
| 724 | } |
| 725 | |
| 726 | // coalesce combines two nodes in the offline constraint graph. |
| 727 | // Precondition: x and y are canonical. |
| 728 | func (h *hvn) coalesce(x, y onodeid) { |
| 729 | xo := h.onodes[x] |
| 730 | yo := h.onodes[y] |
| 731 | |
| 732 | // x becomes y's canonical representative. |
| 733 | yo.rep = x |
| 734 | |
| 735 | if debugHVNVerbose && h.log != nil { |
| 736 | fmt.Fprintf(h.log, "\tcoalesce o%d into o%d\n", y, x) |
| 737 | } |
| 738 | |
| 739 | // x accumulates y's edges. |
| 740 | xo.edges.UnionWith(&yo.edges) |
| 741 | yo.edges.Clear() |
| 742 | |
| 743 | // x accumulates y's implicit edges. |
| 744 | xo.implicit.UnionWith(&yo.implicit) |
| 745 | yo.implicit.Clear() |
| 746 | |
| 747 | // x accumulates y's pointer-equivalence labels. |
| 748 | xo.peLabels.UnionWith(&yo.peLabels) |
| 749 | yo.peLabels.Clear() |
| 750 | |
| 751 | // x accumulates y's indirect flag. |
| 752 | if yo.indirect { |
| 753 | xo.indirect = true |
| 754 | } |
| 755 | } |
| 756 | |
| 757 | // simplify computes a degenerate renumbering of nodeids from the PE |
| 758 | // labels assigned by the hvn, and uses it to simplify the main |
| 759 | // constraint graph, eliminating non-pointer nodes and duplicate |
| 760 | // constraints. |
| 761 | func (h *hvn) simplify() { |
| 762 | // canon maps each peLabel to its canonical main node. |
| 763 | canon := make([]nodeid, h.label) |
| 764 | for i := range canon { |
| 765 | canon[i] = nodeid(h.N) // indicates "unset" |
| 766 | } |
| 767 | |
| 768 | // mapping maps each main node index to the index of the canonical node. |
| 769 | mapping := make([]nodeid, len(h.a.nodes)) |
| 770 | |
| 771 | for id := range h.a.nodes { |
| 772 | id := nodeid(id) |
| 773 | if id == 0 { |
| 774 | canon[0] = 0 |
| 775 | mapping[0] = 0 |
| 776 | continue |
| 777 | } |
| 778 | oid := h.find(onodeid(id)) |
| 779 | peLabels := &h.onodes[oid].peLabels |
| 780 | assert(peLabels.Len() == 1, "PE class is not a singleton") |
| 781 | label := peLabel(peLabels.Min()) |
| 782 | |
| 783 | canonID := canon[label] |
| 784 | if canonID == nodeid(h.N) { |
| 785 | // id becomes the representative of the PE label. |
| 786 | canonID = id |
| 787 | canon[label] = canonID |
| 788 | |
| 789 | if h.a.log != nil { |
| 790 | fmt.Fprintf(h.a.log, "\tpts(n%d) is canonical : \t(%s)\n", |
| 791 | id, h.a.nodes[id].typ) |
| 792 | } |
| 793 | |
| 794 | } else { |
| 795 | // Link the solver states for the two nodes. |
| 796 | assert(h.a.nodes[canonID].solve != nil, "missing solver state") |
| 797 | h.a.nodes[id].solve = h.a.nodes[canonID].solve |
| 798 | |
| 799 | if h.a.log != nil { |
| 800 | // TODO(adonovan): debug: reorganize the log so it prints |
| 801 | // one line: |
| 802 | // pe y = x1, ..., xn |
| 803 | // for each canonical y. Requires allocation. |
| 804 | fmt.Fprintf(h.a.log, "\tpts(n%d) = pts(n%d) : %s\n", |
| 805 | id, canonID, h.a.nodes[id].typ) |
| 806 | } |
| 807 | } |
| 808 | |
| 809 | mapping[id] = canonID |
| 810 | } |
| 811 | |
| 812 | // Renumber the constraints, eliminate duplicates, and eliminate |
| 813 | // any containing non-pointers (n0). |
| 814 | addrs := make(map[addrConstraint]bool) |
| 815 | copys := make(map[copyConstraint]bool) |
| 816 | loads := make(map[loadConstraint]bool) |
| 817 | stores := make(map[storeConstraint]bool) |
| 818 | offsetAddrs := make(map[offsetAddrConstraint]bool) |
| 819 | untags := make(map[untagConstraint]bool) |
| 820 | typeFilters := make(map[typeFilterConstraint]bool) |
| 821 | invokes := make(map[invokeConstraint]bool) |
| 822 | |
| 823 | nbefore := len(h.a.constraints) |
| 824 | cc := h.a.constraints[:0] // in-situ compaction |
| 825 | for _, c := range h.a.constraints { |
| 826 | // Renumber. |
| 827 | switch c := c.(type) { |
| 828 | case *addrConstraint: |
| 829 | // Don't renumber c.src since it is the label of |
| 830 | // an addressable object and will appear in PT sets. |
| 831 | c.dst = mapping[c.dst] |
| 832 | default: |
| 833 | c.renumber(mapping) |
| 834 | } |
| 835 | |
| 836 | if c.ptr() == 0 { |
| 837 | continue // skip: constraint attached to non-pointer |
| 838 | } |
| 839 | |
| 840 | var dup bool |
| 841 | switch c := c.(type) { |
| 842 | case *addrConstraint: |
| 843 | _, dup = addrs[*c] |
| 844 | addrs[*c] = true |
| 845 | |
| 846 | case *copyConstraint: |
| 847 | if c.src == c.dst { |
| 848 | continue // skip degenerate copies |
| 849 | } |
| 850 | if c.src == 0 { |
| 851 | continue // skip copy from non-pointer |
| 852 | } |
| 853 | _, dup = copys[*c] |
| 854 | copys[*c] = true |
| 855 | |
| 856 | case *loadConstraint: |
| 857 | if c.src == 0 { |
| 858 | continue // skip load from non-pointer |
| 859 | } |
| 860 | _, dup = loads[*c] |
| 861 | loads[*c] = true |
| 862 | |
| 863 | case *storeConstraint: |
| 864 | if c.src == 0 { |
| 865 | continue // skip store from non-pointer |
| 866 | } |
| 867 | _, dup = stores[*c] |
| 868 | stores[*c] = true |
| 869 | |
| 870 | case *offsetAddrConstraint: |
| 871 | if c.src == 0 { |
| 872 | continue // skip offset from non-pointer |
| 873 | } |
| 874 | _, dup = offsetAddrs[*c] |
| 875 | offsetAddrs[*c] = true |
| 876 | |
| 877 | case *untagConstraint: |
| 878 | if c.src == 0 { |
| 879 | continue // skip untag of non-pointer |
| 880 | } |
| 881 | _, dup = untags[*c] |
| 882 | untags[*c] = true |
| 883 | |
| 884 | case *typeFilterConstraint: |
| 885 | if c.src == 0 { |
| 886 | continue // skip filter of non-pointer |
| 887 | } |
| 888 | _, dup = typeFilters[*c] |
| 889 | typeFilters[*c] = true |
| 890 | |
| 891 | case *invokeConstraint: |
| 892 | if c.params == 0 { |
| 893 | panic("non-pointer invoke.params") |
| 894 | } |
| 895 | if c.iface == 0 { |
| 896 | continue // skip invoke on non-pointer |
| 897 | } |
| 898 | _, dup = invokes[*c] |
| 899 | invokes[*c] = true |
| 900 | |
| 901 | default: |
| 902 | // We don't bother de-duping advanced constraints |
| 903 | // (e.g. reflection) since they are uncommon. |
| 904 | |
| 905 | // Eliminate constraints containing non-pointer nodeids. |
| 906 | // |
| 907 | // We use reflection to find the fields to avoid |
| 908 | // adding yet another method to constraint. |
| 909 | // |
| 910 | // TODO(adonovan): experiment with a constraint |
| 911 | // method that returns a slice of pointers to |
| 912 | // nodeids fields to enable uniform iteration; |
| 913 | // the renumber() method could be removed and |
| 914 | // implemented using the new one. |
| 915 | // |
| 916 | // TODO(adonovan): opt: this is unsound since |
| 917 | // some constraints still have an effect if one |
| 918 | // of the operands is zero: rVCall, rVMapIndex, |
| 919 | // rvSetMapIndex. Handle them specially. |
| 920 | rtNodeid := reflect.TypeOf(nodeid(0)) |
| 921 | x := reflect.ValueOf(c).Elem() |
| 922 | for i, nf := 0, x.NumField(); i < nf; i++ { |
| 923 | f := x.Field(i) |
| 924 | if f.Type() == rtNodeid { |
| 925 | if f.Uint() == 0 { |
| 926 | dup = true // skip it |
| 927 | break |
| 928 | } |
| 929 | } |
| 930 | } |
| 931 | } |
| 932 | if dup { |
| 933 | continue // skip duplicates |
| 934 | } |
| 935 | |
| 936 | cc = append(cc, c) |
| 937 | } |
| 938 | h.a.constraints = cc |
| 939 | |
| 940 | if h.log != nil { |
| 941 | fmt.Fprintf(h.log, "#constraints: was %d, now %d\n", nbefore, len(h.a.constraints)) |
| 942 | } |
| 943 | } |
| 944 | |
| 945 | // find returns the canonical onodeid for x. |
| 946 | // (The onodes form a disjoint set forest.) |
| 947 | func (h *hvn) find(x onodeid) onodeid { |
| 948 | // TODO(adonovan): opt: this is a CPU hotspot. Try "union by rank". |
| 949 | xo := h.onodes[x] |
| 950 | rep := xo.rep |
| 951 | if rep != x { |
| 952 | rep = h.find(rep) // simple path compression |
| 953 | xo.rep = rep |
| 954 | } |
| 955 | return rep |
| 956 | } |
| 957 | |
| 958 | func (h *hvn) checkCanonical(x onodeid) { |
| 959 | if debugHVN { |
| 960 | assert(x == h.find(x), "not canonical") |
| 961 | } |
| 962 | } |
| 963 | |
| 964 | func assert(p bool, msg string) { |
| 965 | if debugHVN && !p { |
| 966 | panic("assertion failed: " + msg) |
| 967 | } |
| 968 | } |
| 969 |
Members