--- /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 renumbering, a pre-solver optimization to
+// improve the efficiency of the solver's points-to set representation.
+//
+// TODO(adonovan): rename file "renumber.go"
+
+import "fmt"
+
+// renumber permutes a.nodes so that all nodes within an addressable
+// object appear before all non-addressable nodes, maintaining the
+// order of nodes within the same object (as required by offsetAddr).
+//
+// renumber must update every nodeid in the analysis (constraints,
+// Pointers, callgraph, etc) to reflect the new ordering.
+//
+// This is an optimisation to increase the locality and efficiency of
+// sparse representations of points-to sets. (Typically only about
+// 20% of nodes are within an object.)
+//
+// NB: nodes added during solving (e.g. for reflection, SetFinalizer)
+// will be appended to the end.
+//
+// Renumbering makes the PTA log inscrutable. To aid debugging, later
+// phases (e.g. HVN) must not rely on it having occurred.
+//
+func (a *analysis) renumber() {
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\n\n==== Renumbering\n\n")
+ }
+
+ N := nodeid(len(a.nodes))
+ newNodes := make([]*node, N)
+ renumbering := make([]nodeid, N) // maps old to new
+
+ var i, j nodeid
+
+ // The zero node is special.
+ newNodes[j] = a.nodes[i]
+ renumbering[i] = j
+ i++
+ j++
+
+ // Pass 1: object nodes.
+ for i < N {
+ obj := a.nodes[i].obj
+ if obj == nil {
+ i++
+ continue
+ }
+
+ end := i + nodeid(obj.size)
+ for i < end {
+ newNodes[j] = a.nodes[i]
+ renumbering[i] = j
+ i++
+ j++
+ }
+ }
+ nobj := j
+
+ // Pass 2: non-object nodes.
+ for i = 1; i < N; {
+ obj := a.nodes[i].obj
+ if obj != nil {
+ i += nodeid(obj.size)
+ continue
+ }
+
+ newNodes[j] = a.nodes[i]
+ renumbering[i] = j
+ i++
+ j++
+ }
+
+ if j != N {
+ panic(fmt.Sprintf("internal error: j=%d, N=%d", j, N))
+ }
+
+ // Log the remapping table.
+ if a.log != nil {
+ fmt.Fprintf(a.log, "Renumbering nodes to improve density:\n")
+ fmt.Fprintf(a.log, "(%d object nodes of %d total)\n", nobj, N)
+ for old, new := range renumbering {
+ fmt.Fprintf(a.log, "\tn%d -> n%d\n", old, new)
+ }
+ }
+
+ // Now renumber all existing nodeids to use the new node permutation.
+ // It is critical that all reachable nodeids are accounted for!
+
+ // Renumber nodeids in queried Pointers.
+ for v, ptr := range a.result.Queries {
+ ptr.n = renumbering[ptr.n]
+ a.result.Queries[v] = ptr
+ }
+ for v, ptr := range a.result.IndirectQueries {
+ ptr.n = renumbering[ptr.n]
+ a.result.IndirectQueries[v] = ptr
+ }
+ for _, queries := range a.config.extendedQueries {
+ for _, query := range queries {
+ if query.ptr != nil {
+ query.ptr.n = renumbering[query.ptr.n]
+ }
+ }
+ }
+
+ // Renumber nodeids in global objects.
+ for v, id := range a.globalobj {
+ a.globalobj[v] = renumbering[id]
+ }
+
+ // Renumber nodeids in constraints.
+ for _, c := range a.constraints {
+ c.renumber(renumbering)
+ }
+
+ // Renumber nodeids in the call graph.
+ for _, cgn := range a.cgnodes {
+ cgn.obj = renumbering[cgn.obj]
+ for _, site := range cgn.sites {
+ site.targets = renumbering[site.targets]
+ }
+ }
+
+ a.nodes = newNodes
+}