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 implements renumbering, a pre-solver optimization to
8// improve the efficiency of the solver's points-to set representation.
9//
10// TODO(adonovan): rename file "renumber.go"
11
12import "fmt"
13
14// renumber permutes a.nodes so that all nodes within an addressable
15// object appear before all non-addressable nodes, maintaining the
16// order of nodes within the same object (as required by offsetAddr).
17//
18// renumber must update every nodeid in the analysis (constraints,
19// Pointers, callgraph, etc) to reflect the new ordering.
20//
21// This is an optimisation to increase the locality and efficiency of
22// sparse representations of points-to sets.  (Typically only about
23// 20% of nodes are within an object.)
24//
25// NB: nodes added during solving (e.g. for reflection, SetFinalizer)
26// will be appended to the end.
27//
28// Renumbering makes the PTA log inscrutable.  To aid debugging, later
29// phases (e.g. HVN) must not rely on it having occurred.
30//
31func (a *analysis) renumber() {
32	if a.log != nil {
33		fmt.Fprintf(a.log, "\n\n==== Renumbering\n\n")
34	}
35
36	N := nodeid(len(a.nodes))
37	newNodes := make([]*node, N)
38	renumbering := make([]nodeid, N) // maps old to new
39
40	var i, j nodeid
41
42	// The zero node is special.
43	newNodes[j] = a.nodes[i]
44	renumbering[i] = j
45	i++
46	j++
47
48	// Pass 1: object nodes.
49	for i < N {
50		obj := a.nodes[i].obj
51		if obj == nil {
52			i++
53			continue
54		}
55
56		end := i + nodeid(obj.size)
57		for i < end {
58			newNodes[j] = a.nodes[i]
59			renumbering[i] = j
60			i++
61			j++
62		}
63	}
64	nobj := j
65
66	// Pass 2: non-object nodes.
67	for i = 1; i < N; {
68		obj := a.nodes[i].obj
69		if obj != nil {
70			i += nodeid(obj.size)
71			continue
72		}
73
74		newNodes[j] = a.nodes[i]
75		renumbering[i] = j
76		i++
77		j++
78	}
79
80	if j != N {
81		panic(fmt.Sprintf("internal error: j=%d, N=%d", j, N))
82	}
83
84	// Log the remapping table.
85	if a.log != nil {
86		fmt.Fprintf(a.log, "Renumbering nodes to improve density:\n")
87		fmt.Fprintf(a.log, "(%d object nodes of %d total)\n", nobj, N)
88		for old, new := range renumbering {
89			fmt.Fprintf(a.log, "\tn%d -> n%d\n", old, new)
90		}
91	}
92
93	// Now renumber all existing nodeids to use the new node permutation.
94	// It is critical that all reachable nodeids are accounted for!
95
96	// Renumber nodeids in queried Pointers.
97	for v, ptr := range a.result.Queries {
98		ptr.n = renumbering[ptr.n]
99		a.result.Queries[v] = ptr
100	}
101	for v, ptr := range a.result.IndirectQueries {
102		ptr.n = renumbering[ptr.n]
103		a.result.IndirectQueries[v] = ptr
104	}
105	for _, queries := range a.config.extendedQueries {
106		for _, query := range queries {
107			if query.ptr != nil {
108				query.ptr.n = renumbering[query.ptr.n]
109			}
110		}
111	}
112
113	// Renumber nodeids in global objects.
114	for v, id := range a.globalobj {
115		a.globalobj[v] = renumbering[id]
116	}
117
118	// Renumber nodeids in constraints.
119	for _, c := range a.constraints {
120		c.renumber(renumbering)
121	}
122
123	// Renumber nodeids in the call graph.
124	for _, cgn := range a.cgnodes {
125		cgn.obj = renumbering[cgn.obj]
126		for _, site := range cgn.sites {
127			site.targets = renumbering[site.targets]
128		}
129	}
130
131	a.nodes = newNodes
132}
133