+++ /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 implements Andersen's analysis, an inclusion-based
-pointer analysis algorithm first described in (Andersen, 1994).
-
-A pointer analysis relates every pointer expression in a whole program
-to the set of memory locations to which it might point. This
-information can be used to construct a call graph of the program that
-precisely represents the destinations of dynamic function and method
-calls. It can also be used to determine, for example, which pairs of
-channel operations operate on the same channel.
-
-The package allows the client to request a set of expressions of
-interest for which the points-to information will be returned once the
-analysis is complete. In addition, the client may request that a
-callgraph is constructed. The example program in example_test.go
-demonstrates both of these features. Clients should not request more
-information than they need since it may increase the cost of the
-analysis significantly.
-
-
-CLASSIFICATION
-
-Our algorithm is INCLUSION-BASED: the points-to sets for x and y will
-be related by pts(y) ⊇ pts(x) if the program contains the statement
-y = x.
-
-It is FLOW-INSENSITIVE: it ignores all control flow constructs and the
-order of statements in a program. It is therefore a "MAY ALIAS"
-analysis: its facts are of the form "P may/may not point to L",
-not "P must point to L".
-
-It is FIELD-SENSITIVE: it builds separate points-to sets for distinct
-fields, such as x and y in struct { x, y *int }.
-
-It is mostly CONTEXT-INSENSITIVE: most functions are analyzed once,
-so values can flow in at one call to the function and return out at
-another. Only some smaller functions are analyzed with consideration
-of their calling context.
-
-It has a CONTEXT-SENSITIVE HEAP: objects are named by both allocation
-site and context, so the objects returned by two distinct calls to f:
- func f() *T { return new(T) }
-are distinguished up to the limits of the calling context.
-
-It is a WHOLE PROGRAM analysis: it requires SSA-form IR for the
-complete Go program and summaries for native code.
-
-See the (Hind, PASTE'01) survey paper for an explanation of these terms.
-
-
-SOUNDNESS
-
-The analysis is fully sound when invoked on pure Go programs that do not
-use reflection or unsafe.Pointer conversions. In other words, if there
-is any possible execution of the program in which pointer P may point to
-object O, the analysis will report that fact.
-
-
-REFLECTION
-
-By default, the "reflect" library is ignored by the analysis, as if all
-its functions were no-ops, but if the client enables the Reflection flag,
-the analysis will make a reasonable attempt to model the effects of
-calls into this library. However, this comes at a significant
-performance cost, and not all features of that library are yet
-implemented. In addition, some simplifying approximations must be made
-to ensure that the analysis terminates; for example, reflection can be
-used to construct an infinite set of types and values of those types,
-but the analysis arbitrarily bounds the depth of such types.
-
-Most but not all reflection operations are supported.
-In particular, addressable reflect.Values are not yet implemented, so
-operations such as (reflect.Value).Set have no analytic effect.
-
-
-UNSAFE POINTER CONVERSIONS
-
-The pointer analysis makes no attempt to understand aliasing between the
-operand x and result y of an unsafe.Pointer conversion:
- y = (*T)(unsafe.Pointer(x))
-It is as if the conversion allocated an entirely new object:
- y = new(T)
-
-
-NATIVE CODE
-
-The analysis cannot model the aliasing effects of functions written in
-languages other than Go, such as runtime intrinsics in C or assembly, or
-code accessed via cgo. The result is as if such functions are no-ops.
-However, various important intrinsics are understood by the analysis,
-along with built-ins such as append.
-
-The analysis currently provides no way for users to specify the aliasing
-effects of native code.
-
-------------------------------------------------------------------------
-
-IMPLEMENTATION
-
-The remaining documentation is intended for package maintainers and
-pointer analysis specialists. Maintainers should have a solid
-understanding of the referenced papers (especially those by H&L and PKH)
-before making making significant changes.
-
-The implementation is similar to that described in (Pearce et al,
-PASTE'04). Unlike many algorithms which interleave constraint
-generation and solving, constructing the callgraph as they go, this
-implementation for the most part observes a phase ordering (generation
-before solving), with only simple (copy) constraints being generated
-during solving. (The exception is reflection, which creates various
-constraints during solving as new types flow to reflect.Value
-operations.) This improves the traction of presolver optimisations,
-but imposes certain restrictions, e.g. potential context sensitivity
-is limited since all variants must be created a priori.
-
-
-TERMINOLOGY
-
-A type is said to be "pointer-like" if it is a reference to an object.
-Pointer-like types include pointers and also interfaces, maps, channels,
-functions and slices.
-
-We occasionally use C's x->f notation to distinguish the case where x
-is a struct pointer from x.f where is a struct value.
-
-Pointer analysis literature (and our comments) often uses the notation
-dst=*src+offset to mean something different than what it means in Go.
-It means: for each node index p in pts(src), the node index p+offset is
-in pts(dst). Similarly *dst+offset=src is used for store constraints
-and dst=src+offset for offset-address constraints.
-
-
-NODES
-
-Nodes are the key datastructure of the analysis, and have a dual role:
-they represent both constraint variables (equivalence classes of
-pointers) and members of points-to sets (things that can be pointed
-at, i.e. "labels").
-
-Nodes are naturally numbered. The numbering enables compact
-representations of sets of nodes such as bitvectors (or BDDs); and the
-ordering enables a very cheap way to group related nodes together. For
-example, passing n parameters consists of generating n parallel
-constraints from caller+i to callee+i for 0<=i<n.
-
-The zero nodeid means "not a pointer". For simplicity, we generate flow
-constraints even for non-pointer types such as int. The pointer
-equivalence (PE) presolver optimization detects which variables cannot
-point to anything; this includes not only all variables of non-pointer
-types (such as int) but also variables of pointer-like types if they are
-always nil, or are parameters to a function that is never called.
-
-Each node represents a scalar part of a value or object.
-Aggregate types (structs, tuples, arrays) are recursively flattened
-out into a sequential list of scalar component types, and all the
-elements of an array are represented by a single node. (The
-flattening of a basic type is a list containing a single node.)
-
-Nodes are connected into a graph with various kinds of labelled edges:
-simple edges (or copy constraints) represent value flow. Complex
-edges (load, store, etc) trigger the creation of new simple edges
-during the solving phase.
-
-
-OBJECTS
-
-Conceptually, an "object" is a contiguous sequence of nodes denoting
-an addressable location: something that a pointer can point to. The
-first node of an object has a non-nil obj field containing information
-about the allocation: its size, context, and ssa.Value.
-
-Objects include:
- - functions and globals;
- - variable allocations in the stack frame or heap;
- - maps, channels and slices created by calls to make();
- - allocations to construct an interface;
- - allocations caused by conversions, e.g. []byte(str).
- - arrays allocated by calls to append();
-
-Many objects have no Go types. For example, the func, map and chan type
-kinds in Go are all varieties of pointers, but their respective objects
-are actual functions (executable code), maps (hash tables), and channels
-(synchronized queues). Given the way we model interfaces, they too are
-pointers to "tagged" objects with no Go type. And an *ssa.Global denotes
-the address of a global variable, but the object for a Global is the
-actual data. So, the types of an ssa.Value that creates an object is
-"off by one indirection": a pointer to the object.
-
-The individual nodes of an object are sometimes referred to as "labels".
-
-For uniformity, all objects have a non-zero number of fields, even those
-of the empty type struct{}. (All arrays are treated as if of length 1,
-so there are no empty arrays. The empty tuple is never address-taken,
-so is never an object.)
-
-
-TAGGED OBJECTS
-
-An tagged object has the following layout:
-
- T -- obj.flags ⊇ {otTagged}
- v
- ...
-
-The T node's typ field is the dynamic type of the "payload": the value
-v which follows, flattened out. The T node's obj has the otTagged
-flag.
-
-Tagged objects are needed when generalizing across types: interfaces,
-reflect.Values, reflect.Types. Each of these three types is modelled
-as a pointer that exclusively points to tagged objects.
-
-Tagged objects may be indirect (obj.flags ⊇ {otIndirect}) meaning that
-the value v is not of type T but *T; this is used only for
-reflect.Values that represent lvalues. (These are not implemented yet.)
-
-
-ANALYSIS ABSTRACTION OF EACH TYPE
-
-Variables of the following "scalar" types may be represented by a
-single node: basic types, pointers, channels, maps, slices, 'func'
-pointers, interfaces.
-
-Pointers
- Nothing to say here, oddly.
-
-Basic types (bool, string, numbers, unsafe.Pointer)
- Currently all fields in the flattening of a type, including
- non-pointer basic types such as int, are represented in objects and
- values. Though non-pointer nodes within values are uninteresting,
- non-pointer nodes in objects may be useful (if address-taken)
- because they permit the analysis to deduce, in this example,
-
- var s struct{ ...; x int; ... }
- p := &s.x
-
- that p points to s.x. If we ignored such object fields, we could only
- say that p points somewhere within s.
-
- All other basic types are ignored. Expressions of these types have
- zero nodeid, and fields of these types within aggregate other types
- are omitted.
-
- unsafe.Pointers are not modelled as pointers, so a conversion of an
- unsafe.Pointer to *T is (unsoundly) treated equivalent to new(T).
-
-Channels
- An expression of type 'chan T' is a kind of pointer that points
- exclusively to channel objects, i.e. objects created by MakeChan (or
- reflection).
-
- 'chan T' is treated like *T.
- *ssa.MakeChan is treated as equivalent to new(T).
- *ssa.Send and receive (*ssa.UnOp(ARROW)) and are equivalent to store
- and load.
-
-Maps
- An expression of type 'map[K]V' is a kind of pointer that points
- exclusively to map objects, i.e. objects created by MakeMap (or
- reflection).
-
- map K[V] is treated like *M where M = struct{k K; v V}.
- *ssa.MakeMap is equivalent to new(M).
- *ssa.MapUpdate is equivalent to *y=x where *y and x have type M.
- *ssa.Lookup is equivalent to y=x.v where x has type *M.
-
-Slices
- A slice []T, which dynamically resembles a struct{array *T, len, cap int},
- is treated as if it were just a *T pointer; the len and cap fields are
- ignored.
-
- *ssa.MakeSlice is treated like new([1]T): an allocation of a
- singleton array.
- *ssa.Index on a slice is equivalent to a load.
- *ssa.IndexAddr on a slice returns the address of the sole element of the
- slice, i.e. the same address.
- *ssa.Slice is treated as a simple copy.
-
-Functions
- An expression of type 'func...' is a kind of pointer that points
- exclusively to function objects.
-
- A function object has the following layout:
-
- identity -- typ:*types.Signature; obj.flags ⊇ {otFunction}
- params_0 -- (the receiver, if a method)
- ...
- params_n-1
- results_0
- ...
- results_m-1
-
- There may be multiple function objects for the same *ssa.Function
- due to context-sensitive treatment of some functions.
-
- The first node is the function's identity node.
- Associated with every callsite is a special "targets" variable,
- whose pts() contains the identity node of each function to which
- the call may dispatch. Identity words are not otherwise used during
- the analysis, but we construct the call graph from the pts()
- solution for such nodes.
-
- The following block of contiguous nodes represents the flattened-out
- types of the parameters ("P-block") and results ("R-block") of the
- function object.
-
- The treatment of free variables of closures (*ssa.FreeVar) is like
- that of global variables; it is not context-sensitive.
- *ssa.MakeClosure instructions create copy edges to Captures.
-
- A Go value of type 'func' (i.e. a pointer to one or more functions)
- is a pointer whose pts() contains function objects. The valueNode()
- for an *ssa.Function returns a singleton for that function.
-
-Interfaces
- An expression of type 'interface{...}' is a kind of pointer that
- points exclusively to tagged objects. All tagged objects pointed to
- by an interface are direct (the otIndirect flag is clear) and
- concrete (the tag type T is not itself an interface type). The
- associated ssa.Value for an interface's tagged objects may be an
- *ssa.MakeInterface instruction, or nil if the tagged object was
- created by an instrinsic (e.g. reflection).
-
- Constructing an interface value causes generation of constraints for
- all of the concrete type's methods; we can't tell a priori which
- ones may be called.
-
- TypeAssert y = x.(T) is implemented by a dynamic constraint
- triggered by each tagged object O added to pts(x): a typeFilter
- constraint if T is an interface type, or an untag constraint if T is
- a concrete type. A typeFilter tests whether O.typ implements T; if
- so, O is added to pts(y). An untagFilter tests whether O.typ is
- assignable to T,and if so, a copy edge O.v -> y is added.
-
- ChangeInterface is a simple copy because the representation of
- tagged objects is independent of the interface type (in contrast
- to the "method tables" approach used by the gc runtime).
-
- y := Invoke x.m(...) is implemented by allocating contiguous P/R
- blocks for the callsite and adding a dynamic rule triggered by each
- tagged object added to pts(x). The rule adds param/results copy
- edges to/from each discovered concrete method.
-
- (Q. Why do we model an interface as a pointer to a pair of type and
- value, rather than as a pair of a pointer to type and a pointer to
- value?
- A. Control-flow joins would merge interfaces ({T1}, {V1}) and ({T2},
- {V2}) to make ({T1,T2}, {V1,V2}), leading to the infeasible and
- type-unsafe combination (T1,V2). Treating the value and its concrete
- type as inseparable makes the analysis type-safe.)
-
-reflect.Value
- A reflect.Value is modelled very similar to an interface{}, i.e. as
- a pointer exclusively to tagged objects, but with two generalizations.
-
- 1) a reflect.Value that represents an lvalue points to an indirect
- (obj.flags ⊇ {otIndirect}) tagged object, which has a similar
- layout to an tagged object except that the value is a pointer to
- the dynamic type. Indirect tagged objects preserve the correct
- aliasing so that mutations made by (reflect.Value).Set can be
- observed.
-
- Indirect objects only arise when an lvalue is derived from an
- rvalue by indirection, e.g. the following code:
-
- type S struct { X T }
- var s S
- var i interface{} = &s // i points to a *S-tagged object (from MakeInterface)
- v1 := reflect.ValueOf(i) // v1 points to same *S-tagged object as i
- v2 := v1.Elem() // v2 points to an indirect S-tagged object, pointing to s
- v3 := v2.FieldByName("X") // v3 points to an indirect int-tagged object, pointing to s.X
- v3.Set(y) // pts(s.X) ⊇ pts(y)
-
- Whether indirect or not, the concrete type of the tagged object
- corresponds to the user-visible dynamic type, and the existence
- of a pointer is an implementation detail.
-
- (NB: indirect tagged objects are not yet implemented)
-
- 2) The dynamic type tag of a tagged object pointed to by a
- reflect.Value may be an interface type; it need not be concrete.
-
- This arises in code such as this:
- tEface := reflect.TypeOf(new(interface{}).Elem() // interface{}
- eface := reflect.Zero(tEface)
- pts(eface) is a singleton containing an interface{}-tagged
- object. That tagged object's payload is an interface{} value,
- i.e. the pts of the payload contains only concrete-tagged
- objects, although in this example it's the zero interface{} value,
- so its pts is empty.
-
-reflect.Type
- Just as in the real "reflect" library, we represent a reflect.Type
- as an interface whose sole implementation is the concrete type,
- *reflect.rtype. (This choice is forced on us by go/types: clients
- cannot fabricate types with arbitrary method sets.)
-
- rtype instances are canonical: there is at most one per dynamic
- type. (rtypes are in fact large structs but since identity is all
- that matters, we represent them by a single node.)
-
- The payload of each *rtype-tagged object is an *rtype pointer that
- points to exactly one such canonical rtype object. We exploit this
- by setting the node.typ of the payload to the dynamic type, not
- '*rtype'. This saves us an indirection in each resolution rule. As
- an optimisation, *rtype-tagged objects are canonicalized too.
-
-
-Aggregate types:
-
-Aggregate types are treated as if all directly contained
-aggregates are recursively flattened out.
-
-Structs
- *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
-
- *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- simple edges for each struct discovered in pts(x).
-
- The nodes of a struct consist of a special 'identity' node (whose
- type is that of the struct itself), followed by the nodes for all
- the struct's fields, recursively flattened out. A pointer to the
- struct is a pointer to its identity node. That node allows us to
- distinguish a pointer to a struct from a pointer to its first field.
-
- Field offsets are logical field offsets (plus one for the identity
- node), so the sizes of the fields can be ignored by the analysis.
-
- (The identity node is non-traditional but enables the distinction
- described above, which is valuable for code comprehension tools.
- Typical pointer analyses for C, whose purpose is compiler
- optimization, must soundly model unsafe.Pointer (void*) conversions,
- and this requires fidelity to the actual memory layout using physical
- field offsets.)
-
- *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
-
- *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- simple edges for each struct discovered in pts(x).
-
-Arrays
- We model an array by an identity node (whose type is that of the
- array itself) followed by a node representing all the elements of
- the array; the analysis does not distinguish elements with different
- indices. Effectively, an array is treated like struct{elem T}, a
- load y=x[i] like y=x.elem, and a store x[i]=y like x.elem=y; the
- index i is ignored.
-
- A pointer to an array is pointer to its identity node. (A slice is
- also a pointer to an array's identity node.) The identity node
- allows us to distinguish a pointer to an array from a pointer to one
- of its elements, but it is rather costly because it introduces more
- offset constraints into the system. Furthermore, sound treatment of
- unsafe.Pointer would require us to dispense with this node.
-
- Arrays may be allocated by Alloc, by make([]T), by calls to append,
- and via reflection.
-
-Tuples (T, ...)
- Tuples are treated like structs with naturally numbered fields.
- *ssa.Extract is analogous to *ssa.Field.
-
- However, tuples have no identity field since by construction, they
- cannot be address-taken.
-
-
-FUNCTION CALLS
-
- There are three kinds of function call:
- (1) static "call"-mode calls of functions.
- (2) dynamic "call"-mode calls of functions.
- (3) dynamic "invoke"-mode calls of interface methods.
- Cases 1 and 2 apply equally to methods and standalone functions.
-
- Static calls.
- A static call consists three steps:
- - finding the function object of the callee;
- - creating copy edges from the actual parameter value nodes to the
- P-block in the function object (this includes the receiver if
- the callee is a method);
- - creating copy edges from the R-block in the function object to
- the value nodes for the result of the call.
-
- A static function call is little more than two struct value copies
- between the P/R blocks of caller and callee:
-
- callee.P = caller.P
- caller.R = callee.R
-
- Context sensitivity
-
- Static calls (alone) may be treated context sensitively,
- i.e. each callsite may cause a distinct re-analysis of the
- callee, improving precision. Our current context-sensitivity
- policy treats all intrinsics and getter/setter methods in this
- manner since such functions are small and seem like an obvious
- source of spurious confluences, though this has not yet been
- evaluated.
-
- Dynamic function calls
-
- Dynamic calls work in a similar manner except that the creation of
- copy edges occurs dynamically, in a similar fashion to a pair of
- struct copies in which the callee is indirect:
-
- callee->P = caller.P
- caller.R = callee->R
-
- (Recall that the function object's P- and R-blocks are contiguous.)
-
- Interface method invocation
-
- For invoke-mode calls, we create a params/results block for the
- callsite and attach a dynamic closure rule to the interface. For
- each new tagged object that flows to the interface, we look up
- the concrete method, find its function object, and connect its P/R
- blocks to the callsite's P/R blocks, adding copy edges to the graph
- during solving.
-
- Recording call targets
-
- The analysis notifies its clients of each callsite it encounters,
- passing a CallSite interface. Among other things, the CallSite
- contains a synthetic constraint variable ("targets") whose
- points-to solution includes the set of all function objects to
- which the call may dispatch.
-
- It is via this mechanism that the callgraph is made available.
- Clients may also elect to be notified of callgraph edges directly;
- internally this just iterates all "targets" variables' pts(·)s.
-
-
-PRESOLVER
-
-We implement Hash-Value Numbering (HVN), a pre-solver constraint
-optimization described in Hardekopf & Lin, SAS'07. This is documented
-in more detail in hvn.go. We intend to add its cousins HR and HU in
-future.
-
-
-SOLVER
-
-The solver is currently a naive Andersen-style implementation; it does
-not perform online cycle detection, though we plan to add solver
-optimisations such as Hybrid- and Lazy- Cycle Detection from (Hardekopf
-& Lin, PLDI'07).
-
-It uses difference propagation (Pearce et al, SQC'04) to avoid
-redundant re-triggering of closure rules for values already seen.
-
-Points-to sets are represented using sparse bit vectors (similar to
-those used in LLVM and gcc), which are more space- and time-efficient
-than sets based on Go's built-in map type or dense bit vectors.
-
-Nodes are permuted prior to solving so that object nodes (which may
-appear in points-to sets) are lower numbered than non-object (var)
-nodes. This improves the density of the set over which the PTSs
-range, and thus the efficiency of the representation.
-
-Partly thanks to avoiding map iteration, the execution of the solver is
-100% deterministic, a great help during debugging.
-
-
-FURTHER READING
-
-Andersen, L. O. 1994. Program analysis and specialization for the C
-programming language. Ph.D. dissertation. DIKU, University of
-Copenhagen.
-
-David J. Pearce, Paul H. J. Kelly, and Chris Hankin. 2004. Efficient
-field-sensitive pointer analysis for C. In Proceedings of the 5th ACM
-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and
-engineering (PASTE '04). ACM, New York, NY, USA, 37-42.
-http://doi.acm.org/10.1145/996821.996835
-
-David J. Pearce, Paul H. J. Kelly, and Chris Hankin. 2004. Online
-Cycle Detection and Difference Propagation: Applications to Pointer
-Analysis. Software Quality Control 12, 4 (December 2004), 311-337.
-http://dx.doi.org/10.1023/B:SQJO.0000039791.93071.a2
-
-David Grove and Craig Chambers. 2001. A framework for call graph
-construction algorithms. ACM Trans. Program. Lang. Syst. 23, 6
-(November 2001), 685-746.
-http://doi.acm.org/10.1145/506315.506316
-
-Ben Hardekopf and Calvin Lin. 2007. The ant and the grasshopper: fast
-and accurate pointer analysis for millions of lines of code. In
-Proceedings of the 2007 ACM SIGPLAN conference on Programming language
-design and implementation (PLDI '07). ACM, New York, NY, USA, 290-299.
-http://doi.acm.org/10.1145/1250734.1250767
-
-Ben Hardekopf and Calvin Lin. 2007. Exploiting pointer and location
-equivalence to optimize pointer analysis. In Proceedings of the 14th
-international conference on Static Analysis (SAS'07), Hanne Riis
-Nielson and Gilberto Filé (Eds.). Springer-Verlag, Berlin, Heidelberg,
-265-280.
-
-Atanas Rountev and Satish Chandra. 2000. Off-line variable substitution
-for scaling points-to analysis. In Proceedings of the ACM SIGPLAN 2000
-conference on Programming language design and implementation (PLDI '00).
-ACM, New York, NY, USA, 47-56. DOI=10.1145/349299.349310
-http://doi.acm.org/10.1145/349299.349310
-
-*/
-package pointer // import "golang.org/x/tools/go/pointer"
projects / dotfiles / .git / blobdiff