go/pointer/opt.go

// 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
}