| // 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 defines the entry points into the pointer analysis. |
| |
| import ( |
| "fmt" |
| "go/token" |
| "io" |
| "os" |
| |
| "code.google.com/p/go.tools/go/types" |
| "code.google.com/p/go.tools/ssa" |
| ) |
| |
| // nodeid denotes a node. |
| // It is an index within analysis.nodes. |
| // We use small integers, not *node pointers, for many reasons: |
| // - they are smaller on 64-bit systems. |
| // - sets of them can be represented compactly in bitvectors or BDDs. |
| // - order matters; a field offset can be computed by simple addition. |
| type nodeid uint32 |
| |
| // node.flags bitmask values. |
| const ( |
| ntObject = 1 << iota // start of an object (addressable memory location) |
| ntInterface // conctype node of interface object (=> ntObject) |
| ntFunction // identity node of function object (=> ntObject) |
| ) |
| |
| // A node is an equivalence class of memory locations. |
| // Nodes may be pointers, pointed-to locations, neither, or both. |
| type node struct { |
| // flags is a bitset of the node type (nt*) flags defined above. |
| flags uint32 |
| |
| // Number of following words belonging to the same "object" allocation. |
| // (Set by endObject.) Zero for all other nodes. |
| size uint32 |
| |
| // The type of the field denoted by this node. Non-aggregate, |
| // unless this is an iface.conctype node (i.e. the thing |
| // pointed to by an interface) in which case typ is that type. |
| typ types.Type |
| |
| // data holds additional attributes of this node, depending on |
| // its flags. |
| // |
| // If ntObject is set, data is the ssa.Value of the |
| // instruction that allocated this memory, or nil if it was |
| // implicit. |
| // |
| // Special cases: |
| // - If ntInterface is also set, data will be a *ssa.MakeInterface. |
| // - If ntFunction is also set, this node is the first word of a |
| // function block, and data is a *cgnode (not an ssa.Value) |
| // representing this function. |
| data interface{} |
| |
| // subelement indicates which directly embedded subelement of |
| // an object of aggregate type (struct, tuple, array) this is. |
| subelement *fieldInfo // e.g. ".a.b[*].c" |
| |
| // Points-to sets. |
| pts nodeset // points-to set of this node |
| prevPts nodeset // pts(n) in previous iteration (for difference propagation) |
| |
| // Graph edges |
| copyTo nodeset // simple copy constraint edges |
| |
| // Complex constraints attached to this node (x). |
| // - *loadConstraint y=*x |
| // - *offsetAddrConstraint y=&x.f or y=&x[0] |
| // - *storeConstraint *x=z |
| // - *typeAssertConstraint y=x.(T) |
| // - *invokeConstraint y=x.f(params...) |
| complex constraintset |
| } |
| |
| type constraint interface { |
| String() string |
| |
| // Called by solver to prepare a constraint, e.g. to |
| // - initialize a points-to set (addrConstraint). |
| // - attach it to a pointer node (complex constraints). |
| init(a *analysis) |
| |
| // solve is called for complex constraints when the pts for |
| // the node to which they are attached has changed. |
| solve(a *analysis, n *node, delta nodeset) |
| } |
| |
| // dst = &src |
| // pts(dst) ⊇ {src} |
| // A base constraint used to initialize the solver's pt sets |
| type addrConstraint struct { |
| dst nodeid |
| src nodeid |
| } |
| |
| // dst = src |
| // A simple constraint represented directly as a copyTo graph edge. |
| type copyConstraint struct { |
| dst nodeid |
| src nodeid |
| } |
| |
| // dst = src[offset] |
| // A complex constraint attached to src (the pointer) |
| type loadConstraint struct { |
| offset uint32 |
| dst nodeid |
| src nodeid |
| } |
| |
| // dst[offset] = src |
| // A complex constraint attached to dst (the pointer) |
| type storeConstraint struct { |
| offset uint32 |
| dst nodeid |
| src nodeid |
| } |
| |
| // dst = &src.f or dst = &src[0] |
| // A complex constraint attached to dst (the pointer) |
| type offsetAddrConstraint struct { |
| offset uint32 |
| dst nodeid |
| src nodeid |
| } |
| |
| // dst = src.(typ) |
| // A complex constraint attached to src (the interface). |
| type typeAssertConstraint struct { |
| typ types.Type |
| dst nodeid |
| src nodeid |
| } |
| |
| // src.method(params...) |
| // A complex constraint attached to iface. |
| type invokeConstraint struct { |
| method *types.Func // the abstract method |
| iface nodeid // the interface |
| params nodeid // the first parameter in the params/results block |
| } |
| |
| // An analysis instance holds the state of a single pointer analysis problem. |
| type analysis struct { |
| config *Config // the client's control/observer interface |
| prog *ssa.Program // the program being analyzed |
| log io.Writer // log stream; nil to disable |
| panicNode nodeid // sink for panic, source for recover |
| nodes []*node // indexed by nodeid |
| flattenMemo map[types.Type][]*fieldInfo // memoization of flatten() |
| constraints []constraint // set of constraints |
| callsites []*callsite // all callsites |
| genq []*cgnode // queue of functions to generate constraints for |
| intrinsics map[*ssa.Function]intrinsic // non-nil values are summaries for intrinsic fns |
| reflectValueObj types.Object // type symbol for reflect.Value (if present) |
| reflectRtypeObj types.Object // type symbol for reflect.rtype (if present) |
| reflectRtype *types.Pointer // *reflect.rtype |
| funcObj map[*ssa.Function]nodeid // default function object for each func |
| probes map[*ssa.CallCommon]nodeid // maps call to print() to argument variable |
| valNode map[ssa.Value]nodeid // node for each ssa.Value |
| work worklist // solver's worklist |
| } |
| |
| func (a *analysis) warnf(pos token.Pos, format string, args ...interface{}) { |
| if Warn := a.config.Warn; Warn != nil { |
| Warn(pos, format, args...) |
| } else { |
| fmt.Fprintf(os.Stderr, "%s: warning: ", a.prog.Fset.Position(pos)) |
| fmt.Fprintf(os.Stderr, format, args...) |
| fmt.Fprintln(os.Stderr) |
| } |
| } |
| |
| // Analyze runs the pointer analysis with the scope and options |
| // specified by config, and returns the (synthetic) root of the callgraph. |
| // |
| func Analyze(config *Config) CallGraphNode { |
| a := &analysis{ |
| config: config, |
| log: config.Log, |
| prog: config.prog(), |
| valNode: make(map[ssa.Value]nodeid), |
| flattenMemo: make(map[types.Type][]*fieldInfo), |
| intrinsics: make(map[*ssa.Function]intrinsic), |
| funcObj: make(map[*ssa.Function]nodeid), |
| probes: make(map[*ssa.CallCommon]nodeid), |
| work: makeMapWorklist(), |
| } |
| |
| if reflect := a.prog.ImportedPackage("reflect"); reflect != nil { |
| a.reflectValueObj = reflect.Object.Scope().Lookup("Value") |
| a.reflectRtypeObj = reflect.Object.Scope().Lookup("rtype") |
| a.reflectRtype = types.NewPointer(a.reflectRtypeObj.Type()) |
| } |
| |
| if false { |
| a.log = os.Stderr // for debugging crashes; extremely verbose |
| } |
| |
| if a.log != nil { |
| fmt.Fprintln(a.log, "======== NEW ANALYSIS ========") |
| } |
| |
| root := a.generate() |
| |
| // ---------- Presolver ---------- |
| |
| // TODO(adonovan): opt: presolver optimisations. |
| |
| // ---------- Solver ---------- |
| |
| a.solve() |
| |
| if a.log != nil { |
| // Dump solution. |
| for i, n := range a.nodes { |
| if n.pts != nil { |
| fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, n.pts, n.typ) |
| } |
| } |
| } |
| |
| // Notify the client of the callsites if they're interested. |
| if CallSite := a.config.CallSite; CallSite != nil { |
| for _, site := range a.callsites { |
| CallSite(site) |
| } |
| } |
| |
| Call := a.config.Call |
| for _, site := range a.callsites { |
| for nid := range a.nodes[site.targets].pts { |
| cgn := a.nodes[nid].data.(*cgnode) |
| |
| // Notify the client of the call graph, if |
| // they're interested. |
| if Call != nil { |
| Call(site, cgn) |
| } |
| |
| // Warn about calls to non-intrinsic external functions. |
| |
| if fn := cgn.fn; fn.Blocks == nil && a.findIntrinsic(fn) == nil { |
| a.warnf(site.Pos(), "unsound call to unknown intrinsic: %s", fn) |
| a.warnf(fn.Pos(), " (declared here)") |
| } |
| } |
| } |
| |
| return root |
| } |