go.tools/pointer: strength reduction during constraint generation.
Motivation: simple constraints---copy and addr---are more
amenable to pre-solver optimizations (forthcoming) than
complex constraints: load, store, and all others.
In code such as the following:
t0 = new struct { x, y int }
t1 = &t0.y
t2 = *t1
there's no need for the full generality of a (complex)
load constraint for t2=*t1 since t1 can only point to t0.y.
All we need is a (simple) copy constraint t2 = (t0.y)
where (t0.y) is the object node label for that field.
For all "addressable" SSA instructions, we tabulate
whether their points-to set is necessarily a singleton. For
some (e.g. Alloc, MakeSlice, etc) this is always true by
design. For others (e.g. FieldAddr) it depends on their
operands.
We exploit this information when generating constraints:
all load-form and store-form constraints are reduced to copy
constraints if the pointer's PTS is a singleton.
Similarly all FieldAddr (y=&x.f) and IndexAddr (y=&x[0])
constraints are reduced to offset addition, for singleton
operands.
Here's the constraint mix when running on the oracle itself.
The total number of constraints is unchanged but the fraction
that are complex has gone down to 21% from 53%.
before after
--simple--
addr 20682 46949
copy 61454 91211
--complex--
offsetAddr 41621 15325
load 18769 12925
store 30758 6908
invoke 758 760
typeAssert 1688 1689
total 175832 175869
Also:
- Add Pointer.Context() for local variables,
since we now plumb cgnodes throughout. Nice.
- Refactor all load-form (load, receive, lookup) and
store-form (Store, send, MapUpdate) constraints to use
genLoad and genStore.
- Log counts of constraints by type.
- valNodes split into localval and globalval maps;
localval is purged after each function.
- analogous maps localobj[v] and globalobj[v] hold sole label
for pts(v), if singleton.
- fnObj map subsumed by globalobj.
- make{Function/Global/Constant} inlined into objectValue.
Much cleaner.
R=crawshaw
CC=golang-dev
https://golang.org/cl/13979043
diff --git a/pointer/analysis.go b/pointer/analysis.go
index c7d666a..75933b8 100644
--- a/pointer/analysis.go
+++ b/pointer/analysis.go
@@ -11,6 +11,7 @@
"go/token"
"io"
"os"
+ "reflect"
"code.google.com/p/go.tools/go/types"
"code.google.com/p/go.tools/go/types/typemap"
@@ -176,9 +177,11 @@
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
- funcObj map[*ssa.Function]nodeid // default function object for each func
probes map[*ssa.CallCommon]nodeid // maps call to print() to argument variable
- valNode map[ssa.Value]nodeid // node for each ssa.Value
+ 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
+ localobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton
work worklist // solver's worklist
queries map[ssa.Value][]Pointer // same as Results.Queries
@@ -235,16 +238,24 @@
config: config,
log: config.Log,
prog: config.prog(),
- valNode: make(map[ssa.Value]nodeid),
+ globalval: make(map[ssa.Value]nodeid),
+ globalobj: make(map[ssa.Value]nodeid),
flattenMemo: make(map[types.Type][]*fieldInfo),
hasher: typemap.MakeHasher(),
intrinsics: make(map[*ssa.Function]intrinsic),
- funcObj: make(map[*ssa.Function]nodeid),
probes: make(map[*ssa.CallCommon]nodeid),
work: makeMapWorklist(),
queries: make(map[ssa.Value][]Pointer),
}
+ if false {
+ a.log = os.Stderr // for debugging crashes; extremely verbose
+ }
+
+ if a.log != nil {
+ fmt.Fprintln(a.log, "======== NEW ANALYSIS ========")
+ }
+
if reflect := a.prog.ImportedPackage("reflect"); reflect != nil {
a.reflectValueObj = reflect.Object.Scope().Lookup("Value")
a.reflectType = reflect.Object.Scope().Lookup("Type").Type().(*types.Named)
@@ -259,16 +270,21 @@
a.reflectZeros.SetHasher(a.hasher)
}
- if false {
- a.log = os.Stderr // for debugging crashes; extremely verbose
- }
+ root := a.generate()
if a.log != nil {
- fmt.Fprintln(a.log, "======== NEW ANALYSIS ========")
+ // Show size of constraint system.
+ counts := make(map[reflect.Type]int)
+ for _, c := range a.constraints {
+ counts[reflect.TypeOf(c)]++
+ }
+ fmt.Fprintf(a.log, "# constraints:\t%d\n", len(a.constraints))
+ for t, n := range counts {
+ fmt.Fprintf(a.log, "\t%s:\t%d\n", t, n)
+ }
+ fmt.Fprintf(a.log, "# nodes:\t%d\n", len(a.nodes))
}
- root := a.generate()
-
//a.optimize()
a.solve()
