Repository: google/go-flow-levee
Pull request #313 (2021-06-12 03:35:30)

Various minor improvements of the EAR pointer analysis.
(1) Use unify-by-reference more regressively.
(2) Handle the map operations better.
(3) Support some known functions.

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



Patch:
diff --git a/internal/pkg/earpointer/analysis.go b/internal/pkg/earpointer/analysis.go
index d193f30..d6fc7ea 100644
--- a/internal/pkg/earpointer/analysis.go
+++ b/internal/pkg/earpointer/analysis.go
@@ -64,22 +64,25 @@ type visitor struct {
 
 func run(pass *analysis.Pass) (interface{}, error) {
 	ssainput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
-	p := analyze(ssainput.Pkg)
+	p := Analyze(ssainput)
 	return p, nil
 }
 
 // Analyzes an SSA program and build the partition information.
-func analyze(pkg *ssa.Package) *Partitions {
-	prog := pkg.Prog
+func Analyze(ssainput *buildssa.SSA) *Partitions {
+	prog := ssainput.Pkg.Prog
 	// Use the call graph to initialize the contexts.
 	// TODO: the call graph can be CHA, RTA, VTA, etc.
 	cg := static.CallGraph(prog)
 	vis := visitor{state: NewState(), callees: mapCallees(cg)}
 	vis.initContexts(cg)
-	vis.initGlobalReferences(pkg)
+	vis.initGlobalReferences(ssainput.Pkg)
 	// Analyze all the functions and methods in the package,
-	// not just those in ssainput.ScrFuncs.
+	// not just those in ssainput.SrcFuncs.
 	fns := ssautil.AllFunctions(prog)
+	for _, fn := range ssainput.SrcFuncs {
+		fns[fn] = true
+	}
 	for fn := range fns {
 		vis.initFunction(fn)
 	}
@@ -227,6 +230,8 @@ func (vis *visitor) visitInstruction(instr ssa.Instruction) {
 		vis.visitSlice(i)
 	case *ssa.MakeInterface:
 		vis.visitMakeInterface(i)
+	case *ssa.MakeClosure:
+		vis.visitMakeClosure(i)
 	case *ssa.Select:
 		vis.visitSelect(i)
 
@@ -235,7 +240,6 @@ func (vis *visitor) visitInstruction(instr ssa.Instruction) {
 
 	case *ssa.Alloc,
 		*ssa.MakeChan,
-		*ssa.MakeClosure,
 		*ssa.MakeMap,
 		*ssa.MakeSlice:
 		// Local variables are created in the beginning of the pass by initReferences().
@@ -271,15 +275,40 @@ func (vis *visitor) visitFieldAddr(addr *ssa.FieldAddr) {
 }
 
 func (vis *visitor) visitField(field *ssa.Field) {
-	// "t1 = t0.x" is implemented by t0[x -> t1].
+	// "t1 = t0.x" is implemented by t0[x -> addr], addr --> t1,
+	// where addr is the reference to the field address.
 	obj := field.X
 	fd := makeField(obj.Type(), field.Field)
-	vis.processHeapAccess(field, obj, *fd)
+	state := vis.state
+	for _, c := range vis.getContexts(field) {
+		objRef := MakeReference(c, obj)
+		fmap := state.PartitionFieldMap(state.representative(objRef))
+		fref := MakeReference(c, field)
+		// If obj's partition already has a mapping for this field, unify fref
+		// with the suitable partition. Otherwise set fref as the ref.
+		if oldRef, ok := fmap[*fd]; ok {
+			// Implement "fmap[fd -> addr], addr --> fref".
+			state.Unify(vis.getPointee(oldRef), fref)
+		} else {
+			fmap[*fd] = fref // over-approximation
+		}
+	}
 }
 
 func (vis *visitor) visitIndexAddr(addr *ssa.IndexAddr) {
 	// "t2 = &t1[t0]" is handled through address unification.
-	vis.processIndex(addr, addr.X, addr.Index)
+	obj := addr.X
+	if c, ok := addr.Index.(*ssa.Const); ok {
+		field := Field{Name: c.Value.String()}
+		for _, cxt := range vis.getContexts(addr) {
+			vis.unifyFieldAddress(cxt, obj, &field, addr)
+		}
+	}
+	// Also update the AnyField information.
+	// Note that base[c -> data] implies base[AnyField -> data]
+	for _, c := range vis.getContexts(addr) {
+		vis.unifyFieldAddress(c, obj, &anyIndexField, addr)
+	}
 }
 
 func (vis *visitor) visitIndex(index *ssa.Index) {
@@ -347,10 +376,22 @@ func (vis *visitor) visitUnOp(op *ssa.UnOp) {
 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)
+	if op.Op != token.ADD {
+		return
+	}
+	// for r0 = r1 + r2, unifying r0, r1 and r2 may cause too many
+	// over-approximations. Here fields are introduced to make:
+	//     {r0}[0->r1, 1->r2]
+	// which avoids unifying r1 and r2.
+	if tp, ok := op.X.Type().(*types.Basic); ok && tp.Kind() == types.String {
+		// unify instance field
+		for _, c := range vis.getContexts(op) {
+			if mayShareObject(op.X) {
+				vis.unifyField(c, op, Field{Name: "left"}, op.X)
+			}
+			if mayShareObject(op.Y) {
+				vis.unifyField(c, op, Field{Name: "right"}, op.Y)
+			}
 		}
 	}
 }
@@ -387,6 +428,31 @@ func (vis *visitor) visitExtract(extract *ssa.Extract) {
 		if base.CommaOk && extract.Index == 0 {
 			vis.processIndex(extract, base.X, base.Index)
 		}
+	case *ssa.UnOp:
+		// Handle the channel read case with comma.
+		// Other UnOp cases are handled within "visitUnOp()".
+		// t1 = <-t0,ok
+		// t2 = extract t1 0
+		if base.Op == token.ARROW && base.CommaOk && extract.Index == 0 { // channel read
+			// Use array read to simulate channel read.
+			vis.processHeapAccess(extract, base.X, anyIndexField)
+		}
+	case *ssa.Select:
+		// t1 = select blocking [c1<-t0, <-c2]  // (index int, recvOk bool, r_0 T_0, ... r_n-1 T_n-1)
+		// t2 = extract t1 #n
+		if extract.Index <= 1 {
+			break
+		}
+		k := -1 // for locating the (extract.Index-2)^{th} receive
+		for _, st := range base.States {
+			if st.Dir == types.RecvOnly {
+				if k++; k == extract.Index-2 && mayShareObject(st.Chan) {
+					// Extract the receive value from the channel.
+					vis.processHeapAccess(extract, st.Chan, anyIndexField)
+					break
+				}
+			}
+		}
 	default: // Other cases: model "r1 = extract r0 #n" as "r0["n"] = r1".
 		field := Field{Name: strconv.Itoa(extract.Index)}
 		vis.processHeapAccess(extract, base, field)
@@ -401,12 +467,28 @@ func (vis *visitor) visitMakeInterface(makeInterface *ssa.MakeInterface) {
 	vis.unifyLocals(makeInterface, makeInterface.X)
 }
 
+func (vis *visitor) visitMakeClosure(closure *ssa.MakeClosure) {
+	if fn, ok := closure.Fn.(*ssa.Function); ok {
+		// For a closure, add for free variable bindings.
+		for i, bind := range closure.Bindings {
+			if mayShareObject(bind) {
+				fv := fn.FreeVars[i]
+				vis.unifyLocals(fv, bind)
+			}
+		}
+	}
+}
+
 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.
+	for _, st := range s.States {
+		if st.Send != nil {
+			vis.processHeapAccess(st.Send, st.Chan, anyIndexField)
+		}
+	}
 }
 
 func (vis *visitor) visitCall(call *ssa.CallCommon, callsite ssa.Instruction) {
@@ -415,12 +497,16 @@ func (vis *visitor) visitCall(call *ssa.CallCommon, callsite ssa.Instruction) {
 		vis.visitBuiltin(builtin, callsite)
 		return
 	}
-
 	// Collect unification constraints using the call graph.
 	for _, fn := range vis.callees[call] {
 		if fn == nil {
 			continue
 		}
+		if vis.visitKnownFunction(fn, callsite) {
+			// special handling of some known functions
+			continue
+		}
+
 		paramCstrs, retCstrs := vis.collectCalleeConstraints(call, fn, callsite)
 		// Unify caller arguments and callee parameters in matching contexts.
 		for arg, params := range paramCstrs {
@@ -511,7 +597,7 @@ func (vis *visitor) visitBuiltin(builtin *ssa.Builtin, instr ssa.Instruction) {
 		// Propagage the arguments to the return value.
 		if dst, ok := instr.(ssa.Value); ok {
 			ops := instr.Operands(nil)
-			// ops[0] is the "append" function itself.
+			// ops[0] is the function itself.
 			for i := 1; i < len(ops); i++ {
 				// Unify-by-reference the dst and the op for all contexts.
 				vis.unifyLocals(dst, *ops[i])
@@ -521,9 +607,9 @@ func (vis *visitor) visitBuiltin(builtin *ssa.Builtin, instr ssa.Instruction) {
 		{
 			// Propagage the source to the destination through unify-by-value.
 			ops := instr.Operands(nil)
-			// ops[0] is the "copy" function itself.
+			// ops[0] is the function itself.
 			dst, src := *ops[1], *ops[2]
-			if mayShareObject(src) {
+			if mayShareObject(dst) && mayShareObject(src) {
 				for _, c := range vis.getContexts(dst) {
 					vis.unifyByValue(MakeLocal(c, dst), MakeLocal(c, src))
 				}
@@ -532,6 +618,44 @@ func (vis *visitor) visitBuiltin(builtin *ssa.Builtin, instr ssa.Instruction) {
 	}
 }
 
+// Handle some known functions, e.g. in package "fmt".
+func (vis *visitor) visitKnownFunction(fn *ssa.Function, instr ssa.Instruction) bool {
+	// TODO(#312): Handle standard library functions.
+	// Add an operand reference to a field of the "dst", i.e. dst[index -> op].
+	addField := func(dst ssa.Value, op ssa.Value, index int) {
+		fd := Field{Name: strconv.Itoa(index)}
+		if mayShareObject(op) {
+			for _, c := range vis.getContexts(dst) {
+				vis.unifyField(c, dst, fd, op)
+			}
+		}
+	}
+	fname := fn.Name()
+	switch {
+	case strings.HasPrefix(fname, "Sprint"), strings.HasPrefix(fname, "Errorf"):
+		// Propagate the arguments to the return value using fields.
+		if dst, ok := instr.(ssa.Value); ok {
+			ops := instr.Operands(nil)
+			// ops[0] is the function itself.
+			for i := 1; i < len(ops); i++ {
+				addField(dst, *ops[i], i)
+			}
+		}
+		return true
+	case strings.HasPrefix(fname, "Fprint"):
+		// Propagate the arguments to the first argument using fields.
+		ops := instr.Operands(nil)
+		// ops[0] is the function itself.
+		first := *ops[1] // the io stream
+		for i := 2; i < len(ops); i++ {
+			addField(first, *ops[i], i)
+		}
+		return true
+	default:
+		return false
+	}
+}
+
 // Collect unification constraints corresponding to a call.
 // This generates constraints for unifying parameters, free variables, and return values.
 func (vis *visitor) collectCalleeConstraints(common *ssa.CallCommon, fn *ssa.Function, instr ssa.Instruction) (map[ssa.Value][]ssa.Value, map[ssa.Value][][]ssa.Value) {
@@ -592,10 +716,12 @@ func (vis *visitor) processIndex(data ssa.Value, base ssa.Value, index ssa.Value
 	var field Field
 	if c, ok := index.(*ssa.Const); ok {
 		field = Field{Name: c.Value.String()}
+		vis.processHeapAccess(data, base, field)
+		// base[c -> data] implies base[AnyField -> data]
+		vis.processHeapAccess(data, base, anyIndexField)
 	} else {
-		field = anyIndexField
+		vis.processHeapAccess(data, base, anyIndexField)
 	}
-	vis.processHeapAccess(data, base, field)
 }
 
 // Process a load/store from data_reg to (base, index), where base can be a register
@@ -626,7 +752,8 @@ func (vis *visitor) processAddressToValue(addr ssa.Value, value ssa.Value) {
 			if isUnifyByReference(value.Type()) { // unify-by-reference
 				state.Unify(v, cvalue)
 			} else {
-				vis.unifyByValue(v, cvalue)
+				// TODO(#314): handle the unify-by-value semantics
+				state.Unify(v, cvalue)
 			}
 		} else {
 			fmap[directPointToField] = cvalue
@@ -661,23 +788,19 @@ func (vis *visitor) unifyField(context *Context, obj ssa.Value, fd Field, target
 	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)
-		}
+	// TODO(#314): handle the unify-by-value semantics.
+	// unify the two references
+	// Add or unify the field.
+	if v, ok := fmap[fd]; ok {
+		state.Unify(v, tr)
+	} else {
+		fmap[fd] = 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) {
+func (vis *visitor) unifyFieldAddress(context *Context, obj ssa.Value, field *Field, target ssa.Value) {
 	// This generates the unification constraint &obj.field = target
 	state := vis.state
 	objv := vis.getPointee(MakeReference(context, obj))
@@ -818,7 +941,7 @@ func (vis *visitor) unifyByValue(ref1 Reference, ref2 Reference) {
 			fmap1[k] = addr1
 		}
 		toUnified[addr1] = addr2
-		// TODO: Recursively call "UnifyByValue" here.
+		// TODO(#314): Recursively call "UnifyByValue" here.
 	}
 	// "Copy" the remaining fields in ref1 to ref2. Only copy unify-by-reference
 	// field values.
@@ -940,5 +1063,5 @@ func makeField(tp types.Type, index int) *Field {
 		fvar := stp.Field(index)
 		return &Field{Name: fvar.Name(), irField: fvar}
 	}
-	return &Field{Name: fmt.Sprintf("%d", index)}
+	return &Field{Name: strconv.Itoa(index)}
 }
diff --git a/internal/pkg/earpointer/state.go b/internal/pkg/earpointer/state.go
index 2292add..bbf05f0 100644
--- a/internal/pkg/earpointer/state.go
+++ b/internal/pkg/earpointer/state.go
@@ -85,8 +85,10 @@ func (state *state) representatives() ReferenceSet {
 // ("ref" must belong to this state).
 func (state *state) representative(ref Reference) Reference {
 	failureCallback := func(ref Reference) Reference {
-		log.Fatalf("representative: Reference [%s] not found in state", ref)
-		return nil
+		// Some global variables has no declarations in the SSA;
+		// Insert their references dynamically.
+		state.Insert(ref)
+		return ref
 	}
 	return state.lookupPartitionRep(ref, failureCallback)
 }
@@ -169,7 +171,10 @@ func (state *state) unifyReps(ref1 Reference, ref2 Reference) {
 	pinfo1 := state.partitionInfo(prep1)
 	pinfo2 := state.partitionInfo(prep2)
 	// swap so that "ref1" is always the smaller partition
-	if pinfo1.numMembers > pinfo2.numMembers {
+	// if their sizes are the same, use source position information to
+	// make the choice deterministic.
+	n1, n2 := pinfo1.numMembers, pinfo2.numMembers
+	if n1 > n2 || (n1 == n2 && prep1.Value().Pos() > prep2.Value().Pos()) {
 		prep1, prep2 = prep2, prep1
 		pinfo1, pinfo2 = pinfo2, pinfo1
 	}
@@ -308,10 +313,27 @@ func (state *state) ToPartitions() *Partitions {
 // After this call, internal data structures are optimized for lookups only,
 // and no mutations should be made.
 func (p *Partitions) finalize() {
-	// Construct the map from field references to their parents.
-	p.constructFieldParentMap()
-
-	// Construct the members. members maps partitions representatives to the
+	// (1) Construct a new parent map that maps a reference to its representative
+	//     so as to accelerate representative lookup.
+	// For example, supposed the old parent map contains r1->r2, r2->r3,
+	// r3->r4(representative), then the new parent map contains r1->r4.
+	// "r4" can be returned immediately without chasing the union-find relation
+	// in the old map.
+	optParents := make(parentMap) // optimized parents
+	for ref, parent := range p.parents {
+		if ref == parent {
+			optParents[ref] = ref
+		} else {
+			rep := parent
+			for up := p.parents[rep]; up != rep; {
+				rep = up
+			}
+			// Otherwise, get ref's partition representative and update members.
+			optParents[ref] = rep
+		}
+	}
+	p.parents = optParents
+	// (2) Construct the members. members maps partitions representatives to the
 	// members (references) of partitions.
 	for ref, parent := range p.parents {
 		if ref == parent {
@@ -324,16 +346,18 @@ func (p *Partitions) finalize() {
 			p.members[rep] = append(p.members[rep], ref)
 		}
 	}
-	// Normalize fieldRefs table in a way that it only contains partition
+	// (3) Normalize fieldRefs table in a way that it only contains partition
 	// representatives.
 	for _, pinfo := range p.partitions {
 		for fd, entry := range pinfo.fieldRefs {
 			pinfo.fieldRefs[fd] = p.Representative(entry)
 		}
 	}
+	// (4) Construct the map from field references to their parents.
+	p.constructFieldParentMap()
 }
 
-// Has returns true if "ref" is a reference present in the state.
+// Has returns true if "ref" is a reference present in the partitions.
 func (p *Partitions) Has(ref Reference) bool {
 	_, ok := p.parents[ref]
 	return ok
@@ -358,7 +382,7 @@ func (p *Partitions) Representatives() ReferenceSet {
 }
 
 // Representative gets the partition representative of reference "ref"
-// ("ref" must belong to this state).
+// ("ref" must belong to this partitions).
 func (p *Partitions) Representative(ref Reference) Reference {
 	return p.parents[ref]
 }
@@ -378,8 +402,8 @@ func (p *Partitions) String() string {
 }
 
 // FieldParents returns the parents of a field reference. Return nil if ref has no parent.
-// For example, return o for r if "o[x -> r]" is in state. This shall be
-// called only after the state has been finalized.
+// For example, return o for r if "o[x -> r]" is in partitions. This shall be
+// called only after the partitions have been finalized.
 func (p *Partitions) FieldParents(ref Reference) []Reference {
 	return p.revFields[ref]
 }
@@ -416,7 +440,7 @@ func (p *Partitions) MembersForRep(rep Reference) []Reference {
 }
 
 // PartitionMembers gets the list of members in the partition to which "ref" belongs.
-// Precondition: "ref" must be a reference present in the state.
+// Precondition: "ref" must be a reference present in the partitions.
 func (p *Partitions) PartitionMembers(ref Reference) []Reference {
 	return p.MembersForRep(p.Representative(ref))
 }


Test patch:
diff --git a/internal/pkg/earpointer/analysis_test.go b/internal/pkg/earpointer/analysis_test.go
index f102505..b2238e9 100644
--- a/internal/pkg/earpointer/analysis_test.go
+++ b/internal/pkg/earpointer/analysis_test.go
@@ -151,12 +151,10 @@ func TestField(t *testing.T) {
 	}
 	// t2's field x points to t3
 	want := concat(map[string]string{
-		"{f.t0}":         "--> *f.t0",
-		"{*f.t0}":        "[x->f.t1]",
-		"{f.t1}":         "--> f.a",
-		"{f.a}":          "[]",
-		"{f.t2}":         "[x->f.t3]",
-		"{f.t2[.],f.t3}": "--> f.a",
+		"{f.t0}":       "--> f.t2",
+		"{*f.t0,f.t2}": "[x->f.t1]",
+		"{f.t1}":       "--> f.t3",
+		"{f.a,f.t3}":   "[]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -185,15 +183,12 @@ func TestEmbeddedField(t *testing.T) {
 		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 := concat(map[string]string{
-		"{f.i}":     "[]",
-		"{f.t0}":    "--> *f.t0",
-		"{*f.t0}":   "[t->f.t1]",
-		"{f.t1}":    "[]",
-		"{f.t2}":    "[t->f.t2[.]]",
-		"{f.t2[.]}": "[]",
-		"{f.t3}":    "[]",
+		"{f.i}":        "[]",
+		"{*f.t0,f.t2}": "[t->f.t1]",
+		"{f.t0}":       "--> f.t2",
+		"{*f.t1,f.t3}": "[]",
+		"{f.t1}":       "--> f.t3",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -232,35 +227,17 @@ func TestStructCopy(t *testing.T) { // mainly for coverage test
 	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 := concat(map[string]string{
-		"{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}":    "[x->f.t5[.], y->f.t5[.]]",
-		"{f.t5[.]}": "--> f.i",
-		"{f.v1}":    "[x->f.t2, y->f.t3]",
-		"{f.v2}":    "[x->f.t4, y->f.v2[.]]",
-		"{f.v2[.]}": "--> f.i",
-	})
-	want2 := concat(map[string]string{
-		"{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}":    "[x->f.t5[.], y->f.t5[.]]",
-		"{f.t5[.]}": "--> f.j",
-		"{f.v1}":    "[x->f.t2, y->f.t3]",
-		"{f.v2}":    "[x->f.t4, y->f.v2[.]]",
-		"{f.v2[.]}": "--> f.j",
+	want := concat(map[string]string{
+		"{f.i}":            "[]",
+		"{f.j}":            "[]",
+		"{f.t0}":           "--> f.t5",
+		"{f.t1}":           "--> f.t5",
+		"{f.t2,f.t4}":      "--> f.i",
+		"{f.t3}":           "--> f.j",
+		"{f.t5,f.v1,f.v2}": "[x->f.t4, y->f.t3]",
 	})
-	if got := state.String(); got != want1 && got != want2 {
-		t.Errorf("got: %s\n want: %s\n or\n %s", got, want1, want2)
+	if got := state.String(); got != want {
+		t.Errorf("got: %s\n want: %s\n", got, want)
 	}
 }
 
@@ -294,17 +271,12 @@ func TestEmbeddedFieldClone(t *testing.T) {
 		t.Fatal(err)
 	}
 	want := concat(map[string]string{
-		"{f.i}":     "[]",
-		"{f.t0}":    "--> f.i",
-		"{f.t1}":    "--> f.v1",
-		"{f.t2}":    "--> f.v2",
-		"{f.t3}":    "--> f.t4",
-		"{f.t4}":    "[]",
-		"{f.t5}":    "[x->f.t5[.]]",
-		"{f.t5[.]}": "[]",
-		"{f.v1}":    "[x->f.v1[.]]",
-		"{f.v1[.]}": "[]",
-		"{f.v2}":    "[x->f.t3]",
+		"{f.i,f.t4}":       "[]",
+		"{f.t0}":           "--> f.t4",
+		"{f.t1}":           "--> f.t5",
+		"{f.t2}":           "--> f.t5",
+		"{f.t3}":           "--> f.t4",
+		"{f.t5,f.v1,f.v2}": "[x->f.t3]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -331,8 +303,10 @@ func TestIndexAddr(t *testing.T) {
 		t.Fatal(err)
 	}
 	want := concat(map[string]string{
-		"{f.a}":  "[1->f.t0]",
-		"{f.b}":  "[AnyField->f.t1]",
+		"{f.a}":  "--> *f.a",
+		"{*f.a}": "[1->f.t0, AnyField->f.t0]",
+		"{f.b}":  "--> *f.b",
+		"{*f.b}": "[AnyField->f.t1]",
 		"{f.t0}": "--> f.t2",
 		"{f.t1}": "--> f.t2",
 		"{f.t2}": "[]",
@@ -364,11 +338,10 @@ func TestIndex(t *testing.T) {
 	}
 	// t2's field 0 points to t3
 	want := concat(map[string]string{
-		"{f.a}":  "[]",
-		"{f.t0}": "--> f.t2",
-		"{f.t1}": "--> f.a",
-		"{f.t2}": "[0->f.t3]",
-		"{f.t3}": "[]",
+		"{f.a}":        "[]",
+		"{f.t0}":       "--> f.t2",
+		"{f.t1,f.t3}":  "--> f.a",
+		"{*f.t0,f.t2}": "[0->f.t3, AnyField->f.t3]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -441,7 +414,8 @@ func TestStore(t *testing.T) {
 	want := concat(map[string]string{
 		"{f.a}":  "--> *f.a",
 		"{*f.a}": "[x->f.t0, y->f.t2]",
-		"{f.b}":  "[10->f.t3]",
+		"{f.b}":  "--> *f.b",
+		"{*f.b}": "[10->f.t3, AnyField->f.t3]",
 		"{f.t0}": "--> f.t1",
 		"{f.t1}": "[]",
 		"{f.t2}": "--> f.t4",
@@ -511,10 +485,9 @@ func TestMapAccess(t *testing.T) {
 		t.Fatal(err)
 	}
 	want := concat(map[string]string{
-		"{f.m}":       "[0->f.t0, 1->f.t2, AnyField->f.t2]",
-		"{f.t1,f.t2}": "[]",
-		"{t}":         "--> f.t0",
-		"{f.t0}":      "[]",
+		"{f.m}":            "[0->f.t2, 1->f.t2, AnyField->f.t2]",
+		"{f.t0,f.t1,f.t2}": "[]",
+		"{t}":              "--> f.t2",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -543,7 +516,7 @@ func TestLookUp(t *testing.T) {
 		t.Fatal(err)
 	}
 	want := concat(map[string]string{
-		"{f.a}":  "[10->f.t1]",
+		"{f.a}":  "[10->f.t1, AnyField->f.t1]",
 		"{f.t1}": "--> f.t3",
 		"{f.t3}": "[]",
 	})
@@ -639,7 +612,7 @@ func TestBinOp(t *testing.T) {
 	if err != nil {
 		t.Fatal(err)
 	}
-	want := "{f.a,f.b,f.t0}: []"
+	want := "{f.a}: [], {f.b}: [], {f.t0}: [left->f.a, right->f.b]"
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
 	}
@@ -697,6 +670,58 @@ func TestChannel(t *testing.T) {
 	}
 }
 
+func TestSelect(t *testing.T) {
+	code := `package p
+	func f(c1, c2 chan string, m1, m2 string) {
+		select {
+        case c1 <- m1:
+			//
+        case m := <- c2:
+			print(m)
+        case c1 <- m2:
+			//
+        }
+	}
+	`
+	/*
+		func f(c1 chan string, c2 chan string, m1 string, m2 string):
+		0:                                                                entry P:0 S:2
+			t0 = select blocking [c1<-m1, <-c2, c1<-m2] (index int, ok bool, string, string)
+			t1 = extract t0 #0                                                  int
+			t2 = t1 == 0:int                                                   bool
+			if t2 goto 1 else 2
+		1:                                               select.done P:4 S:0
+			return
+		2:                                               select.next P:1 S:2
+			t3 = t1 == 1:int                                            bool
+			if t3 goto 3 else 4
+		3:                                               select.body P:1 S:1
+			t4 = extract t0 #2                                        string
+			t5 = print(t4)                                                ()
+			jump 1
+		4:                                               select.next P:1 S:2
+			t6 = t1 == 2:int                                            bool
+			if t6 goto 1 else 5
+		5:                                               select.next P:1 S:2
+			t7 = make interface{} <- string ("blocking select m...":string) interface{}
+			panic t7
+	*/
+	state, err := runCodeK0(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	want := concat(map[string]string{
+		"{f.c1}":      "[AnyField->f.m2]",
+		"{f.c2}":      "[AnyField->f.t4]",
+		"{f.m1,f.m2}": "[]",
+		"{f.t7}":      "[]",
+		"{f.t4}":      "[]",
+	})
+	if diff := cmp.Diff(want, state.String()); diff != "" {
+		t.Errorf("diff (-want +got):\n%s", diff)
+	}
+}
+
 func TestSlice(t *testing.T) {
 	code := `package p
 	func f(s [6]int) {
@@ -825,13 +850,12 @@ func TestCallWithTupleReturn(t *testing.T) {
 	// f.a and g.a are unified due to the call;
 	// f.t1 and g.a are unified due to the return of this call.
 	// Here (f.t1, f.t2) == f.t0 == (g.a, g.t0).
-	// Note that g.t0 and f.t2 are not unified because they are structs.
+	// Note that g.t0 and f.t2 are unified due to an approximation.
 	want := concat(map[string]string{
-		"{f.t0}":         "[0->f.t1]",
+		"{f.t0}":         "[0->g.a, 1->g.t0]",
 		"{f.a,f.t1,g.a}": "[]",
-		"{f.t2}":         "[]",
+		"{f.t2,g.t0}":    "[]",
 		"{x}":            "--> g.t0",
-		"{g.t0}":         "[]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -871,7 +895,7 @@ func TestClosureCall(t *testing.T) {
 		"{f$1.i,f.t0,f.t4}": "[]",
 		"{f$1.j,f.t1,f.t5}": "[]",
 		"{f.t2}":            "[]",
-		"{f.t3}":            "[0->f.t4, 1->f.t5]",
+		"{f.t3}":            "[0->f.t0, 1->f.t1]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
 		t.Errorf("diff (-want +got):\n%s", diff)
@@ -990,7 +1014,7 @@ func TestGoDefer(t *testing.T) {
 	// Free variable g$1.i is unified with g.t0 due to closure binding;
 	// Arguments g$2.k and g.i are unified due to the defer call.
 	want := concat(map[string]string{
-		"{g$1.i,g.t0}":            "--> g$2.k",
+		"{g$1.i,g.t0}":            "--> g.t2",
 		"{g$1.t0,g$2.k,g.i,g.t2}": "[]",
 		"{g.t1}":                  "[]",
 	})
@@ -1027,9 +1051,10 @@ func TestCallBuiltin(t *testing.T) {
 	// f.d1 contains a field pointing at f.x due to the "copy".
 	// f.s, f.t2 and f.r3 ("d2") are unified due to the "append".
 	want := concat(map[string]string{
-		"{f.d1[.],f.t1}":       "--> f.x",
-		"{f.d1}":               "[0->f.t1]",
-		"{f.s,f.t0,f.t2,f.t3}": "[0->f.t1]",
+		"{f.d1}":               "--> *f.t0",
+		"{*f.t0,f.d1[.]}":      "[0->f.t1, AnyField->f.t1]",
+		"{f.s,f.t0,f.t2,f.t3}": "--> *f.t0",
+		"{f.t1}":               "--> f.x",
 		"{f.x}":                "[]",
 	})
 	if diff := cmp.Diff(want, state.String()); diff != "" {
@@ -1037,6 +1062,45 @@ func TestCallBuiltin(t *testing.T) {
 	}
 }
 
+func TestKnownCall(t *testing.T) {
+	code := `package p
+	import (
+		"fmt"
+		"os"
+	)
+	func f(x string) {
+		_ = fmt.Sprintf(x)
+		fmt.Fprintf(os.Stderr, x)
+	}
+	`
+	/*
+		func f(x string):
+		0:                                                   entry P:0 S:0
+			t0 = fmt.Sprintf(x, nil:[]interface{}...)        string
+			t1 = *os.Stderr                                  *os.File
+			t2 = make io.Writer <- *os.File (t1)             io.Writer
+			t3 = fmt.Fprintf(t2, x, nil:[]interface{}...)   (n int, err error)
+			return
+	*/
+	state, err := runCodeK0(code)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// f.x is pointed by a field of f.t0,
+	// and by a field of f.t1 (i.e. os.Stderr).
+	want := concat(map[string]string{
+		"{Stderr}":    "--> f.t1",
+		"{f.t0}":      "[1->f.x]",
+		"{f.t1,f.t2}": "[2->f.x]",
+		"{f.t3}":      "[]",
+		"{f.x}":       "[]",
+	})
+	// Exclude the references in packages "fmt" and "os".
+	if !strings.Contains(state.String(), want) {
+		t.Errorf("want:\n%s", want)
+	}
+}
+
 func TestVariadicCall(t *testing.T) {
 	code := `package p
 	func g(ks ...*int) *int {
@@ -1068,15 +1132,24 @@ func TestVariadicCall(t *testing.T) {
 	if err != nil {
 		t.Fatal(err)
 	}
-	want := concat(map[string]string{
-		"{f.a,f.t4,g.t1}":  "[]",
-		"{f.b}":            "[]",
-		"{f.t0,f.t3,g.ks}": "[0->g.t0, 1->f.t2]",
-		"{f.t1,g.t0}":      "--> g.t1",
-		"{f.t2}":           "--> f.b",
+	// Handle the non-determinism when choosing the representative during unifying.
+	// The representative of {*f.t0,*g.ks} may be *f.t0 or *g.ks.
+	want1 := concat(map[string]string{
+		"{f.a,f.b,f.t4,g.t1}": "[]",
+		"{*f.t0,*g.ks}":       "[0->g.t0, 1->g.t0, AnyField->g.t0]",
+		"{f.t0,f.t3,g.ks}":    "--> *f.t0", // non-determinism
+		"{f.t1,f.t2,g.t0}":    "--> f.t4",
 	})
-	if diff := cmp.Diff(want, state.String()); diff != "" {
-		t.Errorf("diff (-want +got):\n%s", diff)
+	want2 := concat(map[string]string{
+		"{f.a,f.b,f.t4,g.t1}": "[]",
+		"{*f.t0,*g.ks}":       "[0->g.t0, 1->g.t0, AnyField->g.t0]",
+		"{f.t0,f.t3,g.ks}":    "--> *g.ks", // non-determinism
+		"{f.t1,f.t2,g.t0}":    "--> f.t4",
+	})
+	diff1 := cmp.Diff(want1, state.String())
+	diff2 := cmp.Diff(want2, state.String())
+	if diff1 != "" && diff2 != "" {
+		t.Errorf("diff (-want +got):\n%s", diff1+diff2)
 	}
 }