← Back to branch summary

~vtuson/scopecreator/twitter-template

« back to all changes in this revision

Viewing changes to src/go/src/code.google.com/p/go.tools/go/pointer/opt.go

  • Committer: Victor Palau
  • Date: 2015-03-11 14:24:42 UTC
  • Revision ID: vtuson@gmail.com-20150311142442-f2pxp111c8ynv232
public release

Show diffs side-by-side

added added

removed removed

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