--- /dev/null
+// 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 implements Hash-Value Numbering (HVN), a pre-solver
+// constraint optimization described in Hardekopf & Lin, SAS'07 (see
+// doc.go) that analyses the graph topology to determine which sets of
+// variables are "pointer equivalent" (PE), i.e. must have identical
+// points-to sets in the solution.
+//
+// A separate ("offline") graph is constructed. Its nodes are those of
+// the main-graph, plus an additional node *X for each pointer node X.
+// With this graph we can reason about the unknown points-to set of
+// dereferenced pointers. (We do not generalize this to represent
+// unknown fields x->f, perhaps because such fields would be numerous,
+// though it might be worth an experiment.)
+//
+// Nodes whose points-to relations are not entirely captured by the
+// graph are marked as "indirect": the *X nodes, the parameters of
+// address-taken functions (which includes all functions in method
+// sets), or nodes updated by the solver rules for reflection, etc.
+//
+// All addr (y=&x) nodes are initially assigned a pointer-equivalence
+// (PE) label equal to x's nodeid in the main graph. (These are the
+// only PE labels that are less than len(a.nodes).)
+//
+// All offsetAddr (y=&x.f) constraints are initially assigned a PE
+// label; such labels are memoized, keyed by (x, f), so that equivalent
+// nodes y as assigned the same label.
+//
+// Then we process each strongly connected component (SCC) of the graph
+// in topological order, assigning it a PE label based on the set P of
+// PE labels that flow to it from its immediate dependencies.
+//
+// If any node in P is "indirect", the entire SCC is assigned a fresh PE
+// label. Otherwise:
+//
+// |P|=0 if P is empty, all nodes in the SCC are non-pointers (e.g.
+// uninitialized variables, or formal params of dead functions)
+// and the SCC is assigned the PE label of zero.
+//
+// |P|=1 if P is a singleton, the SCC is assigned the same label as the
+// sole element of P.
+//
+// |P|>1 if P contains multiple labels, a unique label representing P is
+// invented and recorded in an hash table, so that other
+// equivalent SCCs may also be assigned this label, akin to
+// conventional hash-value numbering in a compiler.
+//
+// Finally, a renumbering is computed such that each node is replaced by
+// the lowest-numbered node with the same PE label. All constraints are
+// renumbered, and any resulting duplicates are eliminated.
+//
+// The only nodes that are not renumbered are the objects x in addr
+// (y=&x) constraints, since the ids of these nodes (and fields derived
+// from them via offsetAddr rules) are the elements of all points-to
+// sets, so they must remain as they are if we want the same solution.
+//
+// The solverStates (node.solve) for nodes in the same equivalence class
+// are linked together so that all nodes in the class have the same
+// solution. This avoids the need to renumber nodeids buried in
+// Queries, cgnodes, etc (like (*analysis).renumber() does) since only
+// the solution is needed.
+//
+// The result of HVN is that the number of distinct nodes and
+// constraints is reduced, but the solution is identical (almost---see
+// CROSS-CHECK below). In particular, both linear and cyclic chains of
+// copies are each replaced by a single node.
+//
+// Nodes and constraints created "online" (e.g. while solving reflection
+// constraints) are not subject to this optimization.
+//
+// PERFORMANCE
+//
+// In two benchmarks (guru and godoc), HVN eliminates about two thirds
+// of nodes, the majority accounted for by non-pointers: nodes of
+// non-pointer type, pointers that remain nil, formal parameters of dead
+// functions, nodes of untracked types, etc. It also reduces the number
+// of constraints, also by about two thirds, and the solving time by
+// 30--42%, although we must pay about 15% for the running time of HVN
+// itself. The benefit is greater for larger applications.
+//
+// There are many possible optimizations to improve the performance:
+// * Use fewer than 1:1 onodes to main graph nodes: many of the onodes
+// we create are not needed.
+// * HU (HVN with Union---see paper): coalesce "union" peLabels when
+// their expanded-out sets are equal.
+// * HR (HVN with deReference---see paper): this will require that we
+// apply HVN until fixed point, which may need more bookkeeping of the
+// correspondence of main nodes to onodes.
+// * Location Equivalence (see paper): have points-to sets contain not
+// locations but location-equivalence class labels, each representing
+// a set of locations.
+// * HVN with field-sensitive ref: model each of the fields of a
+// pointer-to-struct.
+//
+// CROSS-CHECK
+//
+// To verify the soundness of the optimization, when the
+// debugHVNCrossCheck option is enabled, we run the solver twice, once
+// before and once after running HVN, dumping the solution to disk, and
+// then we compare the results. If they are not identical, the analysis
+// panics.
+//
+// The solution dumped to disk includes only the N*N submatrix of the
+// complete solution where N is the number of nodes after generation.
+// In other words, we ignore pointer variables and objects created by
+// the solver itself, since their numbering depends on the solver order,
+// which is affected by the optimization. In any case, that's the only
+// part the client cares about.
+//
+// The cross-check is too strict and may fail spuriously. Although the
+// H&L paper describing HVN states that the solutions obtained should be
+// identical, this is not the case in practice because HVN can collapse
+// cycles involving *p even when pts(p)={}. Consider this example
+// distilled from testdata/hello.go:
+//
+// var x T
+// func f(p **T) {
+// t0 = *p
+// ...
+// t1 = φ(t0, &x)
+// *p = t1
+// }
+//
+// If f is dead code, we get:
+// unoptimized: pts(p)={} pts(t0)={} pts(t1)={&x}
+// optimized: pts(p)={} pts(t0)=pts(t1)=pts(*p)={&x}
+//
+// It's hard to argue that this is a bug: the result is sound and the
+// loss of precision is inconsequential---f is dead code, after all.
+// But unfortunately it limits the usefulness of the cross-check since
+// failures must be carefully analyzed. Ben Hardekopf suggests (in
+// personal correspondence) some approaches to mitigating it:
+//
+// If there is a node with an HVN points-to set that is a superset
+// of the NORM points-to set, then either it's a bug or it's a
+// result of this issue. If it's a result of this issue, then in
+// the offline constraint graph there should be a REF node inside
+// some cycle that reaches this node, and in the NORM solution the
+// pointer being dereferenced by that REF node should be the empty
+// set. If that isn't true then this is a bug. If it is true, then
+// you can further check that in the NORM solution the "extra"
+// points-to info in the HVN solution does in fact come from that
+// purported cycle (if it doesn't, then this is still a bug). If
+// you're doing the further check then you'll need to do it for
+// each "extra" points-to element in the HVN points-to set.
+//
+// There are probably ways to optimize these checks by taking
+// advantage of graph properties. For example, extraneous points-to
+// info will flow through the graph and end up in many
+// nodes. Rather than checking every node with extra info, you
+// could probably work out the "origin point" of the extra info and
+// just check there. Note that the check in the first bullet is
+// looking for soundness bugs, while the check in the second bullet
+// is looking for precision bugs; depending on your needs, you may
+// care more about one than the other.
+//
+// which we should evaluate. The cross-check is nonetheless invaluable
+// for all but one of the programs in the pointer_test suite.
+
+import (
+ "fmt"
+ "go/types"
+ "io"
+ "reflect"
+
+ "golang.org/x/tools/container/intsets"
+)
+
+// A peLabel is a pointer-equivalence label: two nodes with the same
+// peLabel have identical points-to solutions.
+//
+// The numbers are allocated consecutively like so:
+// 0 not a pointer
+// 1..N-1 addrConstraints (equals the constraint's .src field, hence sparse)
+// ... offsetAddr constraints
+// ... SCCs (with indirect nodes or multiple inputs)
+//
+// Each PE label denotes a set of pointers containing a single addr, a
+// single offsetAddr, or some set of other PE labels.
+//
+type peLabel int
+
+type hvn struct {
+ a *analysis
+ N int // len(a.nodes) immediately after constraint generation
+ log io.Writer // (optional) log of HVN lemmas
+ onodes []*onode // nodes of the offline graph
+ label peLabel // the next available PE label
+ hvnLabel map[string]peLabel // hash-value numbering (PE label) for each set of onodeids
+ stack []onodeid // DFS stack
+ index int32 // next onode.index, from Tarjan's SCC algorithm
+
+ // For each distinct offsetAddrConstraint (src, offset) pair,
+ // offsetAddrLabels records a unique PE label >= N.
+ offsetAddrLabels map[offsetAddr]peLabel
+}
+
+// The index of an node in the offline graph.
+// (Currently the first N align with the main nodes,
+// but this may change with HRU.)
+type onodeid uint32
+
+// An onode is a node in the offline constraint graph.
+// (Where ambiguous, members of analysis.nodes are referred to as
+// "main graph" nodes.)
+//
+// Edges in the offline constraint graph (edges and implicit) point to
+// the source, i.e. against the flow of values: they are dependencies.
+// Implicit edges are used for SCC computation, but not for gathering
+// incoming labels.
+//
+type onode struct {
+ rep onodeid // index of representative of SCC in offline constraint graph
+
+ edges intsets.Sparse // constraint edges X-->Y (this onode is X)
+ implicit intsets.Sparse // implicit edges *X-->*Y (this onode is X)
+ peLabels intsets.Sparse // set of peLabels are pointer-equivalent to this one
+ indirect bool // node has points-to relations not represented in graph
+
+ // Tarjan's SCC algorithm
+ index, lowlink int32 // Tarjan numbering
+ scc int32 // -ve => on stack; 0 => unvisited; +ve => node is root of a found SCC
+}
+
+type offsetAddr struct {
+ ptr nodeid
+ offset uint32
+}
+
+// nextLabel issues the next unused pointer-equivalence label.
+func (h *hvn) nextLabel() peLabel {
+ h.label++
+ return h.label
+}
+
+// ref(X) returns the index of the onode for *X.
+func (h *hvn) ref(id onodeid) onodeid {
+ return id + onodeid(len(h.a.nodes))
+}
+
+// hvn computes pointer-equivalence labels (peLabels) using the Hash-based
+// Value Numbering (HVN) algorithm described in Hardekopf & Lin, SAS'07.
+//
+func (a *analysis) hvn() {
+ start("HVN")
+
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\n\n==== Pointer equivalence optimization\n\n")
+ }
+
+ h := hvn{
+ a: a,
+ N: len(a.nodes),
+ log: a.log,
+ hvnLabel: make(map[string]peLabel),
+ offsetAddrLabels: make(map[offsetAddr]peLabel),
+ }
+
+ if h.log != nil {
+ fmt.Fprintf(h.log, "\nCreating offline graph nodes...\n")
+ }
+
+ // Create offline nodes. The first N nodes correspond to main
+ // graph nodes; the next N are their corresponding ref() nodes.
+ h.onodes = make([]*onode, 2*h.N)
+ for id := range a.nodes {
+ id := onodeid(id)
+ h.onodes[id] = &onode{}
+ h.onodes[h.ref(id)] = &onode{indirect: true}
+ }
+
+ // Each node initially represents just itself.
+ for id, o := range h.onodes {
+ o.rep = onodeid(id)
+ }
+
+ h.markIndirectNodes()
+
+ // Reserve the first N PE labels for addrConstraints.
+ h.label = peLabel(h.N)
+
+ // Add offline constraint edges.
+ if h.log != nil {
+ fmt.Fprintf(h.log, "\nAdding offline graph edges...\n")
+ }
+ for _, c := range a.constraints {
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "; %s\n", c)
+ }
+ c.presolve(&h)
+ }
+
+ // Find and collapse SCCs.
+ if h.log != nil {
+ fmt.Fprintf(h.log, "\nFinding SCCs...\n")
+ }
+ h.index = 1
+ for id, o := range h.onodes {
+ if id > 0 && o.index == 0 {
+ // Start depth-first search at each unvisited node.
+ h.visit(onodeid(id))
+ }
+ }
+
+ // Dump the solution
+ // (NB: somewhat redundant with logging from simplify().)
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\nPointer equivalences:\n")
+ for id, o := range h.onodes {
+ if id == 0 {
+ continue
+ }
+ if id == int(h.N) {
+ fmt.Fprintf(h.log, "---\n")
+ }
+ fmt.Fprintf(h.log, "o%d\t", id)
+ if o.rep != onodeid(id) {
+ fmt.Fprintf(h.log, "rep=o%d", o.rep)
+ } else {
+ fmt.Fprintf(h.log, "p%d", o.peLabels.Min())
+ if o.indirect {
+ fmt.Fprint(h.log, " indirect")
+ }
+ }
+ fmt.Fprintln(h.log)
+ }
+ }
+
+ // Simplify the main constraint graph
+ h.simplify()
+
+ a.showCounts()
+
+ stop("HVN")
+}
+
+// ---- constraint-specific rules ----
+
+// dst := &src
+func (c *addrConstraint) presolve(h *hvn) {
+ // Each object (src) is an initial PE label.
+ label := peLabel(c.src) // label < N
+ if debugHVNVerbose && h.log != nil {
+ // duplicate log messages are possible
+ fmt.Fprintf(h.log, "\tcreate p%d: {&n%d}\n", label, c.src)
+ }
+ odst := onodeid(c.dst)
+ osrc := onodeid(c.src)
+
+ // Assign dst this label.
+ h.onodes[odst].peLabels.Insert(int(label))
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d has p%d\n", odst, label)
+ }
+
+ h.addImplicitEdge(h.ref(odst), osrc) // *dst ~~> src.
+}
+
+// dst = src
+func (c *copyConstraint) presolve(h *hvn) {
+ odst := onodeid(c.dst)
+ osrc := onodeid(c.src)
+ h.addEdge(odst, osrc) // dst --> src
+ h.addImplicitEdge(h.ref(odst), h.ref(osrc)) // *dst ~~> *src
+}
+
+// dst = *src + offset
+func (c *loadConstraint) presolve(h *hvn) {
+ odst := onodeid(c.dst)
+ osrc := onodeid(c.src)
+ if c.offset == 0 {
+ h.addEdge(odst, h.ref(osrc)) // dst --> *src
+ } else {
+ // We don't interpret load-with-offset, e.g. results
+ // of map value lookup, R-block of dynamic call, slice
+ // copy/append, reflection.
+ h.markIndirect(odst, "load with offset")
+ }
+}
+
+// *dst + offset = src
+func (c *storeConstraint) presolve(h *hvn) {
+ odst := onodeid(c.dst)
+ osrc := onodeid(c.src)
+ if c.offset == 0 {
+ h.onodes[h.ref(odst)].edges.Insert(int(osrc)) // *dst --> src
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d --> o%d\n", h.ref(odst), osrc)
+ }
+ }
+ // We don't interpret store-with-offset.
+ // See discussion of soundness at markIndirectNodes.
+}
+
+// dst = &src.offset
+func (c *offsetAddrConstraint) presolve(h *hvn) {
+ // Give each distinct (addr, offset) pair a fresh PE label.
+ // The cache performs CSE, effectively.
+ key := offsetAddr{c.src, c.offset}
+ label, ok := h.offsetAddrLabels[key]
+ if !ok {
+ label = h.nextLabel()
+ h.offsetAddrLabels[key] = label
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tcreate p%d: {&n%d.#%d}\n",
+ label, c.src, c.offset)
+ }
+ }
+
+ // Assign dst this label.
+ h.onodes[c.dst].peLabels.Insert(int(label))
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d has p%d\n", c.dst, label)
+ }
+}
+
+// dst = src.(typ) where typ is an interface
+func (c *typeFilterConstraint) presolve(h *hvn) {
+ h.markIndirect(onodeid(c.dst), "typeFilter result")
+}
+
+// dst = src.(typ) where typ is concrete
+func (c *untagConstraint) presolve(h *hvn) {
+ odst := onodeid(c.dst)
+ for end := odst + onodeid(h.a.sizeof(c.typ)); odst < end; odst++ {
+ h.markIndirect(odst, "untag result")
+ }
+}
+
+// dst = src.method(c.params...)
+func (c *invokeConstraint) presolve(h *hvn) {
+ // All methods are address-taken functions, so
+ // their formal P-blocks were already marked indirect.
+
+ // Mark the caller's targets node as indirect.
+ sig := c.method.Type().(*types.Signature)
+ id := c.params
+ h.markIndirect(onodeid(c.params), "invoke targets node")
+ id++
+
+ id += nodeid(h.a.sizeof(sig.Params()))
+
+ // Mark the caller's R-block as indirect.
+ end := id + nodeid(h.a.sizeof(sig.Results()))
+ for id < end {
+ h.markIndirect(onodeid(id), "invoke R-block")
+ id++
+ }
+}
+
+// markIndirectNodes marks as indirect nodes whose points-to relations
+// are not entirely captured by the offline graph, including:
+//
+// (a) All address-taken nodes (including the following nodes within
+// the same object). This is described in the paper.
+//
+// The most subtle cause of indirect nodes is the generation of
+// store-with-offset constraints since the offline graph doesn't
+// represent them. A global audit of constraint generation reveals the
+// following uses of store-with-offset:
+//
+// (b) genDynamicCall, for P-blocks of dynamically called functions,
+// to which dynamic copy edges will be added to them during
+// solving: from storeConstraint for standalone functions,
+// and from invokeConstraint for methods.
+// All such P-blocks must be marked indirect.
+// (c) MakeUpdate, to update the value part of a map object.
+// All MakeMap objects's value parts must be marked indirect.
+// (d) copyElems, to update the destination array.
+// All array elements must be marked indirect.
+//
+// Not all indirect marking happens here. ref() nodes are marked
+// indirect at construction, and each constraint's presolve() method may
+// mark additional nodes.
+//
+func (h *hvn) markIndirectNodes() {
+ // (a) all address-taken nodes, plus all nodes following them
+ // within the same object, since these may be indirectly
+ // stored or address-taken.
+ for _, c := range h.a.constraints {
+ if c, ok := c.(*addrConstraint); ok {
+ start := h.a.enclosingObj(c.src)
+ end := start + nodeid(h.a.nodes[start].obj.size)
+ for id := c.src; id < end; id++ {
+ h.markIndirect(onodeid(id), "A-T object")
+ }
+ }
+ }
+
+ // (b) P-blocks of all address-taken functions.
+ for id := 0; id < h.N; id++ {
+ obj := h.a.nodes[id].obj
+
+ // TODO(adonovan): opt: if obj.cgn.fn is a method and
+ // obj.cgn is not its shared contour, this is an
+ // "inlined" static method call. We needn't consider it
+ // address-taken since no invokeConstraint will affect it.
+
+ if obj != nil && obj.flags&otFunction != 0 && h.a.atFuncs[obj.cgn.fn] {
+ // address-taken function
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "n%d is address-taken: %s\n", id, obj.cgn.fn)
+ }
+ h.markIndirect(onodeid(id), "A-T func identity")
+ id++
+ sig := obj.cgn.fn.Signature
+ psize := h.a.sizeof(sig.Params())
+ if sig.Recv() != nil {
+ psize += h.a.sizeof(sig.Recv().Type())
+ }
+ for end := id + int(psize); id < end; id++ {
+ h.markIndirect(onodeid(id), "A-T func P-block")
+ }
+ id--
+ continue
+ }
+ }
+
+ // (c) all map objects' value fields.
+ for _, id := range h.a.mapValues {
+ h.markIndirect(onodeid(id), "makemap.value")
+ }
+
+ // (d) all array element objects.
+ // TODO(adonovan): opt: can we do better?
+ for id := 0; id < h.N; id++ {
+ // Identity node for an object of array type?
+ if tArray, ok := h.a.nodes[id].typ.(*types.Array); ok {
+ // Mark the array element nodes indirect.
+ // (Skip past the identity field.)
+ for range h.a.flatten(tArray.Elem()) {
+ id++
+ h.markIndirect(onodeid(id), "array elem")
+ }
+ }
+ }
+}
+
+func (h *hvn) markIndirect(oid onodeid, comment string) {
+ h.onodes[oid].indirect = true
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d is indirect: %s\n", oid, comment)
+ }
+}
+
+// Adds an edge dst-->src.
+// Note the unusual convention: edges are dependency (contraflow) edges.
+func (h *hvn) addEdge(odst, osrc onodeid) {
+ h.onodes[odst].edges.Insert(int(osrc))
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d --> o%d\n", odst, osrc)
+ }
+}
+
+func (h *hvn) addImplicitEdge(odst, osrc onodeid) {
+ h.onodes[odst].implicit.Insert(int(osrc))
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d ~~> o%d\n", odst, osrc)
+ }
+}
+
+// visit implements the depth-first search of Tarjan's SCC algorithm.
+// Precondition: x is canonical.
+func (h *hvn) visit(x onodeid) {
+ h.checkCanonical(x)
+ xo := h.onodes[x]
+ xo.index = h.index
+ xo.lowlink = h.index
+ h.index++
+
+ h.stack = append(h.stack, x) // push
+ assert(xo.scc == 0, "node revisited")
+ xo.scc = -1
+
+ var deps []int
+ deps = xo.edges.AppendTo(deps)
+ deps = xo.implicit.AppendTo(deps)
+
+ for _, y := range deps {
+ // Loop invariant: x is canonical.
+
+ y := h.find(onodeid(y))
+
+ if x == y {
+ continue // nodes already coalesced
+ }
+
+ xo := h.onodes[x]
+ yo := h.onodes[y]
+
+ switch {
+ case yo.scc > 0:
+ // y is already a collapsed SCC
+
+ case yo.scc < 0:
+ // y is on the stack, and thus in the current SCC.
+ if yo.index < xo.lowlink {
+ xo.lowlink = yo.index
+ }
+
+ default:
+ // y is unvisited; visit it now.
+ h.visit(y)
+ // Note: x and y are now non-canonical.
+
+ x = h.find(onodeid(x))
+
+ if yo.lowlink < xo.lowlink {
+ xo.lowlink = yo.lowlink
+ }
+ }
+ }
+ h.checkCanonical(x)
+
+ // Is x the root of an SCC?
+ if xo.lowlink == xo.index {
+ // Coalesce all nodes in the SCC.
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "scc o%d\n", x)
+ }
+ for {
+ // Pop y from stack.
+ i := len(h.stack) - 1
+ y := h.stack[i]
+ h.stack = h.stack[:i]
+
+ h.checkCanonical(x)
+ xo := h.onodes[x]
+ h.checkCanonical(y)
+ yo := h.onodes[y]
+
+ if xo == yo {
+ // SCC is complete.
+ xo.scc = 1
+ h.labelSCC(x)
+ break
+ }
+ h.coalesce(x, y)
+ }
+ }
+}
+
+// Precondition: x is canonical.
+func (h *hvn) labelSCC(x onodeid) {
+ h.checkCanonical(x)
+ xo := h.onodes[x]
+ xpe := &xo.peLabels
+
+ // All indirect nodes get new labels.
+ if xo.indirect {
+ label := h.nextLabel()
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tcreate p%d: indirect SCC\n", label)
+ fmt.Fprintf(h.log, "\to%d has p%d\n", x, label)
+ }
+
+ // Remove pre-labeling, in case a direct pre-labeled node was
+ // merged with an indirect one.
+ xpe.Clear()
+ xpe.Insert(int(label))
+
+ return
+ }
+
+ // Invariant: all peLabels sets are non-empty.
+ // Those that are logically empty contain zero as their sole element.
+ // No other sets contains zero.
+
+ // Find all labels coming in to the coalesced SCC node.
+ for _, y := range xo.edges.AppendTo(nil) {
+ y := h.find(onodeid(y))
+ if y == x {
+ continue // already coalesced
+ }
+ ype := &h.onodes[y].peLabels
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tedge from o%d = %s\n", y, ype)
+ }
+
+ if ype.IsEmpty() {
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tnode has no PE label\n")
+ }
+ }
+ assert(!ype.IsEmpty(), "incoming node has no PE label")
+
+ if ype.Has(0) {
+ // {0} represents a non-pointer.
+ assert(ype.Len() == 1, "PE set contains {0, ...}")
+ } else {
+ xpe.UnionWith(ype)
+ }
+ }
+
+ switch xpe.Len() {
+ case 0:
+ // SCC has no incoming non-zero PE labels: it is a non-pointer.
+ xpe.Insert(0)
+
+ case 1:
+ // already a singleton
+
+ default:
+ // SCC has multiple incoming non-zero PE labels.
+ // Find the canonical label representing this set.
+ // We use String() as a fingerprint consistent with Equals().
+ key := xpe.String()
+ label, ok := h.hvnLabel[key]
+ if !ok {
+ label = h.nextLabel()
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tcreate p%d: union %s\n", label, xpe.String())
+ }
+ h.hvnLabel[key] = label
+ }
+ xpe.Clear()
+ xpe.Insert(int(label))
+ }
+
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\to%d has p%d\n", x, xpe.Min())
+ }
+}
+
+// coalesce combines two nodes in the offline constraint graph.
+// Precondition: x and y are canonical.
+func (h *hvn) coalesce(x, y onodeid) {
+ xo := h.onodes[x]
+ yo := h.onodes[y]
+
+ // x becomes y's canonical representative.
+ yo.rep = x
+
+ if debugHVNVerbose && h.log != nil {
+ fmt.Fprintf(h.log, "\tcoalesce o%d into o%d\n", y, x)
+ }
+
+ // x accumulates y's edges.
+ xo.edges.UnionWith(&yo.edges)
+ yo.edges.Clear()
+
+ // x accumulates y's implicit edges.
+ xo.implicit.UnionWith(&yo.implicit)
+ yo.implicit.Clear()
+
+ // x accumulates y's pointer-equivalence labels.
+ xo.peLabels.UnionWith(&yo.peLabels)
+ yo.peLabels.Clear()
+
+ // x accumulates y's indirect flag.
+ if yo.indirect {
+ xo.indirect = true
+ }
+}
+
+// simplify computes a degenerate renumbering of nodeids from the PE
+// labels assigned by the hvn, and uses it to simplify the main
+// constraint graph, eliminating non-pointer nodes and duplicate
+// constraints.
+//
+func (h *hvn) simplify() {
+ // canon maps each peLabel to its canonical main node.
+ canon := make([]nodeid, h.label)
+ for i := range canon {
+ canon[i] = nodeid(h.N) // indicates "unset"
+ }
+
+ // mapping maps each main node index to the index of the canonical node.
+ mapping := make([]nodeid, len(h.a.nodes))
+
+ for id := range h.a.nodes {
+ id := nodeid(id)
+ if id == 0 {
+ canon[0] = 0
+ mapping[0] = 0
+ continue
+ }
+ oid := h.find(onodeid(id))
+ peLabels := &h.onodes[oid].peLabels
+ assert(peLabels.Len() == 1, "PE class is not a singleton")
+ label := peLabel(peLabels.Min())
+
+ canonID := canon[label]
+ if canonID == nodeid(h.N) {
+ // id becomes the representative of the PE label.
+ canonID = id
+ canon[label] = canonID
+
+ if h.a.log != nil {
+ fmt.Fprintf(h.a.log, "\tpts(n%d) is canonical : \t(%s)\n",
+ id, h.a.nodes[id].typ)
+ }
+
+ } else {
+ // Link the solver states for the two nodes.
+ assert(h.a.nodes[canonID].solve != nil, "missing solver state")
+ h.a.nodes[id].solve = h.a.nodes[canonID].solve
+
+ if h.a.log != nil {
+ // TODO(adonovan): debug: reorganize the log so it prints
+ // one line:
+ // pe y = x1, ..., xn
+ // for each canonical y. Requires allocation.
+ fmt.Fprintf(h.a.log, "\tpts(n%d) = pts(n%d) : %s\n",
+ id, canonID, h.a.nodes[id].typ)
+ }
+ }
+
+ mapping[id] = canonID
+ }
+
+ // Renumber the constraints, eliminate duplicates, and eliminate
+ // any containing non-pointers (n0).
+ addrs := make(map[addrConstraint]bool)
+ copys := make(map[copyConstraint]bool)
+ loads := make(map[loadConstraint]bool)
+ stores := make(map[storeConstraint]bool)
+ offsetAddrs := make(map[offsetAddrConstraint]bool)
+ untags := make(map[untagConstraint]bool)
+ typeFilters := make(map[typeFilterConstraint]bool)
+ invokes := make(map[invokeConstraint]bool)
+
+ nbefore := len(h.a.constraints)
+ cc := h.a.constraints[:0] // in-situ compaction
+ for _, c := range h.a.constraints {
+ // Renumber.
+ switch c := c.(type) {
+ case *addrConstraint:
+ // Don't renumber c.src since it is the label of
+ // an addressable object and will appear in PT sets.
+ c.dst = mapping[c.dst]
+ default:
+ c.renumber(mapping)
+ }
+
+ if c.ptr() == 0 {
+ continue // skip: constraint attached to non-pointer
+ }
+
+ var dup bool
+ switch c := c.(type) {
+ case *addrConstraint:
+ _, dup = addrs[*c]
+ addrs[*c] = true
+
+ case *copyConstraint:
+ if c.src == c.dst {
+ continue // skip degenerate copies
+ }
+ if c.src == 0 {
+ continue // skip copy from non-pointer
+ }
+ _, dup = copys[*c]
+ copys[*c] = true
+
+ case *loadConstraint:
+ if c.src == 0 {
+ continue // skip load from non-pointer
+ }
+ _, dup = loads[*c]
+ loads[*c] = true
+
+ case *storeConstraint:
+ if c.src == 0 {
+ continue // skip store from non-pointer
+ }
+ _, dup = stores[*c]
+ stores[*c] = true
+
+ case *offsetAddrConstraint:
+ if c.src == 0 {
+ continue // skip offset from non-pointer
+ }
+ _, dup = offsetAddrs[*c]
+ offsetAddrs[*c] = true
+
+ case *untagConstraint:
+ if c.src == 0 {
+ continue // skip untag of non-pointer
+ }
+ _, dup = untags[*c]
+ untags[*c] = true
+
+ case *typeFilterConstraint:
+ if c.src == 0 {
+ continue // skip filter of non-pointer
+ }
+ _, dup = typeFilters[*c]
+ typeFilters[*c] = true
+
+ case *invokeConstraint:
+ if c.params == 0 {
+ panic("non-pointer invoke.params")
+ }
+ if c.iface == 0 {
+ continue // skip invoke on non-pointer
+ }
+ _, dup = invokes[*c]
+ invokes[*c] = true
+
+ default:
+ // We don't bother de-duping advanced constraints
+ // (e.g. reflection) since they are uncommon.
+
+ // Eliminate constraints containing non-pointer nodeids.
+ //
+ // We use reflection to find the fields to avoid
+ // adding yet another method to constraint.
+ //
+ // TODO(adonovan): experiment with a constraint
+ // method that returns a slice of pointers to
+ // nodeids fields to enable uniform iteration;
+ // the renumber() method could be removed and
+ // implemented using the new one.
+ //
+ // TODO(adonovan): opt: this is unsound since
+ // some constraints still have an effect if one
+ // of the operands is zero: rVCall, rVMapIndex,
+ // rvSetMapIndex. Handle them specially.
+ rtNodeid := reflect.TypeOf(nodeid(0))
+ x := reflect.ValueOf(c).Elem()
+ for i, nf := 0, x.NumField(); i < nf; i++ {
+ f := x.Field(i)
+ if f.Type() == rtNodeid {
+ if f.Uint() == 0 {
+ dup = true // skip it
+ break
+ }
+ }
+ }
+ }
+ if dup {
+ continue // skip duplicates
+ }
+
+ cc = append(cc, c)
+ }
+ h.a.constraints = cc
+
+ if h.log != nil {
+ fmt.Fprintf(h.log, "#constraints: was %d, now %d\n", nbefore, len(h.a.constraints))
+ }
+}
+
+// find returns the canonical onodeid for x.
+// (The onodes form a disjoint set forest.)
+func (h *hvn) find(x onodeid) onodeid {
+ // TODO(adonovan): opt: this is a CPU hotspot. Try "union by rank".
+ xo := h.onodes[x]
+ rep := xo.rep
+ if rep != x {
+ rep = h.find(rep) // simple path compression
+ xo.rep = rep
+ }
+ return rep
+}
+
+func (h *hvn) checkCanonical(x onodeid) {
+ if debugHVN {
+ assert(x == h.find(x), "not canonical")
+ }
+}
+
+func assert(p bool, msg string) {
+ if debugHVN && !p {
+ panic("assertion failed: " + msg)
+ }
+}
projects / dotfiles / .git / blobdiff