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/gen.go b/go/pointer/gen.go
index ce190d1..dcaf76c 100644
--- a/go/pointer/gen.go
+++ b/go/pointer/gen.go
@@ -79,6 +79,18 @@
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()))
+
// 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})
@@ -173,7 +185,7 @@
id := a.makeTagged(a.reflectRtypePtr, nil, T)
a.nodes[id+1].typ = T // trick (each *rtype tagged object is a singleton)
- a.addressOf(id+1, obj)
+ a.addressOf(a.reflectRtypePtr, id+1, obj)
a.rtypes.Set(T, id)
return id
@@ -207,7 +219,7 @@
}
id = a.addOneNode(v.Type(), comment, nil)
if obj := a.objectNode(nil, v); obj != 0 {
- a.addressOf(id, obj)
+ a.addressOf(v.Type(), id, obj)
}
a.setValueNode(v, id, nil)
}
@@ -290,14 +302,17 @@
}
// addressOf creates a constraint of the form id = &obj.
-func (a *analysis) addressOf(id, obj nodeid) {
+// T is the type of the address.
+func (a *analysis) addressOf(T types.Type, id, obj nodeid) {
if id == 0 {
panic("addressOf: zero id")
}
if obj == 0 {
panic("addressOf: zero obj")
}
- a.addConstraint(&addrConstraint{id, obj})
+ if a.shouldTrack(T) {
+ a.addConstraint(&addrConstraint{id, obj})
+ }
}
// load creates a load constraint of the form dst = src[offset].
@@ -344,8 +359,12 @@
// offsetAddr creates an offsetAddr constraint of the form dst = &src.#offset.
// offset is the field offset in logical fields.
+// T is the type of the address.
//
-func (a *analysis) offsetAddr(dst, src nodeid, offset uint32) {
+func (a *analysis) offsetAddr(T types.Type, dst, src nodeid, offset uint32) {
+ if !a.shouldTrack(T) {
+ return
+ }
if offset == 0 {
// Simplify dst = &src->f0
// to dst = src
@@ -432,7 +451,7 @@
// unsafe conversions soundly; see TODO file.
obj := a.addNodes(mustDeref(tDst), "unsafe.Pointer conversion")
a.endObject(obj, cgn, conv)
- a.addressOf(res, obj)
+ a.addressOf(tDst, res, obj)
return
}
@@ -441,7 +460,7 @@
if utSrc.Info()&types.IsString != 0 {
obj := a.addNodes(sliceToArray(tDst), "convert")
a.endObject(obj, cgn, conv)
- a.addressOf(res, obj)
+ a.addressOf(tDst, res, obj)
return
}
@@ -499,8 +518,8 @@
a.addNodes(tArray, "append")
a.endObject(w, cgn, instr)
- a.copyElems(cgn, tArray.Elem(), z, y) // *z = *y
- a.addressOf(a.valueNode(z), w) // z = &w
+ a.copyElems(cgn, tArray.Elem(), z, y) // *z = *y
+ a.addressOf(instr.Type(), a.valueNode(z), w) // z = &w
}
// genBuiltinCall generates contraints for a call to a built-in.
@@ -523,29 +542,8 @@
a.copy(a.valueNode(v), a.panicNode, 1)
}
- case "print":
- // Analytically print is a no-op, but it's a convenient hook
- // for testing the pts of an expression, so we notify the client.
- // Existing uses in Go core libraries are few and harmless.
- if a.config.QueryPrintCalls {
- // Due to context-sensitivity, we may encounter
- // the same print() call in many contexts, so
- // we merge them to a canonical node.
-
- t := call.Args[0].Type()
-
- ptr, ok := a.result.PrintCalls[call]
- if !ok {
- // First time? Create the canonical probe node.
- ptr = Pointer{a, nil, a.addNodes(t, "print")}
- a.result.PrintCalls[call] = ptr
- }
- probe := ptr.n
- a.copy(probe, a.valueNode(call.Args[0]), a.sizeof(t))
- }
-
default:
- // No-ops: close len cap real imag complex println delete.
+ // No-ops: close len cap real imag complex print println delete.
}
}
@@ -605,7 +603,7 @@
dotdotdot := false
ret := reflectCallImpl(a, caller, site, a.valueNode(call.Args[0]), a.valueNode(call.Args[1]), dotdotdot)
if result != 0 {
- a.addressOf(result, ret)
+ a.addressOf(fn.Signature.Results().At(0).Type(), result, ret)
}
return
}
@@ -720,8 +718,7 @@
a.typeAssert(a.reflectRtypePtr, rtype, recv, true)
// Look up the concrete method.
- meth := a.prog.MethodSets.MethodSet(a.reflectRtypePtr).Lookup(call.Method.Pkg(), call.Method.Name())
- fn := a.prog.Method(meth)
+ fn := a.prog.LookupMethod(a.reflectRtypePtr, call.Method.Pkg(), call.Method.Name())
obj := a.makeFunctionObject(fn, site) // new contour for this call
a.callEdge(site, obj)
@@ -731,7 +728,7 @@
sig := fn.Signature // concrete method
targets := a.addOneNode(sig, "call.targets", nil)
- a.addressOf(targets, obj) // (a singleton)
+ a.addressOf(sig, targets, obj) // (a singleton)
// Copy receiver.
params := a.funcParams(obj)
@@ -814,12 +811,7 @@
obj = a.makeFunctionObject(v, nil)
case *ssa.Const:
- if t, ok := v.Type().Underlying().(*types.Slice); ok && !v.IsNil() {
- // Non-nil []byte or []rune constant.
- obj = a.nextNode()
- a.addNodes(sliceToArray(t), "array in slice constant")
- a.endObject(obj, nil, v)
- }
+ // The only pointer-like Consts are nil.
case *ssa.Capture:
// For now, Captures have the same cardinality as globals.
@@ -912,9 +904,9 @@
dst := a.valueNode(v)
if obj := a.objectNode(cgn, v); obj != 0 {
// Pre-apply offsetAddrConstraint.solve().
- a.addressOf(dst, obj)
+ a.addressOf(v.Type(), dst, obj)
} else {
- a.offsetAddr(dst, ptr, offset)
+ a.offsetAddr(v.Type(), dst, ptr, offset)
}
}
@@ -1018,7 +1010,7 @@
case *ssa.Alloc, *ssa.MakeSlice, *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeInterface:
v := instr.(ssa.Value)
- a.addressOf(a.valueNode(v), a.objectNode(cgn, v))
+ a.addressOf(v.Type(), a.valueNode(v), a.objectNode(cgn, v))
case *ssa.ChangeInterface:
a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
@@ -1251,9 +1243,10 @@
// The runtime magically allocates os.Args; so should we.
if os := a.prog.ImportedPackage("os"); os != nil {
// In effect: os.Args = new([1]string)[:]
- obj := a.addNodes(types.NewArray(types.Typ[types.String], 1), "<command-line args>")
+ T := types.NewSlice(types.Typ[types.String])
+ obj := a.addNodes(sliceToArray(T), "<command-line args>")
a.endObject(obj, nil, "<command-line args>")
- a.addressOf(a.objectNode(nil, os.Var("Args")), obj)
+ a.addressOf(T, a.objectNode(nil, os.Var("Args")), obj)
}
return root
