go/pointer: use sparse bit vectors to represent points-to sets in solver.
This optimization reduces solve time (typically >90% of the
total) by about 78% when analysing real programs. It also
makes the solver 100% deterministic since all iterations are
ordered.
Also:
- remove unnecessary nodeid parameter to solve() method.
- don't add a fieldInfo for singleton tuples (cosmetic fix).
- inline+simplify "worklist" type.
- replace "constraintset" type by a slice.
LGTM=crawshaw
R=crawshaw
CC=golang-codereviews
https://golang.org/cl/95240043
diff --git a/go/pointer/analysis.go b/go/pointer/analysis.go
index 699462b..884962b 100644
--- a/go/pointer/analysis.go
+++ b/go/pointer/analysis.go
@@ -99,7 +99,7 @@
// - *typeFilterConstraint y=x.(I)
// - *untagConstraint y=x.(C)
// - *invokeConstraint y=x.f(params...)
- complex constraintset
+ complex []constraint
}
// An analysis instance holds the state of a single pointer analysis problem.
@@ -119,9 +119,10 @@
globalobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
localval map[ssa.Value]nodeid // node for each local ssa.Value
localobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
- work worklist // solver's worklist
+ work nodeset // solver's worklist
result *Result // results of the analysis
track track // pointerlike types whose aliasing we track
+ deltaSpace []int // working space for iterating over PTS deltas
// Reflection & intrinsics:
hasher typeutil.Hasher // cache of type hashes
@@ -223,11 +224,11 @@
trackTypes: make(map[types.Type]bool),
hasher: typeutil.MakeHasher(),
intrinsics: make(map[*ssa.Function]intrinsic),
- work: makeMapWorklist(),
result: &Result{
Queries: make(map[ssa.Value]Pointer),
IndirectQueries: make(map[ssa.Value]Pointer),
},
+ deltaSpace: make([]int, 0, 100),
}
if false {
@@ -300,10 +301,11 @@
}
// Add dynamic edges to call graph.
+ var space [100]int
for _, caller := range a.cgnodes {
for _, site := range caller.sites {
- for callee := range a.nodes[site.targets].pts {
- a.callEdge(caller, site, callee)
+ for _, callee := range a.nodes[site.targets].pts.AppendTo(space[:0]) {
+ a.callEdge(caller, site, nodeid(callee))
}
}
}
