go.tools/go/pointer: node renumbering
This change renumbers nodes so that addressable ones
(that may appear in a points-to set) all have lower
numbers than non-addressable ones----initially at least:
reflection, SetFinalizer, etc add new nodes during
solving.
This improves the efficiency of sparse PTS
representations (to be added later). The largest int in
a PTS is now about 20% of the previous max.
Overview:
- move constraint stuff into constraint.go.
- add two methods to constraint:
(1) renumber(): renumbers all nodeids. The
implementations are very repetitive but simple. I
thought hard about other ways (mixins, reflection)
but decided this one was fine.
(2) indirect(): report the set of nodeids whose
points-to relations depend on the solver, not just
the initial constraint graph.
(This method is currently unused and is logically
part of a forthcoming change to implement PE/LE
presolver optimizations. (Perhaps I should comment
it out/remove it for now.)
- split up the population of the intrinsics map by file.
- delete analysis.probes (unused field)
- remove state="..." from panic message; unnecessary.
LGTM=crawshaw
R=crawshaw
CC=golang-codereviews
https://golang.org/cl/73320043
diff --git a/go/pointer/analysis.go b/go/pointer/analysis.go
index 1464982..42deb0b 100644
--- a/go/pointer/analysis.go
+++ b/go/pointer/analysis.go
@@ -102,91 +102,6 @@
complex constraintset
}
-type constraint interface {
- String() string
-
- // For a complex constraint, returns the nodeid of the pointer
- // to which it is attached.
- ptr() nodeid
-
- // 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 // (ptr)
- src nodeid
-}
-
-// dst = src
-// A simple constraint represented directly as a copyTo graph edge.
-type copyConstraint struct {
- dst nodeid
- src nodeid // (ptr)
-}
-
-// dst = src[offset]
-// A complex constraint attached to src (the pointer)
-type loadConstraint struct {
- offset uint32
- dst nodeid
- src nodeid // (ptr)
-}
-
-// dst[offset] = src
-// A complex constraint attached to dst (the pointer)
-type storeConstraint struct {
- offset uint32
- dst nodeid // (ptr)
- 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 // (ptr)
-}
-
-// dst = src.(typ) where typ is an interface
-// A complex constraint attached to src (the interface).
-// No representation change: pts(dst) and pts(src) contains tagged objects.
-type typeFilterConstraint struct {
- typ types.Type // an interface type
- dst nodeid
- src nodeid // (ptr)
-}
-
-// dst = src.(typ) where typ is a concrete type
-// A complex constraint attached to src (the interface).
-//
-// If exact, only tagged objects identical to typ are untagged.
-// If !exact, tagged objects assignable to typ are untagged too.
-// The latter is needed for various reflect operators, e.g. Send.
-//
-// This entails a representation change:
-// pts(src) contains tagged objects,
-// pts(dst) contains their payloads.
-type untagConstraint struct {
- typ types.Type // a concrete type
- dst nodeid
- src nodeid // (ptr)
- exact bool
-}
-
-// src.method(params...)
-// A complex constraint attached to iface.
-type invokeConstraint struct {
- method *types.Func // the abstract method
- iface nodeid // (ptr) 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
@@ -200,7 +115,6 @@
cgnodes []*cgnode // all cgnodes
genq []*cgnode // queue of functions to generate constraints for
intrinsics map[*ssa.Function]intrinsic // non-nil values are summaries for intrinsic fns
- probes map[*ssa.CallCommon]nodeid // maps call to print() to argument variable
globalval map[ssa.Value]nodeid // node for each global ssa.Value
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
@@ -291,10 +205,9 @@
// always succeed. An error can occur only due to an internal bug.
//
func Analyze(config *Config) (result *Result, err error) {
- stage := "setup"
defer func() {
if p := recover(); p != nil {
- err = fmt.Errorf("internal error in pointer analysis %s: %v (please report this bug)", stage, p)
+ err = fmt.Errorf("internal error in pointer analysis: %v (please report this bug)", p)
fmt.Fprintln(os.Stderr, "Internal panic in pointer analysis:")
debug.PrintStack()
}
@@ -360,7 +273,6 @@
}
a.computeTrackBits()
- stage = "constraint generation"
a.generate()
if a.log != nil {
@@ -376,23 +288,11 @@
fmt.Fprintf(a.log, "# nodes:\t%d\n", len(a.nodes))
}
- // stage = "constraint optimization"
- // a.optimize()
+ a.optimize()
- stage = "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)
- }
- }
- }
-
// Create callgraph.Nodes in deterministic order.
- stage = "callgraph construction"
if cg := a.result.CallGraph; cg != nil {
for _, caller := range a.cgnodes {
cg.CreateNode(caller.fn)
