go.tools/pointer: opt: type-based label tracking reduces solver time by up to 75%.
Observation: not all alias facts are interesting.
- A channel-peers query also cares about pointers of kind chan.
- An oracle "points-to" query on an expression of kind map
only cares about maps.
- We always care about func, interface and reflect.Value,
since they're needed for sound analysis of dynamic dispatch.
We needn't bother collecting alias information for
uninteresting pointers, and this massively reduces the number
of labels flowing in to the constraint system.
The only constraints that create new labels are addressOf
and offsetAddr; both are now selectively emitted by type.
We compute the set of type kinds to track, based on the
{Indirect,}Query types. (We could enable tracking at an
even finer grain if we want.)
This requires that we can see all the {Indirect,}Query
value types a priori, which is not the case for the PrintCalls
mechanism used in the tests, so I have rewritten the latter
to use {Indirect,}Query instead.
This reduces the solver-phase time for the entire standard
library and tests from >8m to <2m. Similar speedups are
obtained on small and medium-sized programs.
Details:
- shouldTrack inspects the flattened form of a type to see if
it contains fields we must track. It memoizes the result.
- added precondition checks to (*Config).Add{,Indirect}Query.
- added (*ssa.Program).LookupMethod convenience method.
- added Example of how to use the Query mechanism.
- removed code made dead by a recent invariant:
the only pointerlike Const value is nil.
- don't generate constraints for any functions in "reflect".
(we had forgotten to skip synthetic wrappers too).
- write PTA warnings to the log.
- add annotations for more intrinsics.
LGTM=gri, crawshaw
R=crawshaw, gri
CC=golang-codereviews
https://golang.org/cl/62540043
diff --git a/go/pointer/analysis.go b/go/pointer/analysis.go
index 4cc310b..8896ada 100644
--- a/go/pointer/analysis.go
+++ b/go/pointer/analysis.go
@@ -193,6 +193,7 @@
panicNode nodeid // sink for panic, source for recover
nodes []*node // indexed by nodeid
flattenMemo map[types.Type][]*fieldInfo // memoization of flatten()
+ trackTypes map[types.Type]bool // memoization of shouldTrack()
constraints []constraint // set of constraints
cgnodes []*cgnode // all cgnodes
genq []*cgnode // queue of functions to generate constraints for
@@ -204,6 +205,7 @@
localobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
work worklist // solver's worklist
result *Result // results of the analysis
+ track track // pointerlike types whose aliasing we track
// Reflection & intrinsics:
hasher typemap.Hasher // cache of type hashes
@@ -243,7 +245,41 @@
}
func (a *analysis) warnf(pos token.Pos, format string, args ...interface{}) {
- a.result.Warnings = append(a.result.Warnings, Warning{pos, fmt.Sprintf(format, args...)})
+ msg := fmt.Sprintf(format, args...)
+ if a.log != nil {
+ fmt.Fprintf(a.log, "%s: warning: %s\n", a.prog.Fset.Position(pos), msg)
+ }
+ a.result.Warnings = append(a.result.Warnings, Warning{pos, msg})
+}
+
+// computeTrackBits sets a.track to the necessary 'track' bits for the pointer queries.
+func (a *analysis) computeTrackBits() {
+ var queryTypes []types.Type
+ for v := range a.config.Queries {
+ queryTypes = append(queryTypes, v.Type())
+ }
+ for v := range a.config.IndirectQueries {
+ queryTypes = append(queryTypes, mustDeref(v.Type()))
+ }
+ for _, t := range queryTypes {
+ switch t.Underlying().(type) {
+ case *types.Chan:
+ a.track |= trackChan
+ case *types.Map:
+ a.track |= trackMap
+ case *types.Pointer:
+ a.track |= trackPtr
+ case *types.Slice:
+ a.track |= trackSlice
+ case *types.Interface:
+ a.track = trackAll
+ return
+ }
+ if rVObj := a.reflectValueObj; rVObj != nil && types.Identical(t, rVObj.Type()) {
+ a.track = trackAll
+ return
+ }
+ }
}
// Analyze runs the pointer analysis with the scope and options
@@ -257,13 +293,13 @@
globalval: make(map[ssa.Value]nodeid),
globalobj: make(map[ssa.Value]nodeid),
flattenMemo: make(map[types.Type][]*fieldInfo),
+ trackTypes: make(map[types.Type]bool),
hasher: typemap.MakeHasher(),
intrinsics: make(map[*ssa.Function]intrinsic),
work: makeMapWorklist(),
result: &Result{
Queries: make(map[ssa.Value][]Pointer),
IndirectQueries: make(map[ssa.Value][]Pointer),
- PrintCalls: make(map[*ssa.CallCommon]Pointer),
},
}
@@ -278,7 +314,7 @@
if reflect := a.prog.ImportedPackage("reflect"); reflect != nil {
rV := reflect.Object.Scope().Lookup("Value")
a.reflectValueObj = rV
- a.reflectValueCall = a.prog.Method(a.prog.MethodSets.MethodSet(rV.Type()).Lookup(nil, "Call"))
+ a.reflectValueCall = a.prog.LookupMethod(rV.Type(), nil, "Call")
a.reflectType = reflect.Object.Scope().Lookup("Type").Type().(*types.Named)
a.reflectRtypeObj = reflect.Object.Scope().Lookup("rtype")
a.reflectRtypePtr = types.NewPointer(a.reflectRtypeObj.Type())
@@ -287,12 +323,18 @@
tReflectValue := a.reflectValueObj.Type()
a.flattenMemo[tReflectValue] = []*fieldInfo{{typ: tReflectValue}}
+ // Override shouldTrack of reflect.Value and *reflect.rtype.
+ // Always track pointers of these types.
+ a.trackTypes[tReflectValue] = true
+ a.trackTypes[a.reflectRtypePtr] = true
+
a.rtypes.SetHasher(a.hasher)
a.reflectZeros.SetHasher(a.hasher)
}
if runtime := a.prog.ImportedPackage("runtime"); runtime != nil {
a.runtimeSetFinalizer = runtime.Func("SetFinalizer")
}
+ a.computeTrackBits()
root := a.generate()
