Repository: google/go-flow-levee
Pull request #306 (2021-04-16 06:48:03)

Ear
Fixes #<issue_number_goes_here>

> It's a good idea to open an issue first for discussion.

- [ ] Running against a large codebase such as [Kubernetes](https://github.com/kubernetes/kubernetes) does not error out. (See [DEVELOPING.md](https://github.com/google/go-flow-levee/blob/master/DEVELOPING.md) for instructions on how to do that.)
- [ ] Appropriate changes to README are included in PR


guodongli-google: Not all comments have been addressed. The remaining ones are mainly about coverage. I will add more unit tests in the next step.
guodongli-google: > "Very exciting stuff" is right!
> 
> I also still have some qualms with the level of test coverage (now closer to 80% of `analysis.go`). This can be something we iterate on in a future PR, but there are certain code paths that I'd like to see covered before we hook this up to the main analyzer.
> 
> Just as a workflow note, if you merge `master` into this PR (which should be easy now that you've resolved the conflicts), then the "new" `heap` and `state` files should be dropped from the GitHub UI. It was a clean merge on my machine.

More unit tests have been added. Now the coverage is 90%. The remaining uncovered lines are due mainly to: (1) function call handling, which is in the next PR; and (2) likely dead code (I added TODO to a main one) which I need to double check. In the end we can be close to 100% excluding the defensive Printf statements.

Patch:
diff --git a/internal/pkg/earpointer/analysis.go b/internal/pkg/earpointer/analysis.go
new file mode 100644
index 0000000..b8f69c9
--- /dev/null
+++ b/internal/pkg/earpointer/analysis.go
@@ -0,0 +1,636 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package earpointer
+
+import (
+	"fmt"
+	"go/token"
+	"go/types"
+	"reflect"
+	"strconv"
+	"strings"
+
+	"github.com/google/go-flow-levee/internal/pkg/config"
+
+	"golang.org/x/tools/go/analysis"
+	"golang.org/x/tools/go/analysis/passes/buildssa"
+	"golang.org/x/tools/go/ssa"
+)
+
+// Analyzer traverses the packages and constructs an EAR partitions
+// unifying all the IR elements in these packages.
+var Analyzer = &analysis.Analyzer{
+	Name:       "earpointer",
+	Doc:        "EAR pointer analysis",
+	Flags:      config.FlagSet,
+	Run:        run,
+	ResultType: reflect.TypeOf(new(Partitions)),
+	Requires:   []*analysis.Analyzer{buildssa.Analyzer},
+}
+
+// visitor processes the instructions in a function and perform unifications
+// for all reachable contexts for that function. Both the intra-procedural
+// instructions and inter-procedural instructions (i.e. CallInstruction) are processed.
+type visitor struct {
+	state    *state     // mutable state
+	contexts []*Context // for context sensitive analysis
+}
+
+func run(pass *analysis.Pass) (interface{}, error) {
+	ssainput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
+	vis := visitor{state: NewState(), contexts: []*Context{&emptyContext}}
+	vis.initReferences(ssainput)
+	for _, fn := range ssainput.SrcFuncs {
+		for _, blk := range fn.Blocks {
+			for _, i := range blk.Instrs {
+				vis.visitInstruction(i)
+			}
+		}
+	}
+	return vis.state.ToPartitions(), nil
+}
+
+// Insert into the state all the local references and global references.
+func (vis *visitor) initReferences(ssainput *buildssa.SSA) {
+	state := vis.state
+	for _, member := range ssainput.Pkg.Members {
+		if m, ok := member.(*ssa.Global); ok {
+			if typeMayShareObject(m.Type()) &&
+				!strings.HasPrefix(m.Name(), "init$") { // skip some synthetic variables
+				state.Insert(MakeGlobal(m))
+			}
+		}
+	}
+	for _, fn := range ssainput.SrcFuncs {
+		for _, param := range fn.Params {
+			if typeMayShareObject(param.Type()) {
+				state.Insert(MakeLocal(&emptyContext, param))
+			}
+		}
+		for _, fv := range fn.FreeVars {
+			if typeMayShareObject(fv.Type()) {
+				state.Insert(MakeLocal(&emptyContext, fv))
+			}
+		}
+		for _, blk := range fn.Blocks {
+			for _, instr := range blk.Instrs {
+				if v, ok := instr.(ssa.Value); ok && typeMayShareObject(v.Type()) {
+					state.Insert(MakeLocal(&emptyContext, v))
+				}
+			}
+		}
+	}
+}
+
+func (vis *visitor) visitInstruction(instr ssa.Instruction) {
+	switch i := instr.(type) {
+	case *ssa.FieldAddr:
+		vis.visitFieldAddr(i)
+	case *ssa.IndexAddr:
+		vis.visitIndexAddr(i)
+	case *ssa.Field:
+		vis.visitField(i)
+	case *ssa.Index:
+		vis.visitIndex(i)
+	case *ssa.Phi:
+		vis.visitPhi(i)
+	case *ssa.Store:
+		vis.visitStore(i)
+	case *ssa.MapUpdate:
+		vis.visitMapUpdate(i)
+	case *ssa.Lookup:
+		vis.visitLookup(i)
+	case *ssa.Convert:
+		vis.visitConvert(i)
+	case *ssa.ChangeInterface:
+		vis.visitChangeInterface(i)
+	case *ssa.ChangeType:
+		vis.visitChangeType(i)
+	case *ssa.TypeAssert:
+		vis.visitTypeAssert(i)
+	case *ssa.UnOp:
+		vis.visitUnOp(i)
+	case *ssa.BinOp:
+		vis.visitBinOp(i)
+	case *ssa.Extract:
+		vis.visitExtract(i)
+	case *ssa.Send:
+		vis.visitSend(i)
+	case *ssa.Slice:
+		vis.visitSlice(i)
+	case *ssa.MakeInterface:
+		vis.visitMakeInterface(i)
+	case *ssa.Select:
+		vis.visitSelect(i)
+
+	case *ssa.Call, *ssa.Go, *ssa.Defer:
+		vis.visitCall(i.(ssa.CallInstruction).Common(), instr)
+
+	case *ssa.Alloc,
+		*ssa.MakeChan,
+		*ssa.MakeClosure,
+		*ssa.MakeMap,
+		*ssa.MakeSlice:
+		// Local variables are created in the beginning of the pass by initReferences().
+		// These instructions won't be handled after that.
+	case *ssa.If,
+		*ssa.Jump:
+		// The analysis is flow insensitive.
+	case *ssa.Range:
+		// t1 = range t0: unify t0 and t1.
+		// It will be processed by the subsequent extract instruction that also handles the relevant Next.
+	case *ssa.Next:
+		// The next instruction will be processed by the subsequent extract instruction.
+	case *ssa.Return:
+		// Return is handled in visitCall().
+	case *ssa.RunDefers:
+		// To be implemented.
+	case *ssa.Panic:
+		// To be implemented.
+	case *ssa.DebugRef:
+		// Not related.
+	default:
+		fmt.Printf("unsupported instruction: %s; please report this issue\n", i)
+	}
+}
+
+func (vis *visitor) visitFieldAddr(addr *ssa.FieldAddr) {
+	// "t1 = t0.x" is implemented by t0[x -> t1] through address unification.
+	obj := addr.X
+	field := makeField(obj.Type(), addr.Field)
+	for _, c := range vis.contexts {
+		vis.unifyFieldAddress(c, obj, field, addr)
+	}
+}
+
+func (vis *visitor) visitField(field *ssa.Field) {
+	// "t1 = t0.x" is implemented by t0[x -> t1].
+	obj := field.X
+	fd := makeField(obj.Type(), field.Field)
+	vis.processHeapAccess(field, obj, *fd)
+}
+
+func (vis *visitor) visitIndexAddr(addr *ssa.IndexAddr) {
+	// "t2 = &t1[t0]" is handled through address unification.
+	vis.processIndex(addr, addr.X, addr.Index)
+}
+
+func (vis *visitor) visitIndex(index *ssa.Index) {
+	vis.processIndex(index, index.X, index.Index)
+}
+
+func (vis *visitor) visitLookup(lookup *ssa.Lookup) {
+	if !lookup.CommaOk {
+		vis.processIndex(lookup, lookup.X, lookup.Index)
+	}
+	// The comma case will be processed by the subsequent extract instruction.
+}
+
+func (vis *visitor) visitStore(store *ssa.Store) {
+	// Here store instruction "*address = data" is implemented by a
+	// semantics-equivalent (w.r.t. unification) load instruction "data =
+	// *address".
+	// The address can be a (memory) address, a global variable, or a free
+	// variable.
+	if mayShareObject(store.Val) {
+		vis.processAddressToValue(store.Addr, store.Val)
+	}
+}
+
+func (vis *visitor) visitPhi(phi *ssa.Phi) {
+	if !typeMayShareObject(phi.Type()) {
+		return
+	}
+	for _, e := range phi.Edges {
+		vis.unifyLocals(phi, e)
+	}
+}
+
+func (vis *visitor) visitMapUpdate(update *ssa.MapUpdate) {
+	vis.processIndex(update.Value, update.Map, update.Key)
+}
+
+func (vis *visitor) visitConvert(convert *ssa.Convert) {
+	vis.unifyLocals(convert, convert.X)
+}
+
+func (vis *visitor) visitChangeInterface(change *ssa.ChangeInterface) {
+	vis.unifyLocals(change, change.X)
+}
+
+func (vis *visitor) visitChangeType(change *ssa.ChangeType) {
+	vis.unifyLocals(change, change.X)
+}
+
+func (vis *visitor) visitUnOp(op *ssa.UnOp) {
+	switch op.Op {
+	case token.ARROW: // channel read
+		// Use array read to simulate channel read.
+		vis.processHeapAccess(op, op.X, anyIndexField)
+	case token.MUL:
+		// v = *addr
+		// The LHS is a register; the RHS can be a (memory) address, a global
+		// variable, or a free variable.
+		// t1 = *addr is implemented as "addr[directPointToField] = t1",
+		// i.e., address addr points to value t1.
+		vis.processAddressToValue(op.X, op)
+	}
+}
+
+func (vis *visitor) visitBinOp(op *ssa.BinOp) {
+	// Numeric binop will be skipped.
+	// The only binop that matters now is "+" that concatenates strings.
+	if op.Op == token.ADD {
+		if tp, ok := op.X.Type().(*types.Basic); ok && tp.Kind() == types.String {
+			vis.unifyLocals(op, op.X)
+			vis.unifyLocals(op, op.Y)
+		}
+	}
+}
+
+func (vis *visitor) visitTypeAssert(assert *ssa.TypeAssert) {
+	if !assert.CommaOk {
+		// t1 = typeassert t0.(*int)
+		vis.unifyLocals(assert, assert.X)
+	}
+	// The comma case will be processed by the subsequent extract instruction.
+}
+
+func (vis *visitor) visitExtract(extract *ssa.Extract) {
+	switch base := extract.Tuple.(type) {
+	case *ssa.TypeAssert:
+		// t1 = typeassert,ok t0.(*int)
+		// t2 = extract t1 0
+		if base.CommaOk && extract.Index == 0 {
+			vis.unifyLocals(extract, base.X)
+		}
+	case *ssa.Next:
+		// t1 = range t0
+		// t2 = next t1   // return (ok bool, k Key, v Value)
+		// t3 = extract t2 ?
+		if rng, ok := base.Iter.(*ssa.Range); ok {
+			if mayShareObject(extract) && extract.Index == 2 { // extract the value v
+				// The value from the map t0 flows into the field: t0[*] = v.
+				vis.processHeapAccess(extract, rng.X, anyIndexField)
+			}
+		}
+	case *ssa.Lookup:
+		// t2 = t0[t1],ok
+		// t3 = extract t2 ?
+		if base.CommaOk && extract.Index == 0 {
+			vis.processIndex(extract, base.X, base.Index)
+		}
+	default: // Other cases: model "r1 = extract r0 #n" as "r0["n"] = r1".
+		field := Field{Name: strconv.Itoa(extract.Index)}
+		vis.processHeapAccess(extract, base, field)
+	}
+}
+
+func (vis *visitor) visitSlice(slice *ssa.Slice) {
+	vis.unifyLocals(slice, slice.X)
+}
+
+func (vis *visitor) visitMakeInterface(makeInterface *ssa.MakeInterface) {
+	vis.unifyLocals(makeInterface, makeInterface.X)
+}
+
+func (vis *visitor) visitSend(send *ssa.Send) {
+	vis.processHeapAccess(send.X, send.Chan, anyIndexField)
+}
+
+func (vis *visitor) visitSelect(s *ssa.Select) {
+	// TODO: to be implemented.
+}
+
+func (vis *visitor) visitCall(call *ssa.CallCommon, instr ssa.Instruction) {
+	// TODO: to be added.
+}
+
+// Process a load/store using an index (which can be constant).
+func (vis *visitor) processIndex(data ssa.Value, base ssa.Value, index ssa.Value) {
+	// If the index is a constant, its string name is used as the field name;
+	// otherwise the predefined field name "AnyField" is used.
+	var field Field
+	if c, ok := index.(*ssa.Const); ok {
+		field = Field{Name: c.Value.String()}
+	} else {
+		field = anyIndexField
+	}
+	vis.processHeapAccess(data, base, field)
+}
+
+// Process a load/store from data_reg to (base, index), where base can be a register
+// or global variable. Here heap access is through unify-by-reference simulation.
+func (vis *visitor) processHeapAccess(data ssa.Value, base ssa.Value, fd Field) {
+	// Skip unification if lhs is not a sharable type.
+	if !typeMayShareObject(data.Type()) {
+		return
+	}
+	// unify instance field
+	for _, context := range vis.contexts {
+		vis.unifyField(context, base, fd, data)
+	}
+}
+
+// Process memory operator & and * by making the address pointing to the value.
+func (vis *visitor) processAddressToValue(addr ssa.Value, value ssa.Value) {
+	if !typeMayShareObject(addr.Type()) || !typeMayShareObject(value.Type()) {
+		return
+	}
+	state := vis.state
+	for _, context := range vis.contexts {
+		caddr := state.Insert(MakeReference(context, addr))
+		cvalue := state.Insert(MakeReference(context, value))
+		fmap := state.PartitionFieldMap(state.representative(caddr))
+		// Add or unify the field.
+		if v, ok := fmap[directPointToField]; ok {
+			if isUnifyByReference(value.Type()) { // unify-by-reference
+				state.Unify(v, cvalue)
+			} else {
+				vis.unifyByValue(v, cvalue)
+			}
+		} else {
+			fmap[directPointToField] = cvalue
+		}
+	}
+}
+
+// Unify local regs "v1" and "v2" in all contexts.
+func (vis *visitor) unifyLocals(v1 ssa.Value, v2 ssa.Value) {
+	if !mayShareObject(v1) || !mayShareObject(v2) {
+		return
+	}
+	state := vis.state
+	for _, context := range vis.contexts {
+		state.Unify(MakeReference(context, v1), MakeReference(context, v2))
+	}
+}
+
+// Unify "obj.field" and "target" in "context".
+func (vis *visitor) unifyField(context *Context, obj ssa.Value, fd Field, target ssa.Value) {
+	if !typeMayShareObject(target.Type()) {
+		return
+	}
+	// This generates the unification constraint obj.field = target
+	state := vis.state
+	objr := state.representative(MakeReference(context, obj))
+	fmap := state.PartitionFieldMap(objr)
+	if fmap == nil { // Should not happen
+		fmt.Printf("unexpected nil field map: %s; please report this issue\n", objr)
+		return
+	}
+	tr := state.Insert(MakeReference(context, target))
+	// Add mapping from field to target. If obj's partition already has a mapping for
+	// this field, unify target with the suitable partition,
+	if isUnifyByReference(tr.Type()) { // unify the two references
+		// Add or unify the field.
+		if v, ok := fmap[fd]; ok {
+			state.Unify(v, tr)
+		} else {
+			fmap[fd] = tr
+		}
+	} else { // unify by value
+		if v, ok := fmap[fd]; ok {
+			vis.unifyByValue(v, tr)
+		}
+	}
+}
+
+// Unify "&obj.field" and "target" in "context".
+// For example, for "t1 = &t0.x", after the unification, t0 has a field x pointing to t1.
+func (vis *visitor) unifyFieldAddress(context *Context, obj ssa.Value, field *Field, target *ssa.FieldAddr) {
+	// This generates the unification constraint &obj.field = target
+	state := vis.state
+	objv := vis.getPointee(MakeReference(context, obj))
+	fmap := state.PartitionFieldMap(state.representative(objv))
+	if fmap == nil { // Should not happen
+		fmt.Printf("unexpected nil field map: %s; please report this issue\n", objv)
+		return
+	}
+	tv := MakeReference(context, target)
+	// If obj's partition already has a mapping for this field, unify v with the
+	// suitable partition. Otherwise set v as the ref.
+	if v, ok := fmap[*field]; ok {
+		state.Unify(v, tv)
+	} else {
+		fmap[*field] = tv
+	}
+}
+
+// Return the reference holding the value *r of an address r (which can be
+// either a Local or a Global). Create the value reference if
+// it doesn't exist. In the heap, the address points to the value, i.e., r --> *r.
+func (vis *visitor) getPointee(addr Reference) Reference {
+	state := vis.state
+	arep := state.representative(addr)
+	// if ref is an address pointing to a value, return the value instead.
+	pval := state.valueReferenceOrNil(arep)
+	if pval != nil {
+		return pval
+	}
+	// The value doesn't exist; synthesize a reference for it.
+	val := MakeSynthetic(SyntheticValueOf, arep)
+	state.Insert(val)
+	state.PartitionFieldMap(arep)[directPointToField] = val
+	return val
+}
+
+// Unify a value with another value pointed by an address.
+// For example, unifying value "v2" and address "addr --> v1"
+// results in "addr -> {v1, v2}".
+func (vis *visitor) unifyFieldValueToAddress(toAddr Reference, fromVal Reference) {
+	state := vis.state
+	toFmap := state.PartitionFieldMap(toAddr)
+	if toFmap == nil { // Should not happen
+		fmt.Printf("unexpected nil field map: %s; please report this issue\n", toAddr)
+		return
+	}
+	if toVal, ok := toFmap[directPointToField]; ok {
+		state.Unify(toVal, fromVal)
+	} else {
+		toFmap[directPointToField] = fromVal
+	}
+}
+
+// Unify two field references w.r.t. the unify-by-value semantics, and return
+// the remaining references to be further unified-by-value.
+//
+// Distinguish addressable fields from non-addressable fields:
+// (1) for the non-addressable case such that r1 and r2, unify r1 and r2 if
+// they are references, otherwise return {r1, r2};
+// (2) for the addressable case such as &r1 --> *r1 and &r2 --> *r2,
+// keep &r1 and &r2 intact, but unify *r1 and *r2 if they are references,
+// otherwise return {*r1, *r2}.
+func (vis *visitor) unifyFields(ref1 Reference, ref2 Reference, addressable bool) (Reference, Reference) {
+	// A function to return a pair of references to be unified.
+	toBeUnified := func(r1 Reference, r2 Reference) (Reference, Reference) {
+		if typeMayShareObject(r1.Type()) && typeMayShareObject(r2.Type()) {
+			return r1, r2
+		}
+		return nil, nil
+	}
+
+	state := vis.state
+	if !addressable {
+		// TODO: check whether this is possible,
+		//  i.e. non-addressable fields (e.g. map elements) may have been unified before reaching here.
+		// unify directly for non-addressable fields.
+		if isUnifyByReference(ref1.Type()) { // unify-by-reference
+			state.Unify(ref1, ref2)
+			return nil, nil
+		} else { // unify-by-value
+			return toBeUnified(ref1, ref2)
+		}
+	}
+	rep1, rep2 := state.representative(ref1), state.representative(ref2)
+	// The addressable case: &r1 -> *r1 and &r2 -> *r2, unify *r1 and *r2.
+	if val2 := state.valueReferenceOrNil(rep2); val2 != nil {
+		if isUnifyByReference(val2.Type()) {
+			vis.unifyFieldValueToAddress(rep1, val2)
+		} else { // unify-by-value
+			return toBeUnified(val2, rep1)
+		}
+	} else if val1 := state.valueReferenceOrNil(rep1); val1 != nil {
+		if isUnifyByReference(val1.Type()) {
+			vis.unifyFieldValueToAddress(rep2, val1)
+		} else { // unify-by-value
+			return toBeUnified(val1, rep2)
+		}
+	}
+	return nil, nil // no further unify-by-value
+}
+
+// For non-reference types, unify-by-value semantics is used such that reference
+// r1 and r2 are not unified, but their sub-fields of reference types are
+// unified recursively.
+//
+// Example:
+//   type S struct {x *int, y int, z S};
+//   var v2 S = ...;
+//   v1 := v2;
+// After the unification, the partitions are:
+// { v1.x, v2.x }, {v1.z.x, v2.z.x }, ...
+func (vis *visitor) unifyByValue(ref1 Reference, ref2 Reference) {
+	// A field may be addressable or non-addressable:
+	// (1) for the non-addressable case such that r1 -> r1.x and r2 -> r2.x, unify
+	// r1.x and r2.x;
+	// (2) for the addressable case such as r1 -> &r1.x -> *r1.x and r2 -> &r2.x
+	// -> *r2.x, unify *r1.x and *r2.x, and keep &r1.x and &r2.x intact.
+	state := vis.state
+	rep1, rep2 := state.representative(ref1), state.representative(ref2)
+	fmap1, fmap2 := state.PartitionFieldMap(rep1), state.PartitionFieldMap(rep2)
+	if fmap1 == nil || fmap2 == nil { // Should not happen
+		fmt.Printf("unexpected nil field map: %s or %s; please report this issue\n", rep1, rep2)
+		return
+	}
+	if &fmap1 == &fmap2 { // already unified
+		return
+	}
+	// The to-be-unified field pairs.
+	toUnified := make(map[Reference]Reference)
+	// "Copy" the fields from ref2 to ref1: copy only the field values rather than
+	// the field addresses.
+	for k, addr2 := range fmap2 {
+		var addr1 Reference
+		if fd, ok := fmap1[k]; ok {
+			addr1 = fd
+		} else {
+			addr1 = state.Insert(MakeSynthetic(SyntheticField, rep1))
+			fmap1[k] = addr1
+		}
+		toUnified[addr1] = addr2
+		// TODO: Recursively call "UnifyByValue" here.
+	}
+	// "Copy" the remaining fields in ref1 to ref2. Only copy unify-by-reference
+	// field values.
+	for k, addr1 := range fmap1 {
+		if _, ok := fmap2[k]; ok {
+			continue
+		}
+		addr2 := state.Insert(MakeSynthetic(SyntheticField, rep2))
+		fmap2[k] = addr2
+		toUnified[addr1] = addr2
+	}
+	// Perform further unifications.
+	addressable := isFieldAddressable(rep2.Type())
+	for addr1, addr2 := range toUnified {
+		vis.unifyFields(addr1, addr2, addressable)
+	}
+}
+
+// Return whether a type can use the unify-by-reference semantics. If not then
+// it is assumed to be unifyByValue.
+func isUnifyByReference(tp types.Type) bool {
+	switch t := tp.(type) {
+	case *types.Struct, *types.Array:
+		return false
+	case *types.Named:
+		return isUnifyByReference(t.Underlying())
+	}
+	// "MayShareObject" determines whether the value may share an object
+	// pointed by other values. It includes structs and arrays, whose elements may be shared.
+	return typeMayShareObject(tp)
+}
+
+// Return whether the fields of a type can be accessed through operator &
+// (https://golang.org/ref/spec#Address_operators).
+// The Go frontend and SSA handle an addressable field by introducing an
+// intermediate register for the address. For example, for struct A, "A.x = 1"
+// is compiled into "t1 = &A.x; *t1 = 1".
+func isFieldAddressable(tp types.Type) bool {
+	switch t := tp.(type) {
+	case *types.Struct, *types.Slice, *types.Array:
+		return true
+	case *types.Named:
+		return isFieldAddressable(t.Underlying())
+	}
+	return false
+}
+
+// Return whether a value is a local variable  such as a paramter or a register instruction.
+func isLocal(v ssa.Value) bool {
+	switch v.(type) {
+	case *ssa.Parameter, *ssa.FreeVar, ssa.Instruction:
+		return true
+	}
+	return false
+}
+
+func isGlobal(v ssa.Value) bool {
+	_, ok := v.(*ssa.Global)
+	return ok
+}
+
+// Return whether the value is a local variable or a global variable,
+// and its type allows object sharing.
+func mayShareObject(v ssa.Value) bool {
+	return typeMayShareObject(v.Type()) && (isLocal(v) || isGlobal(v))
+}
+
+// Construct a field from a type and a field index.
+// For example, for struct T {x int, y int), makeField(*T, 1) returns Field{Name:"y", IrField:y}.
+func makeField(tp types.Type, index int) *Field {
+	if pt, ok := tp.(*types.Pointer); ok {
+		tp = pt.Elem()
+	}
+	if named, ok := tp.(*types.Named); ok {
+		tp = named.Underlying()
+	}
+	if stp, ok := tp.(*types.Struct); ok {
+		fvar := stp.Field(index)
+		return &Field{Name: fvar.Name(), irField: fvar}
+	}
+	return &Field{Name: fmt.Sprintf("%d", index)}
+}


Test patch:
diff --git a/internal/pkg/earpointer/analysis_test.go b/internal/pkg/earpointer/analysis_test.go
new file mode 100644
index 0000000..39292c5
--- /dev/null
+++ b/internal/pkg/earpointer/analysis_test.go
@@ -0,0 +1,653 @@
+// Copyright 2021 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package earpointer_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/google/go-flow-levee/internal/pkg/earpointer"
+	"golang.org/x/tools/go/analysis"
+	"golang.org/x/tools/go/analysis/passes/buildssa"
+	"golang.org/x/tools/go/ssa"
+)
+
+// Compiles the code and then runs the EAR pointer analysis.
+func runCode(code string) (*earpointer.Partitions, error) {
+	pkg, err := buildSSA(code)
+	if err != nil {
+		return nil, fmt.Errorf("compilation failed: %s :\n %s", err, code)
+	}
+	// Synthesize an SSA input and an analysis pass.
+	var srcFuncs []*ssa.Function
+	for _, m := range pkg.Members {
+		if f, ok := m.(*ssa.Function); ok {
+			srcFuncs = append(srcFuncs, f)
+		}
+	}
+	ssainput := buildssa.SSA{Pkg: pkg, SrcFuncs: srcFuncs}
+	pass := analysis.Pass{ResultOf: map[*analysis.Analyzer]interface{}{buildssa.Analyzer: &ssainput}}
+	// Run the analysis.
+	partitions, err := earpointer.Analyzer.Run(&pass)
+	if err != nil {
+		return nil, fmt.Errorf("analyzer run failed: %v", ssainput)
+	}
+	return partitions.(*earpointer.Partitions), nil
+}
+
+func TestFieldAddr(t *testing.T) {
+	code := `package p
+	type T struct { x *int; y *int }
+	func f(a *T, b *int) {
+		a.x = b
+	}
+	`
+	/*
+		func f(a *T, b *int):
+		0:                               entry P:0 S:0
+		t0 = &a.x [#0]                   **int
+		*t0 = b
+		return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{*f.a}: [x->f.t0], {f.a}: --> *f.a, {f.b}: [], {f.t0}: --> f.b"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestFieldAddr2(t *testing.T) {
+	code := `package p
+	type T struct { x *int; y *int }
+	func f(a *T, b, c *int) {
+		a.x = b
+		a.x = c
+	}
+	`
+	/*
+		func f(a *T, b *int, c *int):
+		0:                                                entry P:0 S:0
+			t0 = &a.x [#0]                                **int
+			*t0 = b
+			t1 = &a.x [#0]                                **int
+			*t1 = c
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{*f.a}: [x->f.t1], {f.a}: --> *f.a, {f.b,f.c}: [], {f.t0,f.t1}: --> f.c"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestField(t *testing.T) {
+	code := `package p
+	type T struct { x *int }
+	func f(a *int) {
+		_ = T{x: a}.x
+	}
+	`
+	/*
+		func f(a *int):
+		0:                                  entry P:0 S:0
+			t0 = local T (complit)          *T
+			t1 = &t0.x [#0]                 **int
+			*t1 = a
+			t2 = *t0                        T
+			t3 = t2.x [#0]                  *int
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// t2's field x points to t3
+	want := "{*f.t0}: [x->f.t1], {f.a}: [], {f.t0}: --> *f.t0, {f.t1}: --> f.a, {f.t2[.],f.t3}: --> f.a, {f.t2}: [x->f.t3]"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestEmbeddedField(t *testing.T) {
+	code := `package p
+	type T1 struct { }
+	type T2 struct { t T1 }
+	func f(i *int) {
+		_ = T2{t: T1{}}.t
+	}
+	`
+	/*
+		func f(i *int):
+		0:                                  entry P:0 S:0
+			t0 = local T2 (complit)         *T2
+			t1 = &t0.t [#0]                 *T1
+			t2 = *t0                        T2
+			t3 = t2.t [#0]                  T1
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// t3 is not unified with t2.t since they are structs.
+	// f.t2 has a field t pointing to a synthetic reference t2[.].
+	want := "{*f.t0}: [t->f.t1], {f.i}: [], {f.t0}: --> *f.t0, {f.t1}: [], {f.t2[.]}: [], {f.t2}: [t->f.t2[.]], {f.t3}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestStructCopy(t *testing.T) { // mainly for coverage test
+	code := `package p
+	type T1 struct { }
+	type T2 struct { x *T1; y *int }
+	func f(v1, v2 T2, i *T1, j *int) {
+		v1.x = i
+		v1.y = j
+		v2.x = i
+		v2 = v1
+	}
+	`
+	/*
+		func f(v1 T2, v2 T2, i *T1, j *int):
+		0:                                   entry P:0 S:0
+			t0 = local T2 (v1)               *T2
+			*t0 = v1
+			t1 = local T2 (v2)               *T2
+			*t1 = v2
+			t2 = &t0.x [#0]                  **T1
+			*t2 = i
+			t3 = &t0.y [#1]                  **int
+			*t3 = j
+			t4 = &t1.x [#0]                  **T1
+			*t4 = i
+			t5 = *t0                         T2
+			*t1 = t5
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// TODO: there is a non-determinism (f.t3 --> f.i or f.j) that depends on the order of the unification.
+	want1 := "{f.i,f.j}: [], {f.t0}: --> f.v1, {f.t1}: --> f.v2, {f.t2}: --> f.i, {f.t3}: --> f.i, {f.t4}: --> f.i, {f.t5[.]}: --> f.i, " +
+		"{f.t5}: [x->f.t5[.], y->f.t5[.]], {f.v1}: [x->f.t2, y->f.t3], {f.v2[.]}: --> f.i, {f.v2}: [x->f.t4, y->f.v2[.]]"
+	want2 := "{f.i,f.j}: [], {f.t0}: --> f.v1, {f.t1}: --> f.v2, {f.t2}: --> f.j, {f.t3}: --> f.j, {f.t4}: --> f.j, {f.t5[.]}: --> f.j, " +
+		"{f.t5}: [x->f.t5[.], y->f.t5[.]], {f.v1}: [x->f.t2, y->f.t3], {f.v2[.]}: --> f.j, {f.v2}: [x->f.t4, y->f.v2[.]]"
+	if got := state.String(); got != want1 && got != want2 {
+		t.Errorf("got: %s\n want: %s or %s", got, want1, want2)
+	}
+}
+
+func TestEmbeddedFieldClone(t *testing.T) {
+	code := `package p
+  	type T1 struct { x *int}
+	type T2 struct { x T1 }
+	func f(i T1, v1, v2 T2) {
+		v2.x = i
+		v1 = v2
+	}
+	`
+	/*
+		func f(i T1, v1 T2, v2 T2):
+		0:                                                   entry P:0 S:0
+			t0 = local T1 (i)                                *T1
+			*t0 = i
+			t1 = local T2 (v1)                               *T2
+			*t1 = v1
+			t2 = local T2 (v2)                               *T2
+			*t2 = v2
+			t3 = &t2.x [#0]                                  *T1
+			t4 = *t0                                         T1
+			*t3 = t4
+			t5 = *t2                                         T2
+			*t1 = t5
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.i}: [], {f.t0}: --> f.i, {f.t1}: --> f.v1, {f.t2}: --> f.v2, {f.t3}: --> f.t4, {f.t4}: [], " +
+		"{f.t5[.]}: [], {f.t5}: [x->f.t5[.]], {f.v1[.]}: [], {f.v1}: [x->f.v1[.]], {f.v2}: [x->f.t3]"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestIndexAddr(t *testing.T) {
+	code := `package p
+	func f(a, b []*int, i int) {
+		a[1] = b[i]
+	}
+	`
+	/*
+		func f(a []*int, b []*int, i int):
+		0:                       entry P:0 S:0
+			t0 = &a[1:int]       **int
+			t1 = &b[i]           **int
+			t2 = *t1             *int
+			*t0 = t2
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a}: [1->f.t0], {f.b}: [AnyField->f.t1], {f.t0}: --> f.t2, {f.t1}: --> f.t2, {f.t2}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestIndex(t *testing.T) {
+	code := `package p
+	func f(a *int) {
+		_ = [10]*int{a}[0]
+	}
+	`
+	/*
+		func f(a *int):
+		0:                                    entry P:0 S:0
+			t0 = local [10]*int (complit)     *[10]*int
+			t1 = &t0[0:int]                   **int
+			*t1 = a
+			t2 = *t0                          [10]*int
+			t3 = t2[0:int]                    *int
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// t2's field 0 points to t3
+	want := "{f.a}: [], {f.t0}: --> f.t2, {f.t1}: --> f.a, {f.t2}: [0->f.t3], {f.t3}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestPhi(t *testing.T) {
+	code := `package p
+	func f(a, b *int, i int) {
+		c := a
+		if i > 0 {
+		    c = b
+	    }
+		print(c)
+
+		d := 10  // non-pointer type
+		if i > 0 {
+		    d = i
+	    }
+		print(d)
+	}
+	`
+	/*
+		func f(a *int, b *int, i int):
+		0:                                   entry P:0 S:2
+			t0 = i > 0:int                   bool
+			if t0 goto 1 else 2
+		1:                                   if.then P:1 S:1
+			jump 2
+		2:                                   if.done P:2 S:0
+			t1 = phi [0: a, 1: b] #c         *int
+			t2 = print(t1)                   ()
+		...
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a,f.b,f.t1}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestStore(t *testing.T) {
+	code := `package p
+	type A struct { x *int; y *int }
+	var z *int
+	func f(a *A, b []*int) {
+		a.x = z
+		a.y = b[10]
+	}
+	`
+	/*
+		func f(a *A, b []*int):
+		0:                            entry P:0 S:0
+			t0 = &a.x [#0]            **int
+			t1 = *z                   *int
+			*t0 = t1
+			t2 = &a.y [#1]            **int
+			t3 = &b[10:int]           **int
+			t4 = *t3                  *int
+			*t2 = t4
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want :=
+		`{*f.a}: [x->f.t0, y->f.t2], {f.a}: --> *f.a, {f.b}: [10->f.t3], {f.t0}: --> f.t1, {f.t1}: [], {f.t2}: --> f.t4, {f.t3}: --> f.t4, {f.t4}: [], {t.z}: --> f.t1`
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestDereference(t *testing.T) {
+	code := `package p
+	var x *int
+	func f(y, z **int) {
+		x = *y
+		*z = x
+	}
+	`
+	/*
+		func f(y **int, z **int):
+		0:                                  entry P:0 S:0
+			t0 = *y                         *int
+			*x = t0
+			t1 = *z                         *int
+			*x = t1
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := `{f.t0,f.t1}: [], {f.y}: --> f.t1, {f.z}: --> f.t1, {t.x}: --> f.t1`
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestMapAccess(t *testing.T) {
+	code := `package p
+	type T struct { }
+	var t *T
+	func f(m map[int]*T, i int) {
+		m[0] = t
+		m[i] = m[1]
+		_ = m[i]
+	}
+	`
+	/*
+		func f(m map[int]*T, i int):
+		0:                        entry P:0 S:0
+			t0 = *t               *T
+			m[0:int] = t0
+			t1 = m[1:int]         *T
+			m[i] = t1
+			t2 = m[i]             *T
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.m}: [0->f.t0, 1->f.t2, AnyField->f.t2], {f.t0}: [], {f.t1,f.t2}: [], {t.t}: --> f.t0"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestLookUp(t *testing.T) {
+	code := `package p
+	func f(a map[int]**int) {
+		v, ok := a[10]
+		_ = *v
+		_ = ok
+	}
+	`
+	/*
+		func f(a map[int]**int):
+		0:                                      entry P:0 S:0
+			t0 = a[10:int],ok                   (**int, bool)
+			t1 = extract t0 #0                  **int
+			t2 = extract t0 #1                  bool
+			t3 = *t1                            *int
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a}: [10->f.t1], {f.t1}: --> f.t3, {f.t3}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestConvert(t *testing.T) {
+	code := `package p
+	func f(a []byte) {
+		_ = (string)(a)
+	}
+	`
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a,f.t0}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestTypeAssert(t *testing.T) {
+	code := `package p
+	func f(a interface{}) {
+	b,_ := a.(*bool)
+		_ = b
+		_ = a.(*int)
+	}
+	`
+	/*
+		func f(a interface{}):
+		0:                                    entry P:0 S:0
+			t0 = typeassert,ok a.(*bool)      (value *bool, ok bool)
+			t1 = extract t0 #0                *bool
+			t2 = extract t0 #1                bool
+			t3 = typeassert a.(*int)          *int
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a,f.t1,f.t3}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestChangeInterfaceOrType(t *testing.T) {
+	code := `package p
+	type I interface{ f() }
+	type T1 struct {}
+	type T2 struct {}
+	func f(a I) interface{} {
+		var t1 T1
+		_ = (T2)(t1)
+		return a
+	}
+	`
+	/*
+		func f(a I) interface{}:
+		0:                                            entry P:0 S:0
+			t0 = local T1 (t1)                        *T1
+			t1 = *t0                                  T1
+			t2 = changetype T2 <- T1 (t1)             T2
+			t3 = changetype interface{} <- I (a)      interface{}
+			return t3
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a,f.t3}: [], {f.t0}: --> f.t1, {f.t1,f.t2}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestBinOp(t *testing.T) {
+	code := `package p
+	func f(a, b string) {
+	_ = a + b
+	}
+	`
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a,f.b,f.t0}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestRange(t *testing.T) {
+	code := `package p
+	func f(a map[string]*int) {
+	for i, v := range a {
+		_ = i
+		_ = v
+	}
+	}
+	`
+	/*
+		func f(a map[string]*int):
+		0:                                   entry P:0 S:1
+			t0 = range a                     iter
+			jump 1
+		1:                                   rangeiter.loop P:2 S:2
+			t1 = next t0                     (ok bool, k string, v *int)
+			t2 = extract t1 #0               bool
+			if t2 goto 2 else 3
+		2:                                   rangeiter.body P:1 S:1
+			t3 = extract t1 #1               string
+			t4 = extract t1 #2               *int
+			jump 1
+		3:                                   rangeiter.done P:1 S:0
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.a}: [AnyField->f.t4], {f.t3}: [], {f.t4}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestChannel(t *testing.T) {
+	code := `package p
+	func f(ch chan string, z string) {
+	ch <- z   // Send v to channel ch.
+	_ = <-ch  // Receive from ch.
+	}
+	`
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.ch}: [AnyField->f.t0], {f.t0,f.z}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestSlice(t *testing.T) {
+	code := `package p
+	func f(s [6]int) {
+		t1 := s[1:4]
+		_ = t1[2:]
+	}
+	`
+	/*
+		func f(s [6]int):
+		0:                                 entry P:0 S:0
+			t0 = new [6]int (s)            *[6]int
+			*t0 = s
+			t1 = slice t0[1:int:4:int]     []int
+			t2 = slice t1[2:int:]          []int
+			return
+	*/
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.s}: [], {f.t0,f.t1,f.t2}: --> f.s"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestMakeInterface(t *testing.T) {
+	code := `package p
+	func f(s *int) interface{} {
+		return s
+	}
+	`
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.s,f.t0}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}
+
+func TestUnimplemented(t *testing.T) {
+	code := `package p
+	func f() {
+		defer func() {
+			print("defer")
+		}()
+		go func() {
+			print("go")
+		}()
+
+		c1 := make(chan string)
+		c2 := make(chan string)
+		select {
+	        case <-c1: { print("c1") }
+	        case <-c2: { print("c2") }
+		}
+
+		panic("test")
+	}
+	`
+	state, err := runCode(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := "{f.t0}: [], {f.t1}: [], {f.t5}: [], {f.t9}: []"
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s", got, want)
+	}
+}