gen.go

Documentation: golang.org/x/tools/go/pointer

     1  // Copyright 2013 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package pointer
     6  
     7  // This file defines the constraint generation phase.
     8  
     9  // TODO(adonovan): move the constraint definitions and the store() etc
    10  // functions which add them (and are also used by the solver) into a
    11  // new file, constraints.go.
    12  
    13  import (
    14  	"fmt"
    15  	"go/token"
    16  	"go/types"
    17  	"strings"
    18  
    19  	"golang.org/x/tools/go/callgraph"
    20  	"golang.org/x/tools/go/ssa"
    21  	"golang.org/x/tools/internal/typeparams"
    22  )
    23  
    24  var (
    25  	tEface     = types.NewInterfaceType(nil, nil).Complete()
    26  	tInvalid   = types.Typ[types.Invalid]
    27  	tUnsafePtr = types.Typ[types.UnsafePointer]
    28  )
    29  
    30  // ---------- Node creation ----------
    31  
    32  // nextNode returns the index of the next unused node.
    33  func (a *analysis) nextNode() nodeid {
    34  	return nodeid(len(a.nodes))
    35  }
    36  
    37  // addNodes creates nodes for all scalar elements in type typ, and
    38  // returns the id of the first one, or zero if the type was
    39  // analytically uninteresting.
    40  //
    41  // comment explains the origin of the nodes, as a debugging aid.
    42  func (a *analysis) addNodes(typ types.Type, comment string) nodeid {
    43  	id := a.nextNode()
    44  	for _, fi := range a.flatten(typ) {
    45  		a.addOneNode(fi.typ, comment, fi)
    46  	}
    47  	if id == a.nextNode() {
    48  		return 0 // type contained no pointers
    49  	}
    50  	return id
    51  }
    52  
    53  // addOneNode creates a single node with type typ, and returns its id.
    54  //
    55  // typ should generally be scalar (except for tagged.T nodes
    56  // and struct/array identity nodes).  Use addNodes for non-scalar types.
    57  //
    58  // comment explains the origin of the nodes, as a debugging aid.
    59  // subelement indicates the subelement, e.g. ".a.b[*].c".
    60  func (a *analysis) addOneNode(typ types.Type, comment string, subelement *fieldInfo) nodeid {
    61  	id := a.nextNode()
    62  	a.nodes = append(a.nodes, &node{typ: typ, subelement: subelement, solve: new(solverState)})
    63  	if a.log != nil {
    64  		fmt.Fprintf(a.log, "\tcreate n%d %s for %s%s\n",
    65  			id, typ, comment, subelement.path())
    66  	}
    67  	return id
    68  }
    69  
    70  // setValueNode associates node id with the value v.
    71  // cgn identifies the context iff v is a local variable.
    72  func (a *analysis) setValueNode(v ssa.Value, id nodeid, cgn *cgnode) {
    73  	if cgn != nil {
    74  		a.localval[v] = id
    75  	} else {
    76  		a.globalval[v] = id
    77  	}
    78  	if a.log != nil {
    79  		fmt.Fprintf(a.log, "\tval[%s] = n%d  (%T)\n", v.Name(), id, v)
    80  	}
    81  
    82  	// Due to context-sensitivity, we may encounter the same Value
    83  	// in many contexts. We merge them to a canonical node, since
    84  	// that's what all clients want.
    85  
    86  	// Record the (v, id) relation if the client has queried pts(v).
    87  	if _, ok := a.config.Queries[v]; ok {
    88  		t := v.Type()
    89  		ptr, ok := a.result.Queries[v]
    90  		if !ok {
    91  			// First time?  Create the canonical query node.
    92  			ptr = Pointer{a, a.addNodes(t, "query")}
    93  			a.result.Queries[v] = ptr
    94  		}
    95  		a.result.Queries[v] = ptr
    96  		a.copy(ptr.n, id, a.sizeof(t))
    97  	}
    98  
    99  	// Record the (*v, id) relation if the client has queried pts(*v).
   100  	if _, ok := a.config.IndirectQueries[v]; ok {
   101  		t := v.Type()
   102  		ptr, ok := a.result.IndirectQueries[v]
   103  		if !ok {
   104  			// First time? Create the canonical indirect query node.
   105  			ptr = Pointer{a, a.addNodes(v.Type(), "query.indirect")}
   106  			a.result.IndirectQueries[v] = ptr
   107  		}
   108  		a.genLoad(cgn, ptr.n, v, 0, a.sizeof(t))
   109  	}
   110  
   111  	for _, query := range a.config.extendedQueries[v] {
   112  		t, nid := a.evalExtendedQuery(v.Type().Underlying(), id, query.ops)
   113  
   114  		if query.ptr.a == nil {
   115  			query.ptr.a = a
   116  			query.ptr.n = a.addNodes(t, "query.extended")
   117  		}
   118  		a.copy(query.ptr.n, nid, a.sizeof(t))
   119  	}
   120  }
   121  
   122  // endObject marks the end of a sequence of calls to addNodes denoting
   123  // a single object allocation.
   124  //
   125  // obj is the start node of the object, from a prior call to nextNode.
   126  // Its size, flags and optional data will be updated.
   127  func (a *analysis) endObject(obj nodeid, cgn *cgnode, data interface{}) *object {
   128  	// Ensure object is non-empty by padding;
   129  	// the pad will be the object node.
   130  	size := uint32(a.nextNode() - obj)
   131  	if size == 0 {
   132  		a.addOneNode(tInvalid, "padding", nil)
   133  	}
   134  	objNode := a.nodes[obj]
   135  	o := &object{
   136  		size: size, // excludes padding
   137  		cgn:  cgn,
   138  		data: data,
   139  	}
   140  	objNode.obj = o
   141  
   142  	return o
   143  }
   144  
   145  // makeFunctionObject creates and returns a new function object
   146  // (contour) for fn, and returns the id of its first node.  It also
   147  // enqueues fn for subsequent constraint generation.
   148  //
   149  // For a context-sensitive contour, callersite identifies the sole
   150  // callsite; for shared contours, caller is nil.
   151  func (a *analysis) makeFunctionObject(fn *ssa.Function, callersite *callsite) nodeid {
   152  	if a.log != nil {
   153  		fmt.Fprintf(a.log, "\t---- makeFunctionObject %s\n", fn)
   154  	}
   155  
   156  	// obj is the function object (identity, params, results).
   157  	obj := a.nextNode()
   158  	cgn := a.makeCGNode(fn, obj, callersite)
   159  	sig := fn.Signature
   160  	a.addOneNode(sig, "func.cgnode", nil) // (scalar with Signature type)
   161  	if recv := sig.Recv(); recv != nil {
   162  		a.addNodes(recv.Type(), "func.recv")
   163  	}
   164  	a.addNodes(sig.Params(), "func.params")
   165  	a.addNodes(sig.Results(), "func.results")
   166  	a.endObject(obj, cgn, fn).flags |= otFunction
   167  
   168  	if a.log != nil {
   169  		fmt.Fprintf(a.log, "\t----\n")
   170  	}
   171  
   172  	// Queue it up for constraint processing.
   173  	a.genq = append(a.genq, cgn)
   174  
   175  	return obj
   176  }
   177  
   178  // makeTagged creates a tagged object of type typ.
   179  func (a *analysis) makeTagged(typ types.Type, cgn *cgnode, data interface{}) nodeid {
   180  	obj := a.addOneNode(typ, "tagged.T", nil) // NB: type may be non-scalar!
   181  	a.addNodes(typ, "tagged.v")
   182  	a.endObject(obj, cgn, data).flags |= otTagged
   183  	return obj
   184  }
   185  
   186  // makeRtype returns the canonical tagged object of type *rtype whose
   187  // payload points to the sole rtype object for T.
   188  //
   189  // TODO(adonovan): move to reflect.go; it's part of the solver really.
   190  func (a *analysis) makeRtype(T types.Type) nodeid {
   191  	if v := a.rtypes.At(T); v != nil {
   192  		return v.(nodeid)
   193  	}
   194  
   195  	// Create the object for the reflect.rtype itself, which is
   196  	// ordinarily a large struct but here a single node will do.
   197  	obj := a.nextNode()
   198  	a.addOneNode(T, "reflect.rtype", nil)
   199  	a.endObject(obj, nil, T)
   200  
   201  	id := a.makeTagged(a.reflectRtypePtr, nil, T)
   202  	a.nodes[id+1].typ = T // trick (each *rtype tagged object is a singleton)
   203  	a.addressOf(a.reflectRtypePtr, id+1, obj)
   204  
   205  	a.rtypes.Set(T, id)
   206  	return id
   207  }
   208  
   209  // rtypeValue returns the type of the *reflect.rtype-tagged object obj.
   210  func (a *analysis) rtypeTaggedValue(obj nodeid) types.Type {
   211  	tDyn, t, _ := a.taggedValue(obj)
   212  	if tDyn != a.reflectRtypePtr {
   213  		panic(fmt.Sprintf("not a *reflect.rtype-tagged object: obj=n%d tag=%v payload=n%d", obj, tDyn, t))
   214  	}
   215  	return a.nodes[t].typ
   216  }
   217  
   218  // valueNode returns the id of the value node for v, creating it (and
   219  // the association) as needed.  It may return zero for uninteresting
   220  // values containing no pointers.
   221  func (a *analysis) valueNode(v ssa.Value) nodeid {
   222  	// Value nodes for locals are created en masse by genFunc.
   223  	if id, ok := a.localval[v]; ok {
   224  		return id
   225  	}
   226  
   227  	// Value nodes for globals are created on demand.
   228  	id, ok := a.globalval[v]
   229  	if !ok {
   230  		var comment string
   231  		if a.log != nil {
   232  			comment = v.String()
   233  		}
   234  		id = a.addNodes(v.Type(), comment)
   235  		if obj := a.objectNode(nil, v); obj != 0 {
   236  			a.addressOf(v.Type(), id, obj)
   237  		}
   238  		a.setValueNode(v, id, nil)
   239  	}
   240  	return id
   241  }
   242  
   243  // valueOffsetNode ascertains the node for tuple/struct value v,
   244  // then returns the node for its subfield #index.
   245  func (a *analysis) valueOffsetNode(v ssa.Value, index int) nodeid {
   246  	id := a.valueNode(v)
   247  	if id == 0 {
   248  		panic(fmt.Sprintf("cannot offset within n0: %s = %s", v.Name(), v))
   249  	}
   250  	return id + nodeid(a.offsetOf(v.Type(), index))
   251  }
   252  
   253  // isTaggedObject reports whether object obj is a tagged object.
   254  func (a *analysis) isTaggedObject(obj nodeid) bool {
   255  	return a.nodes[obj].obj.flags&otTagged != 0
   256  }
   257  
   258  // taggedValue returns the dynamic type tag, the (first node of the)
   259  // payload, and the indirect flag of the tagged object starting at id.
   260  // Panic ensues if !isTaggedObject(id).
   261  func (a *analysis) taggedValue(obj nodeid) (tDyn types.Type, v nodeid, indirect bool) {
   262  	n := a.nodes[obj]
   263  	flags := n.obj.flags
   264  	if flags&otTagged == 0 {
   265  		panic(fmt.Sprintf("not a tagged object: n%d", obj))
   266  	}
   267  	return n.typ, obj + 1, flags&otIndirect != 0
   268  }
   269  
   270  // funcParams returns the first node of the params (P) block of the
   271  // function whose object node (obj.flags&otFunction) is id.
   272  func (a *analysis) funcParams(id nodeid) nodeid {
   273  	n := a.nodes[id]
   274  	if n.obj == nil || n.obj.flags&otFunction == 0 {
   275  		panic(fmt.Sprintf("funcParams(n%d): not a function object block", id))
   276  	}
   277  	return id + 1
   278  }
   279  
   280  // funcResults returns the first node of the results (R) block of the
   281  // function whose object node (obj.flags&otFunction) is id.
   282  func (a *analysis) funcResults(id nodeid) nodeid {
   283  	n := a.nodes[id]
   284  	if n.obj == nil || n.obj.flags&otFunction == 0 {
   285  		panic(fmt.Sprintf("funcResults(n%d): not a function object block", id))
   286  	}
   287  	sig := n.typ.(*types.Signature)
   288  	id += 1 + nodeid(a.sizeof(sig.Params()))
   289  	if sig.Recv() != nil {
   290  		id += nodeid(a.sizeof(sig.Recv().Type()))
   291  	}
   292  	return id
   293  }
   294  
   295  // ---------- Constraint creation ----------
   296  
   297  // copy creates a constraint of the form dst = src.
   298  // sizeof is the width (in logical fields) of the copied type.
   299  func (a *analysis) copy(dst, src nodeid, sizeof uint32) {
   300  	if src == dst || sizeof == 0 {
   301  		return // trivial
   302  	}
   303  	if src == 0 || dst == 0 {
   304  		panic(fmt.Sprintf("ill-typed copy dst=n%d src=n%d", dst, src))
   305  	}
   306  	for i := uint32(0); i < sizeof; i++ {
   307  		a.addConstraint(&copyConstraint{dst, src})
   308  		src++
   309  		dst++
   310  	}
   311  }
   312  
   313  // addressOf creates a constraint of the form id = &obj.
   314  // T is the type of the address.
   315  func (a *analysis) addressOf(T types.Type, id, obj nodeid) {
   316  	if id == 0 {
   317  		panic("addressOf: zero id")
   318  	}
   319  	if obj == 0 {
   320  		panic("addressOf: zero obj")
   321  	}
   322  	if a.shouldTrack(T) {
   323  		a.addConstraint(&addrConstraint{id, obj})
   324  	}
   325  }
   326  
   327  // load creates a load constraint of the form dst = src[offset].
   328  // offset is the pointer offset in logical fields.
   329  // sizeof is the width (in logical fields) of the loaded type.
   330  func (a *analysis) load(dst, src nodeid, offset, sizeof uint32) {
   331  	if dst == 0 {
   332  		return // load of non-pointerlike value
   333  	}
   334  	if src == 0 && dst == 0 {
   335  		return // non-pointerlike operation
   336  	}
   337  	if src == 0 || dst == 0 {
   338  		panic(fmt.Sprintf("ill-typed load dst=n%d src=n%d", dst, src))
   339  	}
   340  	for i := uint32(0); i < sizeof; i++ {
   341  		a.addConstraint(&loadConstraint{offset, dst, src})
   342  		offset++
   343  		dst++
   344  	}
   345  }
   346  
   347  // store creates a store constraint of the form dst[offset] = src.
   348  // offset is the pointer offset in logical fields.
   349  // sizeof is the width (in logical fields) of the stored type.
   350  func (a *analysis) store(dst, src nodeid, offset uint32, sizeof uint32) {
   351  	if src == 0 {
   352  		return // store of non-pointerlike value
   353  	}
   354  	if src == 0 && dst == 0 {
   355  		return // non-pointerlike operation
   356  	}
   357  	if src == 0 || dst == 0 {
   358  		panic(fmt.Sprintf("ill-typed store dst=n%d src=n%d", dst, src))
   359  	}
   360  	for i := uint32(0); i < sizeof; i++ {
   361  		a.addConstraint(&storeConstraint{offset, dst, src})
   362  		offset++
   363  		src++
   364  	}
   365  }
   366  
   367  // offsetAddr creates an offsetAddr constraint of the form dst = &src.#offset.
   368  // offset is the field offset in logical fields.
   369  // T is the type of the address.
   370  func (a *analysis) offsetAddr(T types.Type, dst, src nodeid, offset uint32) {
   371  	if !a.shouldTrack(T) {
   372  		return
   373  	}
   374  	if offset == 0 {
   375  		// Simplify  dst = &src->f0
   376  		//       to  dst = src
   377  		// (NB: this optimisation is defeated by the identity
   378  		// field prepended to struct and array objects.)
   379  		a.copy(dst, src, 1)
   380  	} else {
   381  		a.addConstraint(&offsetAddrConstraint{offset, dst, src})
   382  	}
   383  }
   384  
   385  // typeAssert creates a typeFilter or untag constraint of the form dst = src.(T):
   386  // typeFilter for an interface, untag for a concrete type.
   387  // The exact flag is specified as for untagConstraint.
   388  func (a *analysis) typeAssert(T types.Type, dst, src nodeid, exact bool) {
   389  	if isInterface(T) {
   390  		a.addConstraint(&typeFilterConstraint{T, dst, src})
   391  	} else {
   392  		a.addConstraint(&untagConstraint{T, dst, src, exact})
   393  	}
   394  }
   395  
   396  // addConstraint adds c to the constraint set.
   397  func (a *analysis) addConstraint(c constraint) {
   398  	a.constraints = append(a.constraints, c)
   399  	if a.log != nil {
   400  		fmt.Fprintf(a.log, "\t%s\n", c)
   401  	}
   402  }
   403  
   404  // copyElems generates load/store constraints for *dst = *src,
   405  // where src and dst are slices or *arrays.
   406  func (a *analysis) copyElems(cgn *cgnode, typ types.Type, dst, src ssa.Value) {
   407  	tmp := a.addNodes(typ, "copy")
   408  	sz := a.sizeof(typ)
   409  	a.genLoad(cgn, tmp, src, 1, sz)
   410  	a.genStore(cgn, dst, tmp, 1, sz)
   411  }
   412  
   413  // ---------- Constraint generation ----------
   414  
   415  // genConv generates constraints for the conversion operation conv.
   416  func (a *analysis) genConv(conv *ssa.Convert, cgn *cgnode) {
   417  	res := a.valueNode(conv)
   418  	if res == 0 {
   419  		return // result is non-pointerlike
   420  	}
   421  
   422  	tSrc := conv.X.Type()
   423  	tDst := conv.Type()
   424  
   425  	switch utSrc := tSrc.Underlying().(type) {
   426  	case *types.Slice:
   427  		// []byte/[]rune -> string?
   428  		return
   429  
   430  	case *types.Pointer:
   431  		// *T -> unsafe.Pointer?
   432  		if tDst.Underlying() == tUnsafePtr {
   433  			return // we don't model unsafe aliasing (unsound)
   434  		}
   435  
   436  	case *types.Basic:
   437  		switch tDst.Underlying().(type) {
   438  		case *types.Pointer:
   439  			// Treat unsafe.Pointer->*T conversions like
   440  			// new(T) and create an unaliased object.
   441  			if utSrc == tUnsafePtr {
   442  				obj := a.addNodes(mustDeref(tDst), "unsafe.Pointer conversion")
   443  				a.endObject(obj, cgn, conv)
   444  				a.addressOf(tDst, res, obj)
   445  				return
   446  			}
   447  
   448  		case *types.Slice:
   449  			// string -> []byte/[]rune (or named aliases)?
   450  			if utSrc.Info()&types.IsString != 0 {
   451  				obj := a.addNodes(sliceToArray(tDst), "convert")
   452  				a.endObject(obj, cgn, conv)
   453  				a.addressOf(tDst, res, obj)
   454  				return
   455  			}
   456  
   457  		case *types.Basic:
   458  			// All basic-to-basic type conversions are no-ops.
   459  			// This includes uintptr<->unsafe.Pointer conversions,
   460  			// which we (unsoundly) ignore.
   461  			return
   462  		}
   463  	}
   464  
   465  	panic(fmt.Sprintf("illegal *ssa.Convert %s -> %s: %s", tSrc, tDst, conv.Parent()))
   466  }
   467  
   468  // genAppend generates constraints for a call to append.
   469  func (a *analysis) genAppend(instr *ssa.Call, cgn *cgnode) {
   470  	// Consider z = append(x, y).   y is optional.
   471  	// This may allocate a new [1]T array; call its object w.
   472  	// We get the following constraints:
   473  	// 	z = x
   474  	// 	z = &w
   475  	//     *z = *y
   476  
   477  	x := instr.Call.Args[0]
   478  
   479  	z := instr
   480  	a.copy(a.valueNode(z), a.valueNode(x), 1) // z = x
   481  
   482  	if len(instr.Call.Args) == 1 {
   483  		return // no allocation for z = append(x) or _ = append(x).
   484  	}
   485  
   486  	// TODO(adonovan): test append([]byte, ...string) []byte.
   487  
   488  	y := instr.Call.Args[1]
   489  	tArray := sliceToArray(instr.Call.Args[0].Type())
   490  
   491  	w := a.nextNode()
   492  	a.addNodes(tArray, "append")
   493  	a.endObject(w, cgn, instr)
   494  
   495  	a.copyElems(cgn, tArray.Elem(), z, y)        // *z = *y
   496  	a.addressOf(instr.Type(), a.valueNode(z), w) //  z = &w
   497  }
   498  
   499  // genBuiltinCall generates constraints for a call to a built-in.
   500  func (a *analysis) genBuiltinCall(instr ssa.CallInstruction, cgn *cgnode) {
   501  	call := instr.Common()
   502  	switch call.Value.(*ssa.Builtin).Name() {
   503  	case "append":
   504  		// Safe cast: append cannot appear in a go or defer statement.
   505  		a.genAppend(instr.(*ssa.Call), cgn)
   506  
   507  	case "copy":
   508  		tElem := call.Args[0].Type().Underlying().(*types.Slice).Elem()
   509  		a.copyElems(cgn, tElem, call.Args[0], call.Args[1])
   510  
   511  	case "panic":
   512  		a.copy(a.panicNode, a.valueNode(call.Args[0]), 1)
   513  
   514  	case "recover":
   515  		if v := instr.Value(); v != nil {
   516  			a.copy(a.valueNode(v), a.panicNode, 1)
   517  		}
   518  
   519  	case "print":
   520  		// In the tests, the probe might be the sole reference
   521  		// to its arg, so make sure we create nodes for it.
   522  		if len(call.Args) > 0 {
   523  			a.valueNode(call.Args[0])
   524  		}
   525  
   526  	case "ssa:wrapnilchk":
   527  		a.copy(a.valueNode(instr.Value()), a.valueNode(call.Args[0]), 1)
   528  
   529  	default:
   530  		// No-ops: close len cap real imag complex print println delete.
   531  	}
   532  }
   533  
   534  // shouldUseContext defines the context-sensitivity policy.  It
   535  // returns true if we should analyse all static calls to fn anew.
   536  //
   537  // Obviously this interface rather limits how much freedom we have to
   538  // choose a policy.  The current policy, rather arbitrarily, is true
   539  // for intrinsics and accessor methods (actually: short, single-block,
   540  // call-free functions).  This is just a starting point.
   541  func (a *analysis) shouldUseContext(fn *ssa.Function) bool {
   542  	if a.findIntrinsic(fn) != nil {
   543  		return true // treat intrinsics context-sensitively
   544  	}
   545  	if len(fn.Blocks) != 1 {
   546  		return false // too expensive
   547  	}
   548  	blk := fn.Blocks[0]
   549  	if len(blk.Instrs) > 10 {
   550  		return false // too expensive
   551  	}
   552  	if fn.Synthetic != "" && (fn.Pkg == nil || fn != fn.Pkg.Func("init")) {
   553  		return true // treat synthetic wrappers context-sensitively
   554  	}
   555  	for _, instr := range blk.Instrs {
   556  		switch instr := instr.(type) {
   557  		case ssa.CallInstruction:
   558  			// Disallow function calls (except to built-ins)
   559  			// because of the danger of unbounded recursion.
   560  			if _, ok := instr.Common().Value.(*ssa.Builtin); !ok {
   561  				return false
   562  			}
   563  		}
   564  	}
   565  	return true
   566  }
   567  
   568  // genStaticCall generates constraints for a statically dispatched function call.
   569  func (a *analysis) genStaticCall(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
   570  	fn := call.StaticCallee()
   571  
   572  	// Special cases for inlined intrinsics.
   573  	switch fn {
   574  	case a.runtimeSetFinalizer:
   575  		// Inline SetFinalizer so the call appears direct.
   576  		site.targets = a.addOneNode(tInvalid, "SetFinalizer.targets", nil)
   577  		a.addConstraint(&runtimeSetFinalizerConstraint{
   578  			targets: site.targets,
   579  			x:       a.valueNode(call.Args[0]),
   580  			f:       a.valueNode(call.Args[1]),
   581  		})
   582  		return
   583  
   584  	case a.reflectValueCall:
   585  		// Inline (reflect.Value).Call so the call appears direct.
   586  		dotdotdot := false
   587  		ret := reflectCallImpl(a, caller, site, a.valueNode(call.Args[0]), a.valueNode(call.Args[1]), dotdotdot)
   588  		if result != 0 {
   589  			a.addressOf(fn.Signature.Results().At(0).Type(), result, ret)
   590  		}
   591  		return
   592  	}
   593  
   594  	// Ascertain the context (contour/cgnode) for a particular call.
   595  	var obj nodeid
   596  	if a.shouldUseContext(fn) {
   597  		obj = a.makeFunctionObject(fn, site) // new contour
   598  	} else {
   599  		obj = a.objectNode(nil, fn) // shared contour
   600  	}
   601  	a.callEdge(caller, site, obj)
   602  
   603  	sig := call.Signature()
   604  
   605  	// Copy receiver, if any.
   606  	params := a.funcParams(obj)
   607  	args := call.Args
   608  	if sig.Recv() != nil {
   609  		sz := a.sizeof(sig.Recv().Type())
   610  		a.copy(params, a.valueNode(args[0]), sz)
   611  		params += nodeid(sz)
   612  		args = args[1:]
   613  	}
   614  
   615  	// Copy actual parameters into formal params block.
   616  	// Must loop, since the actuals aren't contiguous.
   617  	for i, arg := range args {
   618  		sz := a.sizeof(sig.Params().At(i).Type())
   619  		a.copy(params, a.valueNode(arg), sz)
   620  		params += nodeid(sz)
   621  	}
   622  
   623  	// Copy formal results block to actual result.
   624  	if result != 0 {
   625  		a.copy(result, a.funcResults(obj), a.sizeof(sig.Results()))
   626  	}
   627  }
   628  
   629  // genDynamicCall generates constraints for a dynamic function call.
   630  func (a *analysis) genDynamicCall(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
   631  	// pts(targets) will be the set of possible call targets.
   632  	site.targets = a.valueNode(call.Value)
   633  
   634  	// We add dynamic closure rules that store the arguments into
   635  	// the P-block and load the results from the R-block of each
   636  	// function discovered in pts(targets).
   637  
   638  	sig := call.Signature()
   639  	var offset uint32 = 1 // P/R block starts at offset 1
   640  	for i, arg := range call.Args {
   641  		sz := a.sizeof(sig.Params().At(i).Type())
   642  		a.genStore(caller, call.Value, a.valueNode(arg), offset, sz)
   643  		offset += sz
   644  	}
   645  	if result != 0 {
   646  		a.genLoad(caller, result, call.Value, offset, a.sizeof(sig.Results()))
   647  	}
   648  }
   649  
   650  // genInvoke generates constraints for a dynamic method invocation.
   651  func (a *analysis) genInvoke(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
   652  	if call.Value.Type() == a.reflectType {
   653  		a.genInvokeReflectType(caller, site, call, result)
   654  		return
   655  	}
   656  
   657  	sig := call.Signature()
   658  
   659  	// Allocate a contiguous targets/params/results block for this call.
   660  	block := a.nextNode()
   661  	// pts(targets) will be the set of possible call targets
   662  	site.targets = a.addOneNode(sig, "invoke.targets", nil)
   663  	p := a.addNodes(sig.Params(), "invoke.params")
   664  	r := a.addNodes(sig.Results(), "invoke.results")
   665  
   666  	// Copy the actual parameters into the call's params block.
   667  	for i, n := 0, sig.Params().Len(); i < n; i++ {
   668  		sz := a.sizeof(sig.Params().At(i).Type())
   669  		a.copy(p, a.valueNode(call.Args[i]), sz)
   670  		p += nodeid(sz)
   671  	}
   672  	// Copy the call's results block to the actual results.
   673  	if result != 0 {
   674  		a.copy(result, r, a.sizeof(sig.Results()))
   675  	}
   676  
   677  	// We add a dynamic invoke constraint that will connect the
   678  	// caller's and the callee's P/R blocks for each discovered
   679  	// call target.
   680  	a.addConstraint(&invokeConstraint{call.Method, a.valueNode(call.Value), block})
   681  }
   682  
   683  // genInvokeReflectType is a specialization of genInvoke where the
   684  // receiver type is a reflect.Type, under the assumption that there
   685  // can be at most one implementation of this interface, *reflect.rtype.
   686  //
   687  // (Though this may appear to be an instance of a pattern---method
   688  // calls on interfaces known to have exactly one implementation---in
   689  // practice it occurs rarely, so we special case for reflect.Type.)
   690  //
   691  // In effect we treat this:
   692  //
   693  //	var rt reflect.Type = ...
   694  //	rt.F()
   695  //
   696  // as this:
   697  //
   698  //	rt.(*reflect.rtype).F()
   699  func (a *analysis) genInvokeReflectType(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
   700  	// Unpack receiver into rtype
   701  	rtype := a.addOneNode(a.reflectRtypePtr, "rtype.recv", nil)
   702  	recv := a.valueNode(call.Value)
   703  	a.typeAssert(a.reflectRtypePtr, rtype, recv, true)
   704  
   705  	// Look up the concrete method.
   706  	fn := a.prog.LookupMethod(a.reflectRtypePtr, call.Method.Pkg(), call.Method.Name())
   707  
   708  	obj := a.makeFunctionObject(fn, site) // new contour for this call
   709  	a.callEdge(caller, site, obj)
   710  
   711  	// From now on, it's essentially a static call, but little is
   712  	// gained by factoring together the code for both cases.
   713  
   714  	sig := fn.Signature // concrete method
   715  	targets := a.addOneNode(sig, "call.targets", nil)
   716  	a.addressOf(sig, targets, obj) // (a singleton)
   717  
   718  	// Copy receiver.
   719  	params := a.funcParams(obj)
   720  	a.copy(params, rtype, 1)
   721  	params++
   722  
   723  	// Copy actual parameters into formal P-block.
   724  	// Must loop, since the actuals aren't contiguous.
   725  	for i, arg := range call.Args {
   726  		sz := a.sizeof(sig.Params().At(i).Type())
   727  		a.copy(params, a.valueNode(arg), sz)
   728  		params += nodeid(sz)
   729  	}
   730  
   731  	// Copy formal R-block to actual R-block.
   732  	if result != 0 {
   733  		a.copy(result, a.funcResults(obj), a.sizeof(sig.Results()))
   734  	}
   735  }
   736  
   737  // genCall generates constraints for call instruction instr.
   738  func (a *analysis) genCall(caller *cgnode, instr ssa.CallInstruction) {
   739  	call := instr.Common()
   740  
   741  	// Intrinsic implementations of built-in functions.
   742  	if _, ok := call.Value.(*ssa.Builtin); ok {
   743  		a.genBuiltinCall(instr, caller)
   744  		return
   745  	}
   746  
   747  	var result nodeid
   748  	if v := instr.Value(); v != nil {
   749  		result = a.valueNode(v)
   750  	}
   751  
   752  	site := &callsite{instr: instr}
   753  	if call.StaticCallee() != nil {
   754  		a.genStaticCall(caller, site, call, result)
   755  	} else if call.IsInvoke() {
   756  		a.genInvoke(caller, site, call, result)
   757  	} else {
   758  		a.genDynamicCall(caller, site, call, result)
   759  	}
   760  
   761  	caller.sites = append(caller.sites, site)
   762  
   763  	if a.log != nil {
   764  		// TODO(adonovan): debug: improve log message.
   765  		fmt.Fprintf(a.log, "\t%s to targets %s from %s\n", site, site.targets, caller)
   766  	}
   767  }
   768  
   769  // objectNode returns the object to which v points, if known.
   770  // In other words, if the points-to set of v is a singleton, it
   771  // returns the sole label, zero otherwise.
   772  //
   773  // We exploit this information to make the generated constraints less
   774  // dynamic.  For example, a complex load constraint can be replaced by
   775  // a simple copy constraint when the sole destination is known a priori.
   776  //
   777  // Some SSA instructions always have singletons points-to sets:
   778  //
   779  //	Alloc, Function, Global, MakeChan, MakeClosure,  MakeInterface,  MakeMap,  MakeSlice.
   780  //
   781  // Others may be singletons depending on their operands:
   782  //
   783  //	FreeVar, Const, Convert, FieldAddr, IndexAddr, Slice, SliceToArrayPointer.
   784  //
   785  // Idempotent.  Objects are created as needed, possibly via recursion
   786  // down the SSA value graph, e.g IndexAddr(FieldAddr(Alloc))).
   787  func (a *analysis) objectNode(cgn *cgnode, v ssa.Value) nodeid {
   788  	switch v.(type) {
   789  	case *ssa.Global, *ssa.Function, *ssa.Const, *ssa.FreeVar:
   790  		// Global object.
   791  		obj, ok := a.globalobj[v]
   792  		if !ok {
   793  			switch v := v.(type) {
   794  			case *ssa.Global:
   795  				obj = a.nextNode()
   796  				a.addNodes(mustDeref(v.Type()), "global")
   797  				a.endObject(obj, nil, v)
   798  
   799  			case *ssa.Function:
   800  				obj = a.makeFunctionObject(v, nil)
   801  
   802  			case *ssa.Const:
   803  				// not addressable
   804  
   805  			case *ssa.FreeVar:
   806  				// not addressable
   807  			}
   808  
   809  			if a.log != nil {
   810  				fmt.Fprintf(a.log, "\tglobalobj[%s] = n%d\n", v, obj)
   811  			}
   812  			a.globalobj[v] = obj
   813  		}
   814  		return obj
   815  	}
   816  
   817  	// Local object.
   818  	obj, ok := a.localobj[v]
   819  	if !ok {
   820  		switch v := v.(type) {
   821  		case *ssa.Alloc:
   822  			obj = a.nextNode()
   823  			a.addNodes(mustDeref(v.Type()), "alloc")
   824  			a.endObject(obj, cgn, v)
   825  
   826  		case *ssa.MakeSlice:
   827  			obj = a.nextNode()
   828  			a.addNodes(sliceToArray(v.Type()), "makeslice")
   829  			a.endObject(obj, cgn, v)
   830  
   831  		case *ssa.MakeChan:
   832  			obj = a.nextNode()
   833  			a.addNodes(v.Type().Underlying().(*types.Chan).Elem(), "makechan")
   834  			a.endObject(obj, cgn, v)
   835  
   836  		case *ssa.MakeMap:
   837  			obj = a.nextNode()
   838  			tmap := v.Type().Underlying().(*types.Map)
   839  			a.addNodes(tmap.Key(), "makemap.key")
   840  			elem := a.addNodes(tmap.Elem(), "makemap.value")
   841  
   842  			// To update the value field, MapUpdate
   843  			// generates store-with-offset constraints which
   844  			// the presolver can't model, so we must mark
   845  			// those nodes indirect.
   846  			for id, end := elem, elem+nodeid(a.sizeof(tmap.Elem())); id < end; id++ {
   847  				a.mapValues = append(a.mapValues, id)
   848  			}
   849  			a.endObject(obj, cgn, v)
   850  
   851  		case *ssa.MakeInterface:
   852  			tConc := v.X.Type()
   853  			obj = a.makeTagged(tConc, cgn, v)
   854  
   855  			// Copy the value into it, if nontrivial.
   856  			if x := a.valueNode(v.X); x != 0 {
   857  				a.copy(obj+1, x, a.sizeof(tConc))
   858  			}
   859  
   860  		case *ssa.FieldAddr:
   861  			if xobj := a.objectNode(cgn, v.X); xobj != 0 {
   862  				obj = xobj + nodeid(a.offsetOf(mustDeref(v.X.Type()), v.Field))
   863  			}
   864  
   865  		case *ssa.IndexAddr:
   866  			if xobj := a.objectNode(cgn, v.X); xobj != 0 {
   867  				obj = xobj + 1
   868  			}
   869  
   870  		case *ssa.Slice:
   871  			obj = a.objectNode(cgn, v.X)
   872  
   873  		case *ssa.SliceToArrayPointer:
   874  			// Going from a []T to a *[k]T for some k.
   875  			// A slice []T is treated as if it were a *T pointer.
   876  			obj = a.objectNode(cgn, v.X)
   877  
   878  		case *ssa.Convert:
   879  			// TODO(adonovan): opt: handle these cases too:
   880  			// - unsafe.Pointer->*T conversion acts like Alloc
   881  			// - string->[]byte/[]rune conversion acts like MakeSlice
   882  		}
   883  
   884  		if a.log != nil {
   885  			fmt.Fprintf(a.log, "\tlocalobj[%s] = n%d\n", v.Name(), obj)
   886  		}
   887  		a.localobj[v] = obj
   888  	}
   889  	return obj
   890  }
   891  
   892  // genLoad generates constraints for result = *(ptr + val).
   893  func (a *analysis) genLoad(cgn *cgnode, result nodeid, ptr ssa.Value, offset, sizeof uint32) {
   894  	if obj := a.objectNode(cgn, ptr); obj != 0 {
   895  		// Pre-apply loadConstraint.solve().
   896  		a.copy(result, obj+nodeid(offset), sizeof)
   897  	} else {
   898  		a.load(result, a.valueNode(ptr), offset, sizeof)
   899  	}
   900  }
   901  
   902  // genOffsetAddr generates constraints for a 'v=ptr.field' (FieldAddr)
   903  // or 'v=ptr[*]' (IndexAddr) instruction v.
   904  func (a *analysis) genOffsetAddr(cgn *cgnode, v ssa.Value, ptr nodeid, offset uint32) {
   905  	dst := a.valueNode(v)
   906  	if obj := a.objectNode(cgn, v); obj != 0 {
   907  		// Pre-apply offsetAddrConstraint.solve().
   908  		a.addressOf(v.Type(), dst, obj)
   909  	} else {
   910  		a.offsetAddr(v.Type(), dst, ptr, offset)
   911  	}
   912  }
   913  
   914  // genStore generates constraints for *(ptr + offset) = val.
   915  func (a *analysis) genStore(cgn *cgnode, ptr ssa.Value, val nodeid, offset, sizeof uint32) {
   916  	if obj := a.objectNode(cgn, ptr); obj != 0 {
   917  		// Pre-apply storeConstraint.solve().
   918  		a.copy(obj+nodeid(offset), val, sizeof)
   919  	} else {
   920  		a.store(a.valueNode(ptr), val, offset, sizeof)
   921  	}
   922  }
   923  
   924  // genInstr generates constraints for instruction instr in context cgn.
   925  func (a *analysis) genInstr(cgn *cgnode, instr ssa.Instruction) {
   926  	if a.log != nil {
   927  		var prefix string
   928  		if val, ok := instr.(ssa.Value); ok {
   929  			prefix = val.Name() + " = "
   930  		}
   931  		fmt.Fprintf(a.log, "; %s%s\n", prefix, instr)
   932  	}
   933  
   934  	switch instr := instr.(type) {
   935  	case *ssa.DebugRef:
   936  		// no-op.
   937  
   938  	case *ssa.UnOp:
   939  		switch instr.Op {
   940  		case token.ARROW: // <-x
   941  			// We can ignore instr.CommaOk because the node we're
   942  			// altering is always at zero offset relative to instr
   943  			tElem := instr.X.Type().Underlying().(*types.Chan).Elem()
   944  			a.genLoad(cgn, a.valueNode(instr), instr.X, 0, a.sizeof(tElem))
   945  
   946  		case token.MUL: // *x
   947  			a.genLoad(cgn, a.valueNode(instr), instr.X, 0, a.sizeof(instr.Type()))
   948  
   949  		default:
   950  			// NOT, SUB, XOR: no-op.
   951  		}
   952  
   953  	case *ssa.BinOp:
   954  		// All no-ops.
   955  
   956  	case ssa.CallInstruction: // *ssa.Call, *ssa.Go, *ssa.Defer
   957  		a.genCall(cgn, instr)
   958  
   959  	case *ssa.ChangeType:
   960  		a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
   961  
   962  	case *ssa.Convert:
   963  		a.genConv(instr, cgn)
   964  
   965  	case *ssa.Extract:
   966  		a.copy(a.valueNode(instr),
   967  			a.valueOffsetNode(instr.Tuple, instr.Index),
   968  			a.sizeof(instr.Type()))
   969  
   970  	case *ssa.FieldAddr:
   971  		a.genOffsetAddr(cgn, instr, a.valueNode(instr.X),
   972  			a.offsetOf(mustDeref(instr.X.Type()), instr.Field))
   973  
   974  	case *ssa.IndexAddr:
   975  		a.genOffsetAddr(cgn, instr, a.valueNode(instr.X), 1)
   976  
   977  	case *ssa.Field:
   978  		a.copy(a.valueNode(instr),
   979  			a.valueOffsetNode(instr.X, instr.Field),
   980  			a.sizeof(instr.Type()))
   981  
   982  	case *ssa.Index:
   983  		_, isstring := typeparams.CoreType(instr.X.Type()).(*types.Basic)
   984  		if !isstring {
   985  			a.copy(a.valueNode(instr), 1+a.valueNode(instr.X), a.sizeof(instr.Type()))
   986  		}
   987  
   988  	case *ssa.Select:
   989  		recv := a.valueOffsetNode(instr, 2) // instr : (index, recvOk, recv0, ... recv_n-1)
   990  		for _, st := range instr.States {
   991  			elemSize := a.sizeof(st.Chan.Type().Underlying().(*types.Chan).Elem())
   992  			switch st.Dir {
   993  			case types.RecvOnly:
   994  				a.genLoad(cgn, recv, st.Chan, 0, elemSize)
   995  				recv += nodeid(elemSize)
   996  
   997  			case types.SendOnly:
   998  				a.genStore(cgn, st.Chan, a.valueNode(st.Send), 0, elemSize)
   999  			}
  1000  		}
  1001  
  1002  	case *ssa.Return:
  1003  		results := a.funcResults(cgn.obj)
  1004  		for _, r := range instr.Results {
  1005  			sz := a.sizeof(r.Type())
  1006  			a.copy(results, a.valueNode(r), sz)
  1007  			results += nodeid(sz)
  1008  		}
  1009  
  1010  	case *ssa.Send:
  1011  		a.genStore(cgn, instr.Chan, a.valueNode(instr.X), 0, a.sizeof(instr.X.Type()))
  1012  
  1013  	case *ssa.Store:
  1014  		a.genStore(cgn, instr.Addr, a.valueNode(instr.Val), 0, a.sizeof(instr.Val.Type()))
  1015  
  1016  	case *ssa.Alloc, *ssa.MakeSlice, *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeInterface:
  1017  		v := instr.(ssa.Value)
  1018  		a.addressOf(v.Type(), a.valueNode(v), a.objectNode(cgn, v))
  1019  
  1020  	case *ssa.ChangeInterface:
  1021  		a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
  1022  
  1023  	case *ssa.TypeAssert:
  1024  		a.typeAssert(instr.AssertedType, a.valueNode(instr), a.valueNode(instr.X), true)
  1025  
  1026  	case *ssa.Slice:
  1027  		a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
  1028  
  1029  	case *ssa.SliceToArrayPointer:
  1030  		// Going from a []T to a *[k]T (for some k) is a single `dst = src` constraint.
  1031  		// Both []T and *[k]T are modelled as an *IdArrayT where IdArrayT is the identity
  1032  		// node for an array of type T, i.e `type IdArrayT struct{elem T}`.
  1033  		a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
  1034  
  1035  	case *ssa.If, *ssa.Jump:
  1036  		// no-op.
  1037  
  1038  	case *ssa.Phi:
  1039  		sz := a.sizeof(instr.Type())
  1040  		for _, e := range instr.Edges {
  1041  			a.copy(a.valueNode(instr), a.valueNode(e), sz)
  1042  		}
  1043  
  1044  	case *ssa.MakeClosure:
  1045  		fn := instr.Fn.(*ssa.Function)
  1046  		a.copy(a.valueNode(instr), a.valueNode(fn), 1)
  1047  		// Free variables are treated like global variables.
  1048  		for i, b := range instr.Bindings {
  1049  			a.copy(a.valueNode(fn.FreeVars[i]), a.valueNode(b), a.sizeof(b.Type()))
  1050  		}
  1051  
  1052  	case *ssa.RunDefers:
  1053  		// The analysis is flow insensitive, so we just "call"
  1054  		// defers as we encounter them.
  1055  
  1056  	case *ssa.Range:
  1057  		// Do nothing.  Next{Iter: *ssa.Range} handles this case.
  1058  
  1059  	case *ssa.Next:
  1060  		if !instr.IsString {
  1061  			// Assumes that Next is always directly applied to a Range result
  1062  			// for a map.
  1063  
  1064  			// Next results in a destination tuple (ok, dk, dv).
  1065  			// Recall a map is modeled as type *M where M = struct{sk K; sv V}.
  1066  			// Next copies from a src map struct{sk K; sv V} to a dst tuple (ok, dk, dv)
  1067  			//
  1068  			// When keys or value is a blank identifier in a range statement, e.g
  1069  			//   for _, v := range m { ... }
  1070  			// or
  1071  			//   for _, _ = range m { ... }
  1072  			// we skip copying from sk or dk as there is no use. dk and dv will have
  1073  			// Invalid types if they are blank identifiers. This means that the
  1074  			//   size( (ok, dk, dv) )  may differ from 1 + size(struct{sk K; sv V}).
  1075  			//
  1076  			// We encode Next using one load of size sz from an offset in src osrc to an
  1077  			// offset in dst odst. There are 4 cases to consider:
  1078  			//           odst       | osrc     | sz
  1079  			//   k, v  | 1          | 0        | size(sk) + size(sv)
  1080  			//   k, _  | 1          | 0        | size(sk)
  1081  			//   _, v  | 1+size(dk) | size(sk) | size(sv)
  1082  			//   _, _  | 1+size(dk) | size(sk) | 0
  1083  
  1084  			// get the source key and value size.  Note the source types
  1085  			// may be different than the 3-tuple types, but if this is the
  1086  			// case then the source is assignable to the destination.
  1087  			theMap := instr.Iter.(*ssa.Range).X
  1088  			tMap := theMap.Type().Underlying().(*types.Map)
  1089  
  1090  			sksize := a.sizeof(tMap.Key())
  1091  			svsize := a.sizeof(tMap.Elem())
  1092  
  1093  			// get the key size of the destination tuple.
  1094  			tTuple := instr.Type().(*types.Tuple)
  1095  			dksize := a.sizeof(tTuple.At(1).Type())
  1096  
  1097  			// Load from the map's (k,v) into the tuple's (ok, k, v).
  1098  			osrc := uint32(0) // offset within map object
  1099  			odst := uint32(1) // offset within tuple (initially just after 'ok bool')
  1100  			sz := uint32(0)   // amount to copy
  1101  
  1102  			// Is key valid?
  1103  			if tTuple.At(1).Type() != tInvalid {
  1104  				sz += sksize
  1105  			} else {
  1106  				odst += dksize
  1107  				osrc += sksize
  1108  			}
  1109  
  1110  			// Is value valid?
  1111  			if tTuple.At(2).Type() != tInvalid {
  1112  				sz += svsize
  1113  			}
  1114  
  1115  			a.genLoad(cgn, a.valueNode(instr)+nodeid(odst), theMap, osrc, sz)
  1116  		}
  1117  
  1118  	case *ssa.Lookup:
  1119  		if tMap, ok := instr.X.Type().Underlying().(*types.Map); ok {
  1120  			// CommaOk can be ignored: field 0 is a no-op.
  1121  			ksize := a.sizeof(tMap.Key())
  1122  			vsize := a.sizeof(tMap.Elem())
  1123  			a.genLoad(cgn, a.valueNode(instr), instr.X, ksize, vsize)
  1124  		}
  1125  
  1126  	case *ssa.MapUpdate:
  1127  		tmap := instr.Map.Type().Underlying().(*types.Map)
  1128  		ksize := a.sizeof(tmap.Key())
  1129  		vsize := a.sizeof(tmap.Elem())
  1130  		a.genStore(cgn, instr.Map, a.valueNode(instr.Key), 0, ksize)
  1131  		a.genStore(cgn, instr.Map, a.valueNode(instr.Value), ksize, vsize)
  1132  
  1133  	case *ssa.Panic:
  1134  		a.copy(a.panicNode, a.valueNode(instr.X), 1)
  1135  
  1136  	default:
  1137  		panic(fmt.Sprintf("unimplemented: %T", instr))
  1138  	}
  1139  }
  1140  
  1141  func (a *analysis) makeCGNode(fn *ssa.Function, obj nodeid, callersite *callsite) *cgnode {
  1142  	cgn := &cgnode{fn: fn, obj: obj, callersite: callersite}
  1143  	a.cgnodes = append(a.cgnodes, cgn)
  1144  	return cgn
  1145  }
  1146  
  1147  // genRootCalls generates the synthetic root of the callgraph and the
  1148  // initial calls from it to the analysis scope, such as main, a test
  1149  // or a library.
  1150  func (a *analysis) genRootCalls() *cgnode {
  1151  	r := a.prog.NewFunction("<root>", new(types.Signature), "root of callgraph")
  1152  	root := a.makeCGNode(r, 0, nil)
  1153  
  1154  	// TODO(adonovan): make an ssa utility to construct an actual
  1155  	// root function so we don't need to special-case site-less
  1156  	// call edges.
  1157  
  1158  	// For each main package, call main.init(), main.main().
  1159  	for _, mainPkg := range a.config.Mains {
  1160  		main := mainPkg.Func("main")
  1161  		if main == nil {
  1162  			panic(fmt.Sprintf("%s has no main function", mainPkg))
  1163  		}
  1164  
  1165  		targets := a.addOneNode(main.Signature, "root.targets", nil)
  1166  		site := &callsite{targets: targets}
  1167  		root.sites = append(root.sites, site)
  1168  		for _, fn := range [2]*ssa.Function{mainPkg.Func("init"), main} {
  1169  			if a.log != nil {
  1170  				fmt.Fprintf(a.log, "\troot call to %s:\n", fn)
  1171  			}
  1172  			a.copy(targets, a.valueNode(fn), 1)
  1173  		}
  1174  	}
  1175  
  1176  	return root
  1177  }
  1178  
  1179  // genFunc generates constraints for function fn.
  1180  func (a *analysis) genFunc(cgn *cgnode) {
  1181  	fn := cgn.fn
  1182  
  1183  	impl := a.findIntrinsic(fn)
  1184  
  1185  	if a.log != nil {
  1186  		fmt.Fprintf(a.log, "\n\n==== Generating constraints for %s, %s\n", cgn, cgn.contour())
  1187  
  1188  		// Hack: don't display body if intrinsic.
  1189  		if impl != nil {
  1190  			fn2 := *cgn.fn // copy
  1191  			fn2.Locals = nil
  1192  			fn2.Blocks = nil
  1193  			fn2.WriteTo(a.log)
  1194  		} else {
  1195  			cgn.fn.WriteTo(a.log)
  1196  		}
  1197  	}
  1198  
  1199  	if impl != nil {
  1200  		impl(a, cgn)
  1201  		return
  1202  	}
  1203  
  1204  	if fn.Blocks == nil {
  1205  		// External function with no intrinsic treatment.
  1206  		// We'll warn about calls to such functions at the end.
  1207  		return
  1208  	}
  1209  
  1210  	if fn.TypeParams().Len() > 0 && len(fn.TypeArgs()) == 0 {
  1211  		// Body of generic function.
  1212  		// We'll warn about calls to such functions at the end.
  1213  		return
  1214  	}
  1215  
  1216  	if strings.HasPrefix(fn.Synthetic, "instantiation wrapper ") {
  1217  		// instantiation wrapper of a generic function.
  1218  		// These may contain type coercions which are not currently supported.
  1219  		// We'll warn about calls to such functions at the end.
  1220  		return
  1221  	}
  1222  
  1223  	if a.log != nil {
  1224  		fmt.Fprintln(a.log, "; Creating nodes for local values")
  1225  	}
  1226  
  1227  	a.localval = make(map[ssa.Value]nodeid)
  1228  	a.localobj = make(map[ssa.Value]nodeid)
  1229  
  1230  	// The value nodes for the params are in the func object block.
  1231  	params := a.funcParams(cgn.obj)
  1232  	for _, p := range fn.Params {
  1233  		a.setValueNode(p, params, cgn)
  1234  		params += nodeid(a.sizeof(p.Type()))
  1235  	}
  1236  
  1237  	// Free variables have global cardinality:
  1238  	// the outer function sets them with MakeClosure;
  1239  	// the inner function accesses them with FreeVar.
  1240  	//
  1241  	// TODO(adonovan): treat free vars context-sensitively.
  1242  
  1243  	// Create value nodes for all value instructions
  1244  	// since SSA may contain forward references.
  1245  	var space [10]*ssa.Value
  1246  	for _, b := range fn.Blocks {
  1247  		for _, instr := range b.Instrs {
  1248  			switch instr := instr.(type) {
  1249  			case *ssa.Range:
  1250  				// do nothing: it has a funky type,
  1251  				// and *ssa.Next does all the work.
  1252  
  1253  			case ssa.Value:
  1254  				var comment string
  1255  				if a.log != nil {
  1256  					comment = instr.Name()
  1257  				}
  1258  				id := a.addNodes(instr.Type(), comment)
  1259  				a.setValueNode(instr, id, cgn)
  1260  			}
  1261  
  1262  			// Record all address-taken functions (for presolver).
  1263  			rands := instr.Operands(space[:0])
  1264  			if call, ok := instr.(ssa.CallInstruction); ok && !call.Common().IsInvoke() {
  1265  				// Skip CallCommon.Value in "call" mode.
  1266  				// TODO(adonovan): fix: relies on unspecified ordering.  Specify it.
  1267  				rands = rands[1:]
  1268  			}
  1269  			for _, rand := range rands {
  1270  				if atf, ok := (*rand).(*ssa.Function); ok {
  1271  					a.atFuncs[atf] = true
  1272  				}
  1273  			}
  1274  		}
  1275  	}
  1276  
  1277  	// Generate constraints for instructions.
  1278  	for _, b := range fn.Blocks {
  1279  		for _, instr := range b.Instrs {
  1280  			a.genInstr(cgn, instr)
  1281  		}
  1282  	}
  1283  
  1284  	a.localval = nil
  1285  	a.localobj = nil
  1286  }
  1287  
  1288  // genMethodsOf generates nodes and constraints for all methods of type T.
  1289  func (a *analysis) genMethodsOf(T types.Type) {
  1290  	itf := isInterface(T)
  1291  
  1292  	// TODO(adonovan): can we skip this entirely if itf is true?
  1293  	// I think so, but the answer may depend on reflection.
  1294  	mset := a.prog.MethodSets.MethodSet(T)
  1295  	for i, n := 0, mset.Len(); i < n; i++ {
  1296  		m := a.prog.MethodValue(mset.At(i))
  1297  		a.valueNode(m)
  1298  
  1299  		if !itf {
  1300  			// Methods of concrete types are address-taken functions.
  1301  			a.atFuncs[m] = true
  1302  		}
  1303  	}
  1304  }
  1305  
  1306  // generate generates offline constraints for the entire program.
  1307  func (a *analysis) generate() {
  1308  	start("Constraint generation")
  1309  	if a.log != nil {
  1310  		fmt.Fprintln(a.log, "==== Generating constraints")
  1311  	}
  1312  
  1313  	// Create a dummy node since we use the nodeid 0 for
  1314  	// non-pointerlike variables.
  1315  	a.addNodes(tInvalid, "(zero)")
  1316  
  1317  	// Create the global node for panic values.
  1318  	a.panicNode = a.addNodes(tEface, "panic")
  1319  
  1320  	// Create nodes and constraints for all methods of reflect.rtype.
  1321  	// (Shared contours are used by dynamic calls to reflect.Type
  1322  	// methods---typically just String().)
  1323  	if rtype := a.reflectRtypePtr; rtype != nil {
  1324  		a.genMethodsOf(rtype)
  1325  	}
  1326  
  1327  	root := a.genRootCalls()
  1328  
  1329  	if a.config.BuildCallGraph {
  1330  		a.result.CallGraph = callgraph.New(root.fn)
  1331  	}
  1332  
  1333  	// Create nodes and constraints for all methods of all types
  1334  	// that are dynamically accessible via reflection or interfaces.
  1335  	for _, T := range a.prog.RuntimeTypes() {
  1336  		a.genMethodsOf(T)
  1337  	}
  1338  
  1339  	// Generate constraints for functions as they become reachable
  1340  	// from the roots.  (No constraints are generated for functions
  1341  	// that are dead in this analysis scope.)
  1342  	for len(a.genq) > 0 {
  1343  		cgn := a.genq[0]
  1344  		a.genq = a.genq[1:]
  1345  		a.genFunc(cgn)
  1346  	}
  1347  
  1348  	// The runtime magically allocates os.Args; so should we.
  1349  	if os := a.prog.ImportedPackage("os"); os != nil {
  1350  		// In effect:  os.Args = new([1]string)[:]
  1351  		T := types.NewSlice(types.Typ[types.String])
  1352  		obj := a.addNodes(sliceToArray(T), "<command-line args>")
  1353  		a.endObject(obj, nil, "<command-line args>")
  1354  		a.addressOf(T, a.objectNode(nil, os.Var("Args")), obj)
  1355  	}
  1356  
  1357  	// Discard generation state, to avoid confusion after node renumbering.
  1358  	a.panicNode = 0
  1359  	a.globalval = nil
  1360  	a.localval = nil
  1361  	a.localobj = nil
  1362  
  1363  	stop("Constraint generation")
  1364  }
  1365
View as plain text