.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/gen.go

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