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.
7 // This file defines the main datatypes and Analyze function of the pointer analysis.
20 "golang.org/x/tools/go/callgraph"
21 "golang.org/x/tools/go/ssa"
22 "golang.org/x/tools/go/types/typeutil"
26 // optimization options; enable all when committing
27 optRenumber = true // enable renumbering optimization (makes logs hard to read)
28 optHVN = true // enable pointer equivalence via Hash-Value Numbering
30 // debugging options; disable all when committing
31 debugHVN = false // enable assertions in HVN
32 debugHVNVerbose = false // enable extra HVN logging
33 debugHVNCrossCheck = false // run solver with/without HVN and compare (caveats below)
34 debugTimers = false // show running time of each phase
37 // object.flags bitmask values.
39 otTagged = 1 << iota // type-tagged object
40 otIndirect // type-tagged object with indirect payload
41 otFunction // function object
44 // An object represents a contiguous block of memory to which some
45 // (generalized) pointer may point.
47 // (Note: most variables called 'obj' are not *objects but nodeids
48 // such that a.nodes[obj].obj != nil.)
51 // flags is a bitset of the node type (ot*) flags defined above.
54 // Number of following nodes belonging to the same "object"
55 // allocation. Zero for all other nodes.
58 // data describes this object; it has one of these types:
60 // ssa.Value for an object allocated by an SSA operation.
61 // types.Type for an rtype instance object or *rtype-tagged object.
62 // string for an instrinsic object, e.g. the array behind os.Args.
63 // nil for an object allocated by an instrinsic.
64 // (cgn provides the identity of the intrinsic.)
67 // The call-graph node (=context) in which this object was allocated.
68 // May be nil for global objects: Global, Const, some Functions.
72 // nodeid denotes a node.
73 // It is an index within analysis.nodes.
74 // We use small integers, not *node pointers, for many reasons:
75 // - they are smaller on 64-bit systems.
76 // - sets of them can be represented compactly in bitvectors or BDDs.
77 // - order matters; a field offset can be computed by simple addition.
80 // A node is an equivalence class of memory locations.
81 // Nodes may be pointers, pointed-to locations, neither, or both.
83 // Nodes that are pointed-to locations ("labels") have an enclosing
84 // object (see analysis.enclosingObject).
87 // If non-nil, this node is the start of an object
88 // (addressable memory location).
89 // The following obj.size nodes implicitly belong to the object;
90 // they locate their object by scanning back.
93 // The type of the field denoted by this node. Non-aggregate,
94 // unless this is an tagged.T node (i.e. the thing
95 // pointed to by an interface) in which case typ is that type.
98 // subelement indicates which directly embedded subelement of
99 // an object of aggregate type (struct, tuple, array) this is.
100 subelement *fieldInfo // e.g. ".a.b[*].c"
102 // Solver state for the canonical node of this pointer-
103 // equivalence class. Each node is created with its own state
104 // but they become shared after HVN.
108 // An analysis instance holds the state of a single pointer analysis problem.
109 type analysis struct {
110 config *Config // the client's control/observer interface
111 prog *ssa.Program // the program being analyzed
112 log io.Writer // log stream; nil to disable
113 panicNode nodeid // sink for panic, source for recover
114 nodes []*node // indexed by nodeid
115 flattenMemo map[types.Type][]*fieldInfo // memoization of flatten()
116 trackTypes map[types.Type]bool // memoization of shouldTrack()
117 constraints []constraint // set of constraints
118 cgnodes []*cgnode // all cgnodes
119 genq []*cgnode // queue of functions to generate constraints for
120 intrinsics map[*ssa.Function]intrinsic // non-nil values are summaries for intrinsic fns
121 globalval map[ssa.Value]nodeid // node for each global ssa.Value
122 globalobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
123 localval map[ssa.Value]nodeid // node for each local ssa.Value
124 localobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
125 atFuncs map[*ssa.Function]bool // address-taken functions (for presolver)
126 mapValues []nodeid // values of makemap objects (indirect in HVN)
127 work nodeset // solver's worklist
128 result *Result // results of the analysis
129 track track // pointerlike types whose aliasing we track
130 deltaSpace []int // working space for iterating over PTS deltas
132 // Reflection & intrinsics:
133 hasher typeutil.Hasher // cache of type hashes
134 reflectValueObj types.Object // type symbol for reflect.Value (if present)
135 reflectValueCall *ssa.Function // (reflect.Value).Call
136 reflectRtypeObj types.Object // *types.TypeName for reflect.rtype (if present)
137 reflectRtypePtr *types.Pointer // *reflect.rtype
138 reflectType *types.Named // reflect.Type
139 rtypes typeutil.Map // nodeid of canonical *rtype-tagged object for type T
140 reflectZeros typeutil.Map // nodeid of canonical T-tagged object for zero value
141 runtimeSetFinalizer *ssa.Function // runtime.SetFinalizer
144 // enclosingObj returns the first node of the addressable memory
145 // object that encloses node id. Panic ensues if that node does not
146 // belong to any object.
147 func (a *analysis) enclosingObj(id nodeid) nodeid {
148 // Find previous node with obj != nil.
149 for i := id; i >= 0; i-- {
151 if obj := n.obj; obj != nil {
152 if i+nodeid(obj.size) <= id {
153 break // out of bounds
158 panic("node has no enclosing object")
161 // labelFor returns the Label for node id.
162 // Panic ensues if that node is not addressable.
163 func (a *analysis) labelFor(id nodeid) *Label {
165 obj: a.nodes[a.enclosingObj(id)].obj,
166 subelement: a.nodes[id].subelement,
170 func (a *analysis) warnf(pos token.Pos, format string, args ...interface{}) {
171 msg := fmt.Sprintf(format, args...)
173 fmt.Fprintf(a.log, "%s: warning: %s\n", a.prog.Fset.Position(pos), msg)
175 a.result.Warnings = append(a.result.Warnings, Warning{pos, msg})
178 // computeTrackBits sets a.track to the necessary 'track' bits for the pointer queries.
179 func (a *analysis) computeTrackBits() {
180 if len(a.config.extendedQueries) != 0 {
181 // TODO(dh): only track the types necessary for the query.
185 var queryTypes []types.Type
186 for v := range a.config.Queries {
187 queryTypes = append(queryTypes, v.Type())
189 for v := range a.config.IndirectQueries {
190 queryTypes = append(queryTypes, mustDeref(v.Type()))
192 for _, t := range queryTypes {
193 switch t.Underlying().(type) {
201 a.track |= trackSlice
202 case *types.Interface:
206 if rVObj := a.reflectValueObj; rVObj != nil && types.Identical(t, rVObj.Type()) {
213 // Analyze runs the pointer analysis with the scope and options
214 // specified by config, and returns the (synthetic) root of the callgraph.
216 // Pointer analysis of a transitively closed well-typed program should
217 // always succeed. An error can occur only due to an internal bug.
219 func Analyze(config *Config) (result *Result, err error) {
220 if config.Mains == nil {
221 return nil, fmt.Errorf("no main/test packages to analyze (check $GOROOT/$GOPATH)")
224 if p := recover(); p != nil {
225 err = fmt.Errorf("internal error in pointer analysis: %v (please report this bug)", p)
226 fmt.Fprintln(os.Stderr, "Internal panic in pointer analysis:")
235 globalval: make(map[ssa.Value]nodeid),
236 globalobj: make(map[ssa.Value]nodeid),
237 flattenMemo: make(map[types.Type][]*fieldInfo),
238 trackTypes: make(map[types.Type]bool),
239 atFuncs: make(map[*ssa.Function]bool),
240 hasher: typeutil.MakeHasher(),
241 intrinsics: make(map[*ssa.Function]intrinsic),
243 Queries: make(map[ssa.Value]Pointer),
244 IndirectQueries: make(map[ssa.Value]Pointer),
246 deltaSpace: make([]int, 0, 100),
250 a.log = os.Stderr // for debugging crashes; extremely verbose
254 fmt.Fprintln(a.log, "==== Starting analysis")
257 // Pointer analysis requires a complete program for soundness.
258 // Check to prevent accidental misconfiguration.
259 for _, pkg := range a.prog.AllPackages() {
260 // (This only checks that the package scope is complete,
261 // not that func bodies exist, but it's a good signal.)
262 if !pkg.Pkg.Complete() {
263 return nil, fmt.Errorf(`pointer analysis requires a complete program yet package %q was incomplete`, pkg.Pkg.Path())
267 if reflect := a.prog.ImportedPackage("reflect"); reflect != nil {
268 rV := reflect.Pkg.Scope().Lookup("Value")
269 a.reflectValueObj = rV
270 a.reflectValueCall = a.prog.LookupMethod(rV.Type(), nil, "Call")
271 a.reflectType = reflect.Pkg.Scope().Lookup("Type").Type().(*types.Named)
272 a.reflectRtypeObj = reflect.Pkg.Scope().Lookup("rtype")
273 a.reflectRtypePtr = types.NewPointer(a.reflectRtypeObj.Type())
275 // Override flattening of reflect.Value, treating it like a basic type.
276 tReflectValue := a.reflectValueObj.Type()
277 a.flattenMemo[tReflectValue] = []*fieldInfo{{typ: tReflectValue}}
279 // Override shouldTrack of reflect.Value and *reflect.rtype.
280 // Always track pointers of these types.
281 a.trackTypes[tReflectValue] = true
282 a.trackTypes[a.reflectRtypePtr] = true
284 a.rtypes.SetHasher(a.hasher)
285 a.reflectZeros.SetHasher(a.hasher)
287 if runtime := a.prog.ImportedPackage("runtime"); runtime != nil {
288 a.runtimeSetFinalizer = runtime.Func("SetFinalizer")
299 N := len(a.nodes) // excludes solver-created nodes
302 if debugHVNCrossCheck {
303 // Cross-check: run the solver once without
304 // optimization, once with, and compare the
306 savedConstraints := a.constraints
309 a.dumpSolution("A.pts", N)
312 a.constraints = savedConstraints
313 for _, n := range a.nodes {
314 n.solve = new(solverState)
316 a.nodes = a.nodes[:N]
318 // rtypes is effectively part of the solver state.
319 a.rtypes = typeutil.Map{}
320 a.rtypes.SetHasher(a.hasher)
326 if debugHVNCrossCheck {
333 // Compare solutions.
334 if optHVN && debugHVNCrossCheck {
335 a.dumpSolution("B.pts", N)
337 if !diff("A.pts", "B.pts") {
338 return nil, fmt.Errorf("internal error: optimization changed solution")
342 // Create callgraph.Nodes in deterministic order.
343 if cg := a.result.CallGraph; cg != nil {
344 for _, caller := range a.cgnodes {
345 cg.CreateNode(caller.fn)
349 // Add dynamic edges to call graph.
351 for _, caller := range a.cgnodes {
352 for _, site := range caller.sites {
353 for _, callee := range a.nodes[site.targets].solve.pts.AppendTo(space[:0]) {
354 a.callEdge(caller, site, nodeid(callee))
362 // callEdge is called for each edge in the callgraph.
363 // calleeid is the callee's object node (has otFunction flag).
365 func (a *analysis) callEdge(caller *cgnode, site *callsite, calleeid nodeid) {
366 obj := a.nodes[calleeid].obj
367 if obj.flags&otFunction == 0 {
368 panic(fmt.Sprintf("callEdge %s -> n%d: not a function object", site, calleeid))
372 if cg := a.result.CallGraph; cg != nil {
373 // TODO(adonovan): opt: I would expect duplicate edges
374 // (to wrappers) to arise due to the elimination of
375 // context information, but I haven't observed any.
376 // Understand this better.
377 callgraph.AddEdge(cg.CreateNode(caller.fn), site.instr, cg.CreateNode(callee.fn))
381 fmt.Fprintf(a.log, "\tcall edge %s -> %s\n", site, callee)
384 // Warn about calls to non-intrinsic external functions.
385 // TODO(adonovan): de-dup these messages.
386 if fn := callee.fn; fn.Blocks == nil && a.findIntrinsic(fn) == nil {
387 a.warnf(site.pos(), "unsound call to unknown intrinsic: %s", fn)
388 a.warnf(fn.Pos(), " (declared here)")
392 // dumpSolution writes the PTS solution to the specified file.
394 // It only dumps the nodes that existed before solving. The order in
395 // which solver-created nodes are created depends on pre-solver
396 // optimization, so we can't include them in the cross-check.
398 func (a *analysis) dumpSolution(filename string, N int) {
399 f, err := os.Create(filename)
403 for id, n := range a.nodes[:N] {
404 if _, err := fmt.Fprintf(f, "pts(n%d) = {", id); err != nil {
408 for _, l := range n.solve.pts.AppendTo(a.deltaSpace) {
412 fmt.Fprintf(f, "%s%d", sep, l)
415 fmt.Fprintf(f, "} : %s\n", n.typ)
417 if err := f.Close(); err != nil {
422 // showCounts logs the size of the constraint system. A typical
423 // optimized distribution is 65% copy, 13% load, 11% addr, 5%
424 // offsetAddr, 4% store, 2% others.
426 func (a *analysis) showCounts() {
428 counts := make(map[reflect.Type]int)
429 for _, c := range a.constraints {
430 counts[reflect.TypeOf(c)]++
432 fmt.Fprintf(a.log, "# constraints:\t%d\n", len(a.constraints))
434 for t, n := range counts {
435 line := fmt.Sprintf("%7d (%2d%%)\t%s", n, 100*n/len(a.constraints), t)
436 lines = append(lines, line)
438 sort.Sort(sort.Reverse(sort.StringSlice(lines)))
439 for _, line := range lines {
440 fmt.Fprintf(a.log, "\t%s\n", line)
443 fmt.Fprintf(a.log, "# nodes:\t%d\n", len(a.nodes))
445 // Show number of pointer equivalence classes.
446 m := make(map[*solverState]bool)
447 for _, n := range a.nodes {
450 fmt.Fprintf(a.log, "# ptsets:\t%d\n", len(m))