go.tools/go/pointer: remove context-sensitivity from API.
Previously, each {Indirect,}Query would return a set of Pointers, one per context; now it returns (at most) one Pointer combining information from all contexts.
The old API was more faithful to the implementation concepts, but the analysis is not sufficiently context-sensitive that it makes sense: all existing clients simply throw away the context information---so now we do that for them.
(I may remove the context-sensitivity from the callgraph too, but I'll benchmark that first to see if it reduces precision.)
LGTM=crawshaw
R=crawshaw
CC=golang-codereviews
https://golang.org/cl/66130044
diff --git a/go/pointer/analysis.go b/go/pointer/analysis.go
index 4741caf..44875e9 100644
--- a/go/pointer/analysis.go
+++ b/go/pointer/analysis.go
@@ -298,8 +298,8 @@
intrinsics: make(map[*ssa.Function]intrinsic),
work: makeMapWorklist(),
result: &Result{
- Queries: make(map[ssa.Value][]Pointer),
- IndirectQueries: make(map[ssa.Value][]Pointer),
+ Queries: make(map[ssa.Value]Pointer),
+ IndirectQueries: make(map[ssa.Value]Pointer),
},
}
diff --git a/go/pointer/api.go b/go/pointer/api.go
index 3925b63..8932581 100644
--- a/go/pointer/api.go
+++ b/go/pointer/api.go
@@ -47,13 +47,6 @@
// variable for v or *v. Upon completion the client can
// inspect that map for the results.
//
- // If a Value belongs to a function that the analysis treats
- // context-sensitively, the corresponding Result.{Indirect,}Queries
- // slice may have multiple Pointers, one per distinct context.
- // Use PointsToCombined to merge them.
- // TODO(adonovan): need we distinguish contexts? Current
- // clients always combine them.
- //
// TODO(adonovan): this API doesn't scale well for batch tools
// that want to dump the entire solution. Perhaps optionally
// populate a map[*ssa.DebugRef]Pointer in the Result, one
@@ -122,10 +115,10 @@
// See Config for how to request the various Result components.
//
type Result struct {
- CallGraph callgraph.Graph // discovered call graph
- Queries map[ssa.Value][]Pointer // pts(v) for each v in Config.Queries.
- IndirectQueries map[ssa.Value][]Pointer // pts(*v) for each v in Config.IndirectQueries.
- Warnings []Warning // warnings of unsoundness
+ CallGraph callgraph.Graph // discovered call graph
+ Queries map[ssa.Value]Pointer // pts(v) for each v in Config.Queries.
+ IndirectQueries map[ssa.Value]Pointer // pts(*v) for each v in Config.IndirectQueries.
+ Warnings []Warning // warnings of unsoundness
}
// A Pointer is an equivalence class of pointer-like values.
@@ -134,9 +127,8 @@
// types may alias the same object.
//
type Pointer struct {
- a *analysis
- cgn *cgnode
- n nodeid // non-zero
+ a *analysis
+ n nodeid // non-zero
}
// A PointsToSet is a set of labels (locations or allocations).
@@ -145,26 +137,6 @@
pts nodeset
}
-// Union returns the set containing all the elements of each set in sets.
-func Union(sets ...PointsToSet) PointsToSet {
- var union PointsToSet
- for _, set := range sets {
- union.a = set.a
- union.pts.addAll(set.pts)
- }
- return union
-}
-
-// PointsToCombined returns the combined points-to set of all the
-// specified pointers.
-func PointsToCombined(ptrs []Pointer) PointsToSet {
- var ptsets []PointsToSet
- for _, ptr := range ptrs {
- ptsets = append(ptsets, ptr.PointsTo())
- }
- return Union(ptsets...)
-}
-
func (s PointsToSet) String() string {
var buf bytes.Buffer
fmt.Fprintf(&buf, "[")
@@ -192,11 +164,9 @@
// types that it may contain. (For an interface, they will
// always be concrete types.)
//
-// The result is a mapping whose keys are the dynamic types to
-// which it may point. For each pointer-like key type, the
-// corresponding map value is a set of pointer abstractions of
-// that dynamic type, represented as a []Pointer slice. Use
-// PointsToCombined to merge them.
+// The result is a mapping whose keys are the dynamic types to which
+// it may point. For each pointer-like key type, the corresponding
+// map value is the PointsToSet for pointers of that type.
//
// The result is empty unless CanHaveDynamicTypes(T).
//
@@ -211,8 +181,12 @@
if indirect {
panic("indirect tagged object") // implement later
}
- prev, _ := tmap.At(tDyn).([]Pointer)
- tmap.Set(tDyn, append(prev, Pointer{s.a, nil, v}))
+ pts, ok := tmap.At(tDyn).(PointsToSet)
+ if !ok {
+ pts = PointsToSet{s.a, make(nodeset)}
+ tmap.Set(tDyn, pts)
+ }
+ pts.pts.addAll(s.a.nodes[v].pts)
}
return &tmap
}
@@ -232,12 +206,6 @@
return fmt.Sprintf("n%d", p.n)
}
-// Context returns the context of this pointer,
-// if it corresponds to a local variable.
-func (p Pointer) Context() callgraph.Node {
- return p.cgn
-}
-
// PointsTo returns the points-to set of this pointer.
func (p Pointer) PointsTo() PointsToSet {
return PointsToSet{p.a, p.a.nodes[p.n].pts}
diff --git a/go/pointer/example_test.go b/go/pointer/example_test.go
index 71210b4..7f518af 100644
--- a/go/pointer/example_test.go
+++ b/go/pointer/example_test.go
@@ -102,9 +102,8 @@
// Print the labels of (C).f(m)'s points-to set.
fmt.Println("m may point to:")
- ptset := pointer.PointsToCombined(result.Queries[Cfm])
var labels []string
- for _, l := range ptset.Labels() {
+ for _, l := range result.Queries[Cfm].PointsTo().Labels() {
label := fmt.Sprintf(" %s: %s", prog.Fset.Position(l.Pos()), l)
labels = append(labels, label)
}
diff --git a/go/pointer/gen.go b/go/pointer/gen.go
index dcaf76c..1a2bfcf 100644
--- a/go/pointer/gen.go
+++ b/go/pointer/gen.go
@@ -79,28 +79,33 @@
fmt.Fprintf(a.log, "\tval[%s] = n%d (%T)\n", v.Name(), id, v)
}
- // TODO(adonovan): due to context-sensitivity, we may
- // encounter the same Value in many contexts. In a follow-up,
- // let's merge them to a canonical node, since that's what all
- // clients want.
- // ptr, ok := a.result.Queries[v]
- // if !ok {
- // // First time? Create the canonical probe node.
- // ptr = Pointer{a, nil, a.addNodes(t, "query")}
- // a.result.Queries[v] = ptr
- // }
- // a.copy(ptr.n, id, a.sizeof(v.Type()))
+ // Due to context-sensitivity, we may encounter the same Value
+ // in many contexts. We merge them to a canonical node, since
+ // that's what all clients want.
// Record the (v, id) relation if the client has queried pts(v).
if _, ok := a.config.Queries[v]; ok {
- a.result.Queries[v] = append(a.result.Queries[v], Pointer{a, cgn, id})
+ t := v.Type()
+ ptr, ok := a.result.Queries[v]
+ if !ok {
+ // First time? Create the canonical query node.
+ ptr = Pointer{a, a.addNodes(t, "query")}
+ a.result.Queries[v] = ptr
+ }
+ a.result.Queries[v] = ptr
+ a.copy(ptr.n, id, a.sizeof(t))
}
// Record the (*v, id) relation if the client has queried pts(*v).
if _, ok := a.config.IndirectQueries[v]; ok {
- indirect := a.addNodes(v.Type(), "query.indirect")
- a.genLoad(cgn, indirect, v, 0, a.sizeof(v.Type()))
- a.result.IndirectQueries[v] = append(a.result.IndirectQueries[v], Pointer{a, cgn, indirect})
+ t := v.Type()
+ ptr, ok := a.result.IndirectQueries[v]
+ if !ok {
+ // First time? Create the canonical indirect query node.
+ ptr = Pointer{a, a.addNodes(v.Type(), "query.indirect")}
+ a.result.IndirectQueries[v] = ptr
+ }
+ a.genLoad(cgn, ptr.n, v, 0, a.sizeof(t))
}
}
diff --git a/go/pointer/pointer_test.go b/go/pointer/pointer_test.go
index 9f76a22..f8bee71 100644
--- a/go/pointer/pointer_test.go
+++ b/go/pointer/pointer_test.go
@@ -137,14 +137,14 @@
}
// Find probe (call to print(x)) of same source file/line as expectation.
-func findProbe(prog *ssa.Program, probes map[*ssa.CallCommon]bool, queries map[ssa.Value][]pointer.Pointer, e *expectation) (site *ssa.CallCommon, pts pointer.PointsToSet) {
+func findProbe(prog *ssa.Program, probes map[*ssa.CallCommon]bool, queries map[ssa.Value]pointer.Pointer, e *expectation) (site *ssa.CallCommon, pts pointer.PointsToSet) {
for call := range probes {
pos := prog.Fset.Position(call.Pos())
if pos.Line == e.linenum && pos.Filename == e.filename {
// TODO(adonovan): send this to test log (display only on failure).
// fmt.Printf("%s:%d: info: found probe for %s: %s\n",
// e.filename, e.linenum, e, p.arg0) // debugging
- return call, pointer.PointsToCombined(queries[call.Args[0]])
+ return call, queries[call.Args[0]].PointsTo()
}
}
return // e.g. analysis didn't reach this call
