src/cmd/compile/internal/reflectdata/reflect.go

   1 // Copyright 2009 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 reflectdata
   6
   7 import (
   8         "encoding/binary"
   9         "fmt"
  10         "internal/buildcfg"
  11         "os"
  12         "sort"
  13         "strings"
  14         "sync"
  15
  16         "cmd/compile/internal/base"
  17         "cmd/compile/internal/bitvec"
  18         "cmd/compile/internal/escape"
  19         "cmd/compile/internal/inline"
  20         "cmd/compile/internal/ir"
  21         "cmd/compile/internal/objw"
  22         "cmd/compile/internal/typebits"
  23         "cmd/compile/internal/typecheck"
  24         "cmd/compile/internal/types"
  25         "cmd/internal/gcprog"
  26         "cmd/internal/obj"
  27         "cmd/internal/objabi"
  28         "cmd/internal/src"
  29 )
  30
  31 type ptabEntry struct {
  32         s *types.Sym
  33         t *types.Type
  34 }
  35
  36 func CountPTabs() int {
  37         return len(ptabs)
  38 }
  39
  40 // runtime interface and reflection data structures
  41 var (
  42         signatmu    sync.Mutex // protects signatset and signatslice
  43         signatset   = make(map[*types.Type]struct{})
  44         signatslice []*types.Type
  45
  46         gcsymmu  sync.Mutex // protects gcsymset and gcsymslice
  47         gcsymset = make(map[*types.Type]struct{})
  48
  49         ptabs []*ir.Name
  50 )
  51
  52 type typeSig struct {
  53         name  *types.Sym
  54         isym  *obj.LSym
  55         tsym  *obj.LSym
  56         type_ *types.Type
  57         mtype *types.Type
  58 }
  59
  60 // Builds a type representing a Bucket structure for
  61 // the given map type. This type is not visible to users -
  62 // we include only enough information to generate a correct GC
  63 // program for it.
  64 // Make sure this stays in sync with runtime/map.go.
  65 const (
  66         BUCKETSIZE  = 8
  67         MAXKEYSIZE  = 128
  68         MAXELEMSIZE = 128
  69 )
  70
  71 func structfieldSize() int { return 3 * types.PtrSize }       // Sizeof(runtime.structfield{})
  72 func imethodSize() int     { return 4 + 4 }                   // Sizeof(runtime.imethod{})
  73 func commonSize() int      { return 4*types.PtrSize + 8 + 8 } // Sizeof(runtime._type{})
  74
  75 func uncommonSize(t *types.Type) int { // Sizeof(runtime.uncommontype{})
  76         if t.Sym() == nil && len(methods(t)) == 0 {
  77                 return 0
  78         }
  79         return 4 + 2 + 2 + 4 + 4
  80 }
  81
  82 func makefield(name string, t *types.Type) *types.Field {
  83         sym := (*types.Pkg)(nil).Lookup(name)
  84         return types.NewField(src.NoXPos, sym, t)
  85 }
  86
  87 // MapBucketType makes the map bucket type given the type of the map.
  88 func MapBucketType(t *types.Type) *types.Type {
  89         if t.MapType().Bucket != nil {
  90                 return t.MapType().Bucket
  91         }
  92
  93         keytype := t.Key()
  94         elemtype := t.Elem()
  95         types.CalcSize(keytype)
  96         types.CalcSize(elemtype)
  97         if keytype.Width > MAXKEYSIZE {
  98                 keytype = types.NewPtr(keytype)
  99         }
 100         if elemtype.Width > MAXELEMSIZE {
 101                 elemtype = types.NewPtr(elemtype)
 102         }
 103
 104         field := make([]*types.Field, 0, 5)
 105
 106         // The first field is: uint8 topbits[BUCKETSIZE].
 107         arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
 108         field = append(field, makefield("topbits", arr))
 109
 110         arr = types.NewArray(keytype, BUCKETSIZE)
 111         arr.SetNoalg(true)
 112         keys := makefield("keys", arr)
 113         field = append(field, keys)
 114
 115         arr = types.NewArray(elemtype, BUCKETSIZE)
 116         arr.SetNoalg(true)
 117         elems := makefield("elems", arr)
 118         field = append(field, elems)
 119
 120         // If keys and elems have no pointers, the map implementation
 121         // can keep a list of overflow pointers on the side so that
 122         // buckets can be marked as having no pointers.
 123         // Arrange for the bucket to have no pointers by changing
 124         // the type of the overflow field to uintptr in this case.
 125         // See comment on hmap.overflow in runtime/map.go.
 126         otyp := types.Types[types.TUNSAFEPTR]
 127         if !elemtype.HasPointers() && !keytype.HasPointers() {
 128                 otyp = types.Types[types.TUINTPTR]
 129         }
 130         overflow := makefield("overflow", otyp)
 131         field = append(field, overflow)
 132
 133         // link up fields
 134         bucket := types.NewStruct(types.NoPkg, field[:])
 135         bucket.SetNoalg(true)
 136         types.CalcSize(bucket)
 137
 138         // Check invariants that map code depends on.
 139         if !types.IsComparable(t.Key()) {
 140                 base.Fatalf("unsupported map key type for %v", t)
 141         }
 142         if BUCKETSIZE < 8 {
 143                 base.Fatalf("bucket size too small for proper alignment")
 144         }
 145         if keytype.Align > BUCKETSIZE {
 146                 base.Fatalf("key align too big for %v", t)
 147         }
 148         if elemtype.Align > BUCKETSIZE {
 149                 base.Fatalf("elem align too big for %v", t)
 150         }
 151         if keytype.Width > MAXKEYSIZE {
 152                 base.Fatalf("key size to large for %v", t)
 153         }
 154         if elemtype.Width > MAXELEMSIZE {
 155                 base.Fatalf("elem size to large for %v", t)
 156         }
 157         if t.Key().Width > MAXKEYSIZE && !keytype.IsPtr() {
 158                 base.Fatalf("key indirect incorrect for %v", t)
 159         }
 160         if t.Elem().Width > MAXELEMSIZE && !elemtype.IsPtr() {
 161                 base.Fatalf("elem indirect incorrect for %v", t)
 162         }
 163         if keytype.Width%int64(keytype.Align) != 0 {
 164                 base.Fatalf("key size not a multiple of key align for %v", t)
 165         }
 166         if elemtype.Width%int64(elemtype.Align) != 0 {
 167                 base.Fatalf("elem size not a multiple of elem align for %v", t)
 168         }
 169         if bucket.Align%keytype.Align != 0 {
 170                 base.Fatalf("bucket align not multiple of key align %v", t)
 171         }
 172         if bucket.Align%elemtype.Align != 0 {
 173                 base.Fatalf("bucket align not multiple of elem align %v", t)
 174         }
 175         if keys.Offset%int64(keytype.Align) != 0 {
 176                 base.Fatalf("bad alignment of keys in bmap for %v", t)
 177         }
 178         if elems.Offset%int64(elemtype.Align) != 0 {
 179                 base.Fatalf("bad alignment of elems in bmap for %v", t)
 180         }
 181
 182         // Double-check that overflow field is final memory in struct,
 183         // with no padding at end.
 184         if overflow.Offset != bucket.Width-int64(types.PtrSize) {
 185                 base.Fatalf("bad offset of overflow in bmap for %v", t)
 186         }
 187
 188         t.MapType().Bucket = bucket
 189
 190         bucket.StructType().Map = t
 191         return bucket
 192 }
 193
 194 // MapType builds a type representing a Hmap structure for the given map type.
 195 // Make sure this stays in sync with runtime/map.go.
 196 func MapType(t *types.Type) *types.Type {
 197         if t.MapType().Hmap != nil {
 198                 return t.MapType().Hmap
 199         }
 200
 201         bmap := MapBucketType(t)
 202
 203         // build a struct:
 204         // type hmap struct {
 205         //    count      int
 206         //    flags      uint8
 207         //    B          uint8
 208         //    noverflow  uint16
 209         //    hash0      uint32
 210         //    buckets    *bmap
 211         //    oldbuckets *bmap
 212         //    nevacuate  uintptr
 213         //    extra      unsafe.Pointer // *mapextra
 214         // }
 215         // must match runtime/map.go:hmap.
 216         fields := []*types.Field{
 217                 makefield("count", types.Types[types.TINT]),
 218                 makefield("flags", types.Types[types.TUINT8]),
 219                 makefield("B", types.Types[types.TUINT8]),
 220                 makefield("noverflow", types.Types[types.TUINT16]),
 221                 makefield("hash0", types.Types[types.TUINT32]), // Used in walk.go for OMAKEMAP.
 222                 makefield("buckets", types.NewPtr(bmap)),       // Used in walk.go for OMAKEMAP.
 223                 makefield("oldbuckets", types.NewPtr(bmap)),
 224                 makefield("nevacuate", types.Types[types.TUINTPTR]),
 225                 makefield("extra", types.Types[types.TUNSAFEPTR]),
 226         }
 227
 228         hmap := types.NewStruct(types.NoPkg, fields)
 229         hmap.SetNoalg(true)
 230         types.CalcSize(hmap)
 231
 232         // The size of hmap should be 48 bytes on 64 bit
 233         // and 28 bytes on 32 bit platforms.
 234         if size := int64(8 + 5*types.PtrSize); hmap.Width != size {
 235                 base.Fatalf("hmap size not correct: got %d, want %d", hmap.Width, size)
 236         }
 237
 238         t.MapType().Hmap = hmap
 239         hmap.StructType().Map = t
 240         return hmap
 241 }
 242
 243 // MapIterType builds a type representing an Hiter structure for the given map type.
 244 // Make sure this stays in sync with runtime/map.go.
 245 func MapIterType(t *types.Type) *types.Type {
 246         if t.MapType().Hiter != nil {
 247                 return t.MapType().Hiter
 248         }
 249
 250         hmap := MapType(t)
 251         bmap := MapBucketType(t)
 252
 253         // build a struct:
 254         // type hiter struct {
 255         //    key         *Key
 256         //    elem        *Elem
 257         //    t           unsafe.Pointer // *MapType
 258         //    h           *hmap
 259         //    buckets     *bmap
 260         //    bptr        *bmap
 261         //    overflow    unsafe.Pointer // *[]*bmap
 262         //    oldoverflow unsafe.Pointer // *[]*bmap
 263         //    startBucket uintptr
 264         //    offset      uint8
 265         //    wrapped     bool
 266         //    B           uint8
 267         //    i           uint8
 268         //    bucket      uintptr
 269         //    checkBucket uintptr
 270         // }
 271         // must match runtime/map.go:hiter.
 272         fields := []*types.Field{
 273                 makefield("key", types.NewPtr(t.Key())),   // Used in range.go for TMAP.
 274                 makefield("elem", types.NewPtr(t.Elem())), // Used in range.go for TMAP.
 275                 makefield("t", types.Types[types.TUNSAFEPTR]),
 276                 makefield("h", types.NewPtr(hmap)),
 277                 makefield("buckets", types.NewPtr(bmap)),
 278                 makefield("bptr", types.NewPtr(bmap)),
 279                 makefield("overflow", types.Types[types.TUNSAFEPTR]),
 280                 makefield("oldoverflow", types.Types[types.TUNSAFEPTR]),
 281                 makefield("startBucket", types.Types[types.TUINTPTR]),
 282                 makefield("offset", types.Types[types.TUINT8]),
 283                 makefield("wrapped", types.Types[types.TBOOL]),
 284                 makefield("B", types.Types[types.TUINT8]),
 285                 makefield("i", types.Types[types.TUINT8]),
 286                 makefield("bucket", types.Types[types.TUINTPTR]),
 287                 makefield("checkBucket", types.Types[types.TUINTPTR]),
 288         }
 289
 290         // build iterator struct holding the above fields
 291         hiter := types.NewStruct(types.NoPkg, fields)
 292         hiter.SetNoalg(true)
 293         types.CalcSize(hiter)
 294         if hiter.Width != int64(12*types.PtrSize) {
 295                 base.Fatalf("hash_iter size not correct %d %d", hiter.Width, 12*types.PtrSize)
 296         }
 297         t.MapType().Hiter = hiter
 298         hiter.StructType().Map = t
 299         return hiter
 300 }
 301
 302 // methods returns the methods of the non-interface type t, sorted by name.
 303 // Generates stub functions as needed.
 304 func methods(t *types.Type) []*typeSig {
 305         if t.HasShape() {
 306                 // Shape types have no methods.
 307                 return nil
 308         }
 309         // method type
 310         mt := types.ReceiverBaseType(t)
 311
 312         if mt == nil {
 313                 return nil
 314         }
 315         typecheck.CalcMethods(mt)
 316
 317         // make list of methods for t,
 318         // generating code if necessary.
 319         var ms []*typeSig
 320         for _, f := range mt.AllMethods().Slice() {
 321                 if f.Sym == nil {
 322                         base.Fatalf("method with no sym on %v", mt)
 323                 }
 324                 if !f.IsMethod() {
 325                         base.Fatalf("non-method on %v method %v %v", mt, f.Sym, f)
 326                 }
 327                 if f.Type.Recv() == nil {
 328                         base.Fatalf("receiver with no type on %v method %v %v", mt, f.Sym, f)
 329                 }
 330                 if f.Nointerface() {
 331                         continue
 332                 }
 333
 334                 // get receiver type for this particular method.
 335                 // if pointer receiver but non-pointer t and
 336                 // this is not an embedded pointer inside a struct,
 337                 // method does not apply.
 338                 if !types.IsMethodApplicable(t, f) {
 339                         continue
 340                 }
 341
 342                 sig := &typeSig{
 343                         name:  f.Sym,
 344                         isym:  methodWrapper(t, f, true),
 345                         tsym:  methodWrapper(t, f, false),
 346                         type_: typecheck.NewMethodType(f.Type, t),
 347                         mtype: typecheck.NewMethodType(f.Type, nil),
 348                 }
 349                 ms = append(ms, sig)
 350         }
 351
 352         return ms
 353 }
 354
 355 // imethods returns the methods of the interface type t, sorted by name.
 356 func imethods(t *types.Type) []*typeSig {
 357         var methods []*typeSig
 358         for _, f := range t.AllMethods().Slice() {
 359                 if f.Type.Kind() != types.TFUNC || f.Sym == nil {
 360                         continue
 361                 }
 362                 if f.Sym.IsBlank() {
 363                         base.Fatalf("unexpected blank symbol in interface method set")
 364                 }
 365                 if n := len(methods); n > 0 {
 366                         last := methods[n-1]
 367                         if !last.name.Less(f.Sym) {
 368                                 base.Fatalf("sigcmp vs sortinter %v %v", last.name, f.Sym)
 369                         }
 370                 }
 371
 372                 sig := &typeSig{
 373                         name:  f.Sym,
 374                         mtype: f.Type,
 375                         type_: typecheck.NewMethodType(f.Type, nil),
 376                 }
 377                 methods = append(methods, sig)
 378
 379                 // NOTE(rsc): Perhaps an oversight that
 380                 // IfaceType.Method is not in the reflect data.
 381                 // Generate the method body, so that compiled
 382                 // code can refer to it.
 383                 methodWrapper(t, f, false)
 384         }
 385
 386         return methods
 387 }
 388
 389 func dimportpath(p *types.Pkg) {
 390         if p.Pathsym != nil {
 391                 return
 392         }
 393
 394         // If we are compiling the runtime package, there are two runtime packages around
 395         // -- localpkg and Pkgs.Runtime. We don't want to produce import path symbols for
 396         // both of them, so just produce one for localpkg.
 397         if base.Ctxt.Pkgpath == "runtime" && p == ir.Pkgs.Runtime {
 398                 return
 399         }
 400
 401         str := p.Path
 402         if p == types.LocalPkg {
 403                 // Note: myimportpath != "", or else dgopkgpath won't call dimportpath.
 404                 str = base.Ctxt.Pkgpath
 405         }
 406
 407         s := base.Ctxt.Lookup("type..importpath." + p.Prefix + ".")
 408         ot := dnameData(s, 0, str, "", nil, false)
 409         objw.Global(s, int32(ot), obj.DUPOK|obj.RODATA)
 410         s.Set(obj.AttrContentAddressable, true)
 411         p.Pathsym = s
 412 }
 413
 414 func dgopkgpath(s *obj.LSym, ot int, pkg *types.Pkg) int {
 415         if pkg == nil {
 416                 return objw.Uintptr(s, ot, 0)
 417         }
 418
 419         if pkg == types.LocalPkg && base.Ctxt.Pkgpath == "" {
 420                 // If we don't know the full import path of the package being compiled
 421                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 422                 // type..importpath.""., which the linker will rewrite using the correct import path.
 423                 // Every package that imports this one directly defines the symbol.
 424                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 425                 ns := base.Ctxt.Lookup(`type..importpath."".`)
 426                 return objw.SymPtr(s, ot, ns, 0)
 427         }
 428
 429         dimportpath(pkg)
 430         return objw.SymPtr(s, ot, pkg.Pathsym, 0)
 431 }
 432
 433 // dgopkgpathOff writes an offset relocation in s at offset ot to the pkg path symbol.
 434 func dgopkgpathOff(s *obj.LSym, ot int, pkg *types.Pkg) int {
 435         if pkg == nil {
 436                 return objw.Uint32(s, ot, 0)
 437         }
 438         if pkg == types.LocalPkg && base.Ctxt.Pkgpath == "" {
 439                 // If we don't know the full import path of the package being compiled
 440                 // (i.e. -p was not passed on the compiler command line), emit a reference to
 441                 // type..importpath.""., which the linker will rewrite using the correct import path.
 442                 // Every package that imports this one directly defines the symbol.
 443                 // See also https://groups.google.com/forum/#!topic/golang-dev/myb9s53HxGQ.
 444                 ns := base.Ctxt.Lookup(`type..importpath."".`)
 445                 return objw.SymPtrOff(s, ot, ns)
 446         }
 447
 448         dimportpath(pkg)
 449         return objw.SymPtrOff(s, ot, pkg.Pathsym)
 450 }
 451
 452 // dnameField dumps a reflect.name for a struct field.
 453 func dnameField(lsym *obj.LSym, ot int, spkg *types.Pkg, ft *types.Field) int {
 454         if !types.IsExported(ft.Sym.Name) && ft.Sym.Pkg != spkg {
 455                 base.Fatalf("package mismatch for %v", ft.Sym)
 456         }
 457         nsym := dname(ft.Sym.Name, ft.Note, nil, types.IsExported(ft.Sym.Name))
 458         return objw.SymPtr(lsym, ot, nsym, 0)
 459 }
 460
 461 // dnameData writes the contents of a reflect.name into s at offset ot.
 462 func dnameData(s *obj.LSym, ot int, name, tag string, pkg *types.Pkg, exported bool) int {
 463         if len(name) >= 1<<29 {
 464                 base.Fatalf("name too long: %d %s...", len(name), name[:1024])
 465         }
 466         if len(tag) >= 1<<29 {
 467                 base.Fatalf("tag too long: %d %s...", len(tag), tag[:1024])
 468         }
 469         var nameLen [binary.MaxVarintLen64]byte
 470         nameLenLen := binary.PutUvarint(nameLen[:], uint64(len(name)))
 471         var tagLen [binary.MaxVarintLen64]byte
 472         tagLenLen := binary.PutUvarint(tagLen[:], uint64(len(tag)))
 473
 474         // Encode name and tag. See reflect/type.go for details.
 475         var bits byte
 476         l := 1 + nameLenLen + len(name)
 477         if exported {
 478                 bits |= 1 << 0
 479         }
 480         if len(tag) > 0 {
 481                 l += tagLenLen + len(tag)
 482                 bits |= 1 << 1
 483         }
 484         if pkg != nil {
 485                 bits |= 1 << 2
 486         }
 487         b := make([]byte, l)
 488         b[0] = bits
 489         copy(b[1:], nameLen[:nameLenLen])
 490         copy(b[1+nameLenLen:], name)
 491         if len(tag) > 0 {
 492                 tb := b[1+nameLenLen+len(name):]
 493                 copy(tb, tagLen[:tagLenLen])
 494                 copy(tb[tagLenLen:], tag)
 495         }
 496
 497         ot = int(s.WriteBytes(base.Ctxt, int64(ot), b))
 498
 499         if pkg != nil {
 500                 ot = dgopkgpathOff(s, ot, pkg)
 501         }
 502
 503         return ot
 504 }
 505
 506 var dnameCount int
 507
 508 // dname creates a reflect.name for a struct field or method.
 509 func dname(name, tag string, pkg *types.Pkg, exported bool) *obj.LSym {
 510         // Write out data as "type.." to signal two things to the
 511         // linker, first that when dynamically linking, the symbol
 512         // should be moved to a relro section, and second that the
 513         // contents should not be decoded as a type.
 514         sname := "type..namedata."
 515         if pkg == nil {
 516                 // In the common case, share data with other packages.
 517                 if name == "" {
 518                         if exported {
 519                                 sname += "-noname-exported." + tag
 520                         } else {
 521                                 sname += "-noname-unexported." + tag
 522                         }
 523                 } else {
 524                         if exported {
 525                                 sname += name + "." + tag
 526                         } else {
 527                                 sname += name + "-" + tag
 528                         }
 529                 }
 530         } else {
 531                 sname = fmt.Sprintf(`%s"".%d`, sname, dnameCount)
 532                 dnameCount++
 533         }
 534         s := base.Ctxt.Lookup(sname)
 535         if len(s.P) > 0 {
 536                 return s
 537         }
 538         ot := dnameData(s, 0, name, tag, pkg, exported)
 539         objw.Global(s, int32(ot), obj.DUPOK|obj.RODATA)
 540         s.Set(obj.AttrContentAddressable, true)
 541         return s
 542 }
 543
 544 // dextratype dumps the fields of a runtime.uncommontype.
 545 // dataAdd is the offset in bytes after the header where the
 546 // backing array of the []method field is written (by dextratypeData).
 547 func dextratype(lsym *obj.LSym, ot int, t *types.Type, dataAdd int) int {
 548         m := methods(t)
 549         if t.Sym() == nil && len(m) == 0 {
 550                 return ot
 551         }
 552         noff := int(types.Rnd(int64(ot), int64(types.PtrSize)))
 553         if noff != ot {
 554                 base.Fatalf("unexpected alignment in dextratype for %v", t)
 555         }
 556
 557         for _, a := range m {
 558                 writeType(a.type_)
 559         }
 560
 561         ot = dgopkgpathOff(lsym, ot, typePkg(t))
 562
 563         dataAdd += uncommonSize(t)
 564         mcount := len(m)
 565         if mcount != int(uint16(mcount)) {
 566                 base.Fatalf("too many methods on %v: %d", t, mcount)
 567         }
 568         xcount := sort.Search(mcount, func(i int) bool { return !types.IsExported(m[i].name.Name) })
 569         if dataAdd != int(uint32(dataAdd)) {
 570                 base.Fatalf("methods are too far away on %v: %d", t, dataAdd)
 571         }
 572
 573         ot = objw.Uint16(lsym, ot, uint16(mcount))
 574         ot = objw.Uint16(lsym, ot, uint16(xcount))
 575         ot = objw.Uint32(lsym, ot, uint32(dataAdd))
 576         ot = objw.Uint32(lsym, ot, 0)
 577         return ot
 578 }
 579
 580 func typePkg(t *types.Type) *types.Pkg {
 581         tsym := t.Sym()
 582         if tsym == nil {
 583                 switch t.Kind() {
 584                 case types.TARRAY, types.TSLICE, types.TPTR, types.TCHAN:
 585                         if t.Elem() != nil {
 586                                 tsym = t.Elem().Sym()
 587                         }
 588                 }
 589         }
 590         if tsym != nil && tsym.Pkg != types.BuiltinPkg {
 591                 return tsym.Pkg
 592         }
 593         return nil
 594 }
 595
 596 // dextratypeData dumps the backing array for the []method field of
 597 // runtime.uncommontype.
 598 func dextratypeData(lsym *obj.LSym, ot int, t *types.Type) int {
 599         for _, a := range methods(t) {
 600                 // ../../../../runtime/type.go:/method
 601                 exported := types.IsExported(a.name.Name)
 602                 var pkg *types.Pkg
 603                 if !exported && a.name.Pkg != typePkg(t) {
 604                         pkg = a.name.Pkg
 605                 }
 606                 nsym := dname(a.name.Name, "", pkg, exported)
 607
 608                 ot = objw.SymPtrOff(lsym, ot, nsym)
 609                 ot = dmethodptrOff(lsym, ot, writeType(a.mtype))
 610                 ot = dmethodptrOff(lsym, ot, a.isym)
 611                 ot = dmethodptrOff(lsym, ot, a.tsym)
 612         }
 613         return ot
 614 }
 615
 616 func dmethodptrOff(s *obj.LSym, ot int, x *obj.LSym) int {
 617         objw.Uint32(s, ot, 0)
 618         r := obj.Addrel(s)
 619         r.Off = int32(ot)
 620         r.Siz = 4
 621         r.Sym = x
 622         r.Type = objabi.R_METHODOFF
 623         return ot + 4
 624 }
 625
 626 var kinds = []int{
 627         types.TINT:        objabi.KindInt,
 628         types.TUINT:       objabi.KindUint,
 629         types.TINT8:       objabi.KindInt8,
 630         types.TUINT8:      objabi.KindUint8,
 631         types.TINT16:      objabi.KindInt16,
 632         types.TUINT16:     objabi.KindUint16,
 633         types.TINT32:      objabi.KindInt32,
 634         types.TUINT32:     objabi.KindUint32,
 635         types.TINT64:      objabi.KindInt64,
 636         types.TUINT64:     objabi.KindUint64,
 637         types.TUINTPTR:    objabi.KindUintptr,
 638         types.TFLOAT32:    objabi.KindFloat32,
 639         types.TFLOAT64:    objabi.KindFloat64,
 640         types.TBOOL:       objabi.KindBool,
 641         types.TSTRING:     objabi.KindString,
 642         types.TPTR:        objabi.KindPtr,
 643         types.TSTRUCT:     objabi.KindStruct,
 644         types.TINTER:      objabi.KindInterface,
 645         types.TCHAN:       objabi.KindChan,
 646         types.TMAP:        objabi.KindMap,
 647         types.TARRAY:      objabi.KindArray,
 648         types.TSLICE:      objabi.KindSlice,
 649         types.TFUNC:       objabi.KindFunc,
 650         types.TCOMPLEX64:  objabi.KindComplex64,
 651         types.TCOMPLEX128: objabi.KindComplex128,
 652         types.TUNSAFEPTR:  objabi.KindUnsafePointer,
 653 }
 654
 655 // tflag is documented in reflect/type.go.
 656 //
 657 // tflag values must be kept in sync with copies in:
 658 //      cmd/compile/internal/reflectdata/reflect.go
 659 //      cmd/link/internal/ld/decodesym.go
 660 //      reflect/type.go
 661 //      runtime/type.go
 662 const (
 663         tflagUncommon      = 1 << 0
 664         tflagExtraStar     = 1 << 1
 665         tflagNamed         = 1 << 2
 666         tflagRegularMemory = 1 << 3
 667 )
 668
 669 var (
 670         memhashvarlen  *obj.LSym
 671         memequalvarlen *obj.LSym
 672 )
 673
 674 // dcommontype dumps the contents of a reflect.rtype (runtime._type).
 675 func dcommontype(lsym *obj.LSym, t *types.Type) int {
 676         types.CalcSize(t)
 677         eqfunc := geneq(t)
 678
 679         sptrWeak := true
 680         var sptr *obj.LSym
 681         if !t.IsPtr() || t.IsPtrElem() {
 682                 tptr := types.NewPtr(t)
 683                 if t.Sym() != nil || methods(tptr) != nil {
 684                         sptrWeak = false
 685                 }
 686                 sptr = writeType(tptr)
 687         }
 688
 689         gcsym, useGCProg, ptrdata := dgcsym(t, true)
 690         delete(gcsymset, t)
 691
 692         // ../../../../reflect/type.go:/^type.rtype
 693         // actual type structure
 694         //      type rtype struct {
 695         //              size          uintptr
 696         //              ptrdata       uintptr
 697         //              hash          uint32
 698         //              tflag         tflag
 699         //              align         uint8
 700         //              fieldAlign    uint8
 701         //              kind          uint8
 702         //              equal         func(unsafe.Pointer, unsafe.Pointer) bool
 703         //              gcdata        *byte
 704         //              str           nameOff
 705         //              ptrToThis     typeOff
 706         //      }
 707         ot := 0
 708         ot = objw.Uintptr(lsym, ot, uint64(t.Width))
 709         ot = objw.Uintptr(lsym, ot, uint64(ptrdata))
 710         ot = objw.Uint32(lsym, ot, types.TypeHash(t))
 711
 712         var tflag uint8
 713         if uncommonSize(t) != 0 {
 714                 tflag |= tflagUncommon
 715         }
 716         if t.Sym() != nil && t.Sym().Name != "" {
 717                 tflag |= tflagNamed
 718         }
 719         if isRegularMemory(t) {
 720                 tflag |= tflagRegularMemory
 721         }
 722
 723         exported := false
 724         p := t.NameString()
 725         // If we're writing out type T,
 726         // we are very likely to write out type *T as well.
 727         // Use the string "*T"[1:] for "T", so that the two
 728         // share storage. This is a cheap way to reduce the
 729         // amount of space taken up by reflect strings.
 730         if !strings.HasPrefix(p, "*") {
 731                 p = "*" + p
 732                 tflag |= tflagExtraStar
 733                 if t.Sym() != nil {
 734                         exported = types.IsExported(t.Sym().Name)
 735                 }
 736         } else {
 737                 if t.Elem() != nil && t.Elem().Sym() != nil {
 738                         exported = types.IsExported(t.Elem().Sym().Name)
 739                 }
 740         }
 741
 742         ot = objw.Uint8(lsym, ot, tflag)
 743
 744         // runtime (and common sense) expects alignment to be a power of two.
 745         i := int(t.Align)
 746
 747         if i == 0 {
 748                 i = 1
 749         }
 750         if i&(i-1) != 0 {
 751                 base.Fatalf("invalid alignment %d for %v", t.Align, t)
 752         }
 753         ot = objw.Uint8(lsym, ot, t.Align) // align
 754         ot = objw.Uint8(lsym, ot, t.Align) // fieldAlign
 755
 756         i = kinds[t.Kind()]
 757         if types.IsDirectIface(t) {
 758                 i |= objabi.KindDirectIface
 759         }
 760         if useGCProg {
 761                 i |= objabi.KindGCProg
 762         }
 763         ot = objw.Uint8(lsym, ot, uint8(i)) // kind
 764         if eqfunc != nil {
 765                 ot = objw.SymPtr(lsym, ot, eqfunc, 0) // equality function
 766         } else {
 767                 ot = objw.Uintptr(lsym, ot, 0) // type we can't do == with
 768         }
 769         ot = objw.SymPtr(lsym, ot, gcsym, 0) // gcdata
 770
 771         nsym := dname(p, "", nil, exported)
 772         ot = objw.SymPtrOff(lsym, ot, nsym) // str
 773         // ptrToThis
 774         if sptr == nil {
 775                 ot = objw.Uint32(lsym, ot, 0)
 776         } else if sptrWeak {
 777                 ot = objw.SymPtrWeakOff(lsym, ot, sptr)
 778         } else {
 779                 ot = objw.SymPtrOff(lsym, ot, sptr)
 780         }
 781
 782         return ot
 783 }
 784
 785 // TrackSym returns the symbol for tracking use of field/method f, assumed
 786 // to be a member of struct/interface type t.
 787 func TrackSym(t *types.Type, f *types.Field) *obj.LSym {
 788         return base.PkgLinksym("go.track", t.LinkString()+"."+f.Sym.Name, obj.ABI0)
 789 }
 790
 791 func TypeSymPrefix(prefix string, t *types.Type) *types.Sym {
 792         p := prefix + "." + t.LinkString()
 793         s := types.TypeSymLookup(p)
 794
 795         // This function is for looking up type-related generated functions
 796         // (e.g. eq and hash). Make sure they are indeed generated.
 797         signatmu.Lock()
 798         NeedRuntimeType(t)
 799         signatmu.Unlock()
 800
 801         //print("algsym: %s -> %+S\n", p, s);
 802
 803         return s
 804 }
 805
 806 func TypeSym(t *types.Type) *types.Sym {
 807         if t == nil || (t.IsPtr() && t.Elem() == nil) || t.IsUntyped() {
 808                 base.Fatalf("TypeSym %v", t)
 809         }
 810         if t.Kind() == types.TFUNC && t.Recv() != nil {
 811                 base.Fatalf("misuse of method type: %v", t)
 812         }
 813         s := types.TypeSym(t)
 814         signatmu.Lock()
 815         NeedRuntimeType(t)
 816         signatmu.Unlock()
 817         return s
 818 }
 819
 820 func TypeLinksymPrefix(prefix string, t *types.Type) *obj.LSym {
 821         return TypeSymPrefix(prefix, t).Linksym()
 822 }
 823
 824 func TypeLinksymLookup(name string) *obj.LSym {
 825         return types.TypeSymLookup(name).Linksym()
 826 }
 827
 828 func TypeLinksym(t *types.Type) *obj.LSym {
 829         return TypeSym(t).Linksym()
 830 }
 831
 832 func TypePtr(t *types.Type) *ir.AddrExpr {
 833         n := ir.NewLinksymExpr(base.Pos, TypeLinksym(t), types.Types[types.TUINT8])
 834         return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 835 }
 836
 837 // ITabLsym returns the LSym representing the itab for concreate type typ
 838 // implementing interface iface.
 839 func ITabLsym(typ, iface *types.Type) *obj.LSym {
 840         s, existed := ir.Pkgs.Itab.LookupOK(typ.LinkString() + "," + iface.LinkString())
 841         lsym := s.Linksym()
 842
 843         if !existed {
 844                 writeITab(lsym, typ, iface)
 845         }
 846         return lsym
 847 }
 848
 849 // ITabAddr returns an expression representing a pointer to the itab
 850 // for concrete type typ implementing interface iface.
 851 func ITabAddr(typ, iface *types.Type) *ir.AddrExpr {
 852         s, existed := ir.Pkgs.Itab.LookupOK(typ.LinkString() + "," + iface.LinkString())
 853         lsym := s.Linksym()
 854
 855         if !existed {
 856                 writeITab(lsym, typ, iface)
 857         }
 858
 859         n := ir.NewLinksymExpr(base.Pos, lsym, types.Types[types.TUINT8])
 860         return typecheck.Expr(typecheck.NodAddr(n)).(*ir.AddrExpr)
 861 }
 862
 863 // needkeyupdate reports whether map updates with t as a key
 864 // need the key to be updated.
 865 func needkeyupdate(t *types.Type) bool {
 866         switch t.Kind() {
 867         case types.TBOOL, types.TINT, types.TUINT, types.TINT8, types.TUINT8, types.TINT16, types.TUINT16, types.TINT32, types.TUINT32,
 868                 types.TINT64, types.TUINT64, types.TUINTPTR, types.TPTR, types.TUNSAFEPTR, types.TCHAN:
 869                 return false
 870
 871         case types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128, // floats and complex can be +0/-0
 872                 types.TINTER,
 873                 types.TSTRING: // strings might have smaller backing stores
 874                 return true
 875
 876         case types.TARRAY:
 877                 return needkeyupdate(t.Elem())
 878
 879         case types.TSTRUCT:
 880                 for _, t1 := range t.Fields().Slice() {
 881                         if needkeyupdate(t1.Type) {
 882                                 return true
 883                         }
 884                 }
 885                 return false
 886
 887         default:
 888                 base.Fatalf("bad type for map key: %v", t)
 889                 return true
 890         }
 891 }
 892
 893 // hashMightPanic reports whether the hash of a map key of type t might panic.
 894 func hashMightPanic(t *types.Type) bool {
 895         switch t.Kind() {
 896         case types.TINTER:
 897                 return true
 898
 899         case types.TARRAY:
 900                 return hashMightPanic(t.Elem())
 901
 902         case types.TSTRUCT:
 903                 for _, t1 := range t.Fields().Slice() {
 904                         if hashMightPanic(t1.Type) {
 905                                 return true
 906                         }
 907                 }
 908                 return false
 909
 910         default:
 911                 return false
 912         }
 913 }
 914
 915 // formalType replaces byte and rune aliases with real types.
 916 // They've been separate internally to make error messages
 917 // better, but we have to merge them in the reflect tables.
 918 func formalType(t *types.Type) *types.Type {
 919         if t == types.ByteType || t == types.RuneType {
 920                 return types.Types[t.Kind()]
 921         }
 922         return t
 923 }
 924
 925 func writeType(t *types.Type) *obj.LSym {
 926         t = formalType(t)
 927         if t.IsUntyped() {
 928                 base.Fatalf("writeType %v", t)
 929         }
 930
 931         s := types.TypeSym(t)
 932         lsym := s.Linksym()
 933         if s.Siggen() {
 934                 return lsym
 935         }
 936         s.SetSiggen(true)
 937
 938         // special case (look for runtime below):
 939         // when compiling package runtime,
 940         // emit the type structures for int, float, etc.
 941         tbase := t
 942
 943         if t.IsPtr() && t.Sym() == nil && t.Elem().Sym() != nil {
 944                 tbase = t.Elem()
 945         }
 946         if tbase.Kind() == types.TFORW {
 947                 base.Fatalf("unresolved defined type: %v", tbase)
 948         }
 949
 950         dupok := 0
 951         if tbase.Sym() == nil || tbase.HasShape() { // TODO(mdempsky): Probably need DUPOK for instantiated types too.
 952                 dupok = obj.DUPOK
 953         }
 954
 955         if !NeedEmit(tbase) {
 956                 if i := typecheck.BaseTypeIndex(t); i >= 0 {
 957                         lsym.Pkg = tbase.Sym().Pkg.Prefix
 958                         lsym.SymIdx = int32(i)
 959                         lsym.Set(obj.AttrIndexed, true)
 960                 }
 961
 962                 // TODO(mdempsky): Investigate whether this still happens.
 963                 // If we know we don't need to emit code for a type,
 964                 // we should have a link-symbol index for it.
 965                 // See also TODO in NeedEmit.
 966                 return lsym
 967         }
 968
 969         ot := 0
 970         switch t.Kind() {
 971         default:
 972                 ot = dcommontype(lsym, t)
 973                 ot = dextratype(lsym, ot, t, 0)
 974
 975         case types.TARRAY:
 976                 // ../../../../runtime/type.go:/arrayType
 977                 s1 := writeType(t.Elem())
 978                 t2 := types.NewSlice(t.Elem())
 979                 s2 := writeType(t2)
 980                 ot = dcommontype(lsym, t)
 981                 ot = objw.SymPtr(lsym, ot, s1, 0)
 982                 ot = objw.SymPtr(lsym, ot, s2, 0)
 983                 ot = objw.Uintptr(lsym, ot, uint64(t.NumElem()))
 984                 ot = dextratype(lsym, ot, t, 0)
 985
 986         case types.TSLICE:
 987                 // ../../../../runtime/type.go:/sliceType
 988                 s1 := writeType(t.Elem())
 989                 ot = dcommontype(lsym, t)
 990                 ot = objw.SymPtr(lsym, ot, s1, 0)
 991                 ot = dextratype(lsym, ot, t, 0)
 992
 993         case types.TCHAN:
 994                 // ../../../../runtime/type.go:/chanType
 995                 s1 := writeType(t.Elem())
 996                 ot = dcommontype(lsym, t)
 997                 ot = objw.SymPtr(lsym, ot, s1, 0)
 998                 ot = objw.Uintptr(lsym, ot, uint64(t.ChanDir()))
 999                 ot = dextratype(lsym, ot, t, 0)
1000
1001         case types.TFUNC:
1002                 for _, t1 := range t.Recvs().Fields().Slice() {
1003                         writeType(t1.Type)
1004                 }
1005                 isddd := false
1006                 for _, t1 := range t.Params().Fields().Slice() {
1007                         isddd = t1.IsDDD()
1008                         writeType(t1.Type)
1009                 }
1010                 for _, t1 := range t.Results().Fields().Slice() {
1011                         writeType(t1.Type)
1012                 }
1013
1014                 ot = dcommontype(lsym, t)
1015                 inCount := t.NumRecvs() + t.NumParams()
1016                 outCount := t.NumResults()
1017                 if isddd {
1018                         outCount |= 1 << 15
1019                 }
1020                 ot = objw.Uint16(lsym, ot, uint16(inCount))
1021                 ot = objw.Uint16(lsym, ot, uint16(outCount))
1022                 if types.PtrSize == 8 {
1023                         ot += 4 // align for *rtype
1024                 }
1025
1026                 dataAdd := (inCount + t.NumResults()) * types.PtrSize
1027                 ot = dextratype(lsym, ot, t, dataAdd)
1028
1029                 // Array of rtype pointers follows funcType.
1030                 for _, t1 := range t.Recvs().Fields().Slice() {
1031                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1032                 }
1033                 for _, t1 := range t.Params().Fields().Slice() {
1034                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1035                 }
1036                 for _, t1 := range t.Results().Fields().Slice() {
1037                         ot = objw.SymPtr(lsym, ot, writeType(t1.Type), 0)
1038                 }
1039
1040         case types.TINTER:
1041                 m := imethods(t)
1042                 n := len(m)
1043                 for _, a := range m {
1044                         writeType(a.type_)
1045                 }
1046
1047                 // ../../../../runtime/type.go:/interfaceType
1048                 ot = dcommontype(lsym, t)
1049
1050                 var tpkg *types.Pkg
1051                 if t.Sym() != nil && t != types.Types[t.Kind()] && t != types.ErrorType {
1052                         tpkg = t.Sym().Pkg
1053                 }
1054                 ot = dgopkgpath(lsym, ot, tpkg)
1055
1056                 ot = objw.SymPtr(lsym, ot, lsym, ot+3*types.PtrSize+uncommonSize(t))
1057                 ot = objw.Uintptr(lsym, ot, uint64(n))
1058                 ot = objw.Uintptr(lsym, ot, uint64(n))
1059                 dataAdd := imethodSize() * n
1060                 ot = dextratype(lsym, ot, t, dataAdd)
1061
1062                 for _, a := range m {
1063                         // ../../../../runtime/type.go:/imethod
1064                         exported := types.IsExported(a.name.Name)
1065                         var pkg *types.Pkg
1066                         if !exported && a.name.Pkg != tpkg {
1067                                 pkg = a.name.Pkg
1068                         }
1069                         nsym := dname(a.name.Name, "", pkg, exported)
1070
1071                         ot = objw.SymPtrOff(lsym, ot, nsym)
1072                         ot = objw.SymPtrOff(lsym, ot, writeType(a.type_))
1073                 }
1074
1075         // ../../../../runtime/type.go:/mapType
1076         case types.TMAP:
1077                 s1 := writeType(t.Key())
1078                 s2 := writeType(t.Elem())
1079                 s3 := writeType(MapBucketType(t))
1080                 hasher := genhash(t.Key())
1081
1082                 ot = dcommontype(lsym, t)
1083                 ot = objw.SymPtr(lsym, ot, s1, 0)
1084                 ot = objw.SymPtr(lsym, ot, s2, 0)
1085                 ot = objw.SymPtr(lsym, ot, s3, 0)
1086                 ot = objw.SymPtr(lsym, ot, hasher, 0)
1087                 var flags uint32
1088                 // Note: flags must match maptype accessors in ../../../../runtime/type.go
1089                 // and maptype builder in ../../../../reflect/type.go:MapOf.
1090                 if t.Key().Width > MAXKEYSIZE {
1091                         ot = objw.Uint8(lsym, ot, uint8(types.PtrSize))
1092                         flags |= 1 // indirect key
1093                 } else {
1094                         ot = objw.Uint8(lsym, ot, uint8(t.Key().Width))
1095                 }
1096
1097                 if t.Elem().Width > MAXELEMSIZE {
1098                         ot = objw.Uint8(lsym, ot, uint8(types.PtrSize))
1099                         flags |= 2 // indirect value
1100                 } else {
1101                         ot = objw.Uint8(lsym, ot, uint8(t.Elem().Width))
1102                 }
1103                 ot = objw.Uint16(lsym, ot, uint16(MapBucketType(t).Width))
1104                 if types.IsReflexive(t.Key()) {
1105                         flags |= 4 // reflexive key
1106                 }
1107                 if needkeyupdate(t.Key()) {
1108                         flags |= 8 // need key update
1109                 }
1110                 if hashMightPanic(t.Key()) {
1111                         flags |= 16 // hash might panic
1112                 }
1113                 ot = objw.Uint32(lsym, ot, flags)
1114                 ot = dextratype(lsym, ot, t, 0)
1115                 if u := t.Underlying(); u != t {
1116                         // If t is a named map type, also keep the underlying map
1117                         // type live in the binary. This is important to make sure that
1118                         // a named map and that same map cast to its underlying type via
1119                         // reflection, use the same hash function. See issue 37716.
1120                         r := obj.Addrel(lsym)
1121                         r.Sym = writeType(u)
1122                         r.Type = objabi.R_KEEP
1123                 }
1124
1125         case types.TPTR:
1126                 if t.Elem().Kind() == types.TANY {
1127                         // ../../../../runtime/type.go:/UnsafePointerType
1128                         ot = dcommontype(lsym, t)
1129                         ot = dextratype(lsym, ot, t, 0)
1130
1131                         break
1132                 }
1133
1134                 // ../../../../runtime/type.go:/ptrType
1135                 s1 := writeType(t.Elem())
1136
1137                 ot = dcommontype(lsym, t)
1138                 ot = objw.SymPtr(lsym, ot, s1, 0)
1139                 ot = dextratype(lsym, ot, t, 0)
1140
1141         // ../../../../runtime/type.go:/structType
1142         // for security, only the exported fields.
1143         case types.TSTRUCT:
1144                 fields := t.Fields().Slice()
1145
1146                 // omitFieldForAwfulBoringCryptoKludge reports whether
1147                 // the field t should be omitted from the reflect data.
1148                 // In the crypto/... packages we omit an unexported field
1149                 // named "boring", to keep from breaking client code that
1150                 // expects rsa.PublicKey etc to have only public fields.
1151                 // As the name suggests, this is an awful kludge, but it is
1152                 // limited to the dev.boringcrypto branch and avoids
1153                 // much more invasive effects elsewhere.
1154                 omitFieldForAwfulBoringCryptoKludge := func(t *types.Field) bool {
1155                         if t.Sym == nil || t.Sym.Name != "boring" || t.Sym.Pkg == nil {
1156                                 return false
1157                         }
1158                         path := t.Sym.Pkg.Path
1159                         if t.Sym.Pkg == types.LocalPkg {
1160                                 path = base.Ctxt.Pkgpath
1161                         }
1162                         return strings.HasPrefix(path, "crypto/")
1163                 }
1164                 newFields := fields[:0:0]
1165                 for _, t1 := range fields {
1166                         if !omitFieldForAwfulBoringCryptoKludge(t1) {
1167                                 newFields = append(newFields, t1)
1168                         }
1169                 }
1170                 fields = newFields
1171
1172                 for _, t1 := range fields {
1173                         writeType(t1.Type)
1174                 }
1175
1176                 // All non-exported struct field names within a struct
1177                 // type must originate from a single package. By
1178                 // identifying and recording that package within the
1179                 // struct type descriptor, we can omit that
1180                 // information from the field descriptors.
1181                 var spkg *types.Pkg
1182                 for _, f := range fields {
1183                         if !types.IsExported(f.Sym.Name) {
1184                                 spkg = f.Sym.Pkg
1185                                 break
1186                         }
1187                 }
1188
1189                 ot = dcommontype(lsym, t)
1190                 ot = dgopkgpath(lsym, ot, spkg)
1191                 ot = objw.SymPtr(lsym, ot, lsym, ot+3*types.PtrSize+uncommonSize(t))
1192                 ot = objw.Uintptr(lsym, ot, uint64(len(fields)))
1193                 ot = objw.Uintptr(lsym, ot, uint64(len(fields)))
1194
1195                 dataAdd := len(fields) * structfieldSize()
1196                 ot = dextratype(lsym, ot, t, dataAdd)
1197
1198                 for _, f := range fields {
1199                         // ../../../../runtime/type.go:/structField
1200                         ot = dnameField(lsym, ot, spkg, f)
1201                         ot = objw.SymPtr(lsym, ot, writeType(f.Type), 0)
1202                         offsetAnon := uint64(f.Offset) << 1
1203                         if offsetAnon>>1 != uint64(f.Offset) {
1204                                 base.Fatalf("%v: bad field offset for %s", t, f.Sym.Name)
1205                         }
1206                         if f.Embedded != 0 {
1207                                 offsetAnon |= 1
1208                         }
1209                         ot = objw.Uintptr(lsym, ot, offsetAnon)
1210                 }
1211         }
1212
1213         ot = dextratypeData(lsym, ot, t)
1214         objw.Global(lsym, int32(ot), int16(dupok|obj.RODATA))
1215
1216         // The linker will leave a table of all the typelinks for
1217         // types in the binary, so the runtime can find them.
1218         //
1219         // When buildmode=shared, all types are in typelinks so the
1220         // runtime can deduplicate type pointers.
1221         keep := base.Ctxt.Flag_dynlink
1222         if !keep && t.Sym() == nil {
1223                 // For an unnamed type, we only need the link if the type can
1224                 // be created at run time by reflect.PtrTo and similar
1225                 // functions. If the type exists in the program, those
1226                 // functions must return the existing type structure rather
1227                 // than creating a new one.
1228                 switch t.Kind() {
1229                 case types.TPTR, types.TARRAY, types.TCHAN, types.TFUNC, types.TMAP, types.TSLICE, types.TSTRUCT:
1230                         keep = true
1231                 }
1232         }
1233         // Do not put Noalg types in typelinks.  See issue #22605.
1234         if types.TypeHasNoAlg(t) {
1235                 keep = false
1236         }
1237         lsym.Set(obj.AttrMakeTypelink, keep)
1238
1239         return lsym
1240 }
1241
1242 // InterfaceMethodOffset returns the offset of the i-th method in the interface
1243 // type descriptor, ityp.
1244 func InterfaceMethodOffset(ityp *types.Type, i int64) int64 {
1245         // interface type descriptor layout is struct {
1246         //   _type        // commonSize
1247         //   pkgpath      // 1 word
1248         //   []imethod    // 3 words (pointing to [...]imethod below)
1249         //   uncommontype // uncommonSize
1250         //   [...]imethod
1251         // }
1252         // The size of imethod is 8.
1253         return int64(commonSize()+4*types.PtrSize+uncommonSize(ityp)) + i*8
1254 }
1255
1256 // NeedRuntimeType ensures that a runtime type descriptor is emitted for t.
1257 func NeedRuntimeType(t *types.Type) {
1258         if t.HasTParam() {
1259                 // Generic types don't really exist at run-time and have no runtime
1260                 // type descriptor.  But we do write out shape types.
1261                 return
1262         }
1263         if _, ok := signatset[t]; !ok {
1264                 signatset[t] = struct{}{}
1265                 signatslice = append(signatslice, t)
1266         }
1267 }
1268
1269 func WriteRuntimeTypes() {
1270         // Process signatset. Use a loop, as writeType adds
1271         // entries to signatset while it is being processed.
1272         signats := make([]typeAndStr, len(signatslice))
1273         for len(signatslice) > 0 {
1274                 signats = signats[:0]
1275                 // Transfer entries to a slice and sort, for reproducible builds.
1276                 for _, t := range signatslice {
1277                         signats = append(signats, typeAndStr{t: t, short: types.TypeSymName(t), regular: t.String()})
1278                         delete(signatset, t)
1279                 }
1280                 signatslice = signatslice[:0]
1281                 sort.Sort(typesByString(signats))
1282                 for _, ts := range signats {
1283                         t := ts.t
1284                         writeType(t)
1285                         if t.Sym() != nil {
1286                                 writeType(types.NewPtr(t))
1287                         }
1288                 }
1289         }
1290
1291         // Emit GC data symbols.
1292         gcsyms := make([]typeAndStr, 0, len(gcsymset))
1293         for t := range gcsymset {
1294                 gcsyms = append(gcsyms, typeAndStr{t: t, short: types.TypeSymName(t), regular: t.String()})
1295         }
1296         sort.Sort(typesByString(gcsyms))
1297         for _, ts := range gcsyms {
1298                 dgcsym(ts.t, true)
1299         }
1300 }
1301
1302 // writeITab writes the itab for concrete type typ implementing
1303 // interface iface.
1304 func writeITab(lsym *obj.LSym, typ, iface *types.Type) {
1305         // TODO(mdempsky): Fix methodWrapper, geneq, and genhash (and maybe
1306         // others) to stop clobbering these.
1307         oldpos, oldfn := base.Pos, ir.CurFunc
1308         defer func() { base.Pos, ir.CurFunc = oldpos, oldfn }()
1309
1310         if typ == nil || (typ.IsPtr() && typ.Elem() == nil) || typ.IsUntyped() || iface == nil || !iface.IsInterface() || iface.IsEmptyInterface() {
1311                 base.Fatalf("writeITab(%v, %v)", typ, iface)
1312         }
1313
1314         sigs := iface.AllMethods().Slice()
1315         entries := make([]*obj.LSym, 0, len(sigs))
1316
1317         // both sigs and methods are sorted by name,
1318         // so we can find the intersection in a single pass
1319         for _, m := range methods(typ) {
1320                 if m.name == sigs[0].Sym {
1321                         entries = append(entries, m.isym)
1322                         if m.isym == nil {
1323                                 panic("NO ISYM")
1324                         }
1325                         sigs = sigs[1:]
1326                         if len(sigs) == 0 {
1327                                 break
1328                         }
1329                 }
1330                 if sigs[0].Sym.Name == "==" {
1331                         sigs = sigs[1:]
1332                         if len(sigs) == 0 {
1333                                 break
1334                         }
1335                 }
1336         }
1337         if len(sigs) != 0 {
1338                 base.Fatalf("incomplete itab")
1339         }
1340
1341         // dump empty itab symbol into i.sym
1342         // type itab struct {
1343         //   inter  *interfacetype
1344         //   _type  *_type
1345         //   hash   uint32
1346         //   _      [4]byte
1347         //   fun    [1]uintptr // variable sized
1348         // }
1349         o := objw.SymPtr(lsym, 0, writeType(iface), 0)
1350         o = objw.SymPtr(lsym, o, writeType(typ), 0)
1351         o = objw.Uint32(lsym, o, types.TypeHash(typ)) // copy of type hash
1352         o += 4                                        // skip unused field
1353         for _, fn := range entries {
1354                 o = objw.SymPtrWeak(lsym, o, fn, 0) // method pointer for each method
1355         }
1356         // Nothing writes static itabs, so they are read only.
1357         objw.Global(lsym, int32(o), int16(obj.DUPOK|obj.RODATA))
1358         lsym.Set(obj.AttrContentAddressable, true)
1359 }
1360
1361 func WriteTabs() {
1362         // process ptabs
1363         if types.LocalPkg.Name == "main" && len(ptabs) > 0 {
1364                 ot := 0
1365                 s := base.Ctxt.Lookup("go.plugin.tabs")
1366                 for _, p := range ptabs {
1367                         // Dump ptab symbol into go.pluginsym package.
1368                         //
1369                         // type ptab struct {
1370                         //      name nameOff
1371                         //      typ  typeOff // pointer to symbol
1372                         // }
1373                         nsym := dname(p.Sym().Name, "", nil, true)
1374                         t := p.Type()
1375                         if p.Class != ir.PFUNC {
1376                                 t = types.NewPtr(t)
1377                         }
1378                         tsym := writeType(t)
1379                         ot = objw.SymPtrOff(s, ot, nsym)
1380                         ot = objw.SymPtrOff(s, ot, tsym)
1381                         // Plugin exports symbols as interfaces. Mark their types
1382                         // as UsedInIface.
1383                         tsym.Set(obj.AttrUsedInIface, true)
1384                 }
1385                 objw.Global(s, int32(ot), int16(obj.RODATA))
1386
1387                 ot = 0
1388                 s = base.Ctxt.Lookup("go.plugin.exports")
1389                 for _, p := range ptabs {
1390                         ot = objw.SymPtr(s, ot, p.Linksym(), 0)
1391                 }
1392                 objw.Global(s, int32(ot), int16(obj.RODATA))
1393         }
1394 }
1395
1396 func WriteImportStrings() {
1397         // generate import strings for imported packages
1398         for _, p := range types.ImportedPkgList() {
1399                 dimportpath(p)
1400         }
1401 }
1402
1403 func WriteBasicTypes() {
1404         // do basic types if compiling package runtime.
1405         // they have to be in at least one package,
1406         // and runtime is always loaded implicitly,
1407         // so this is as good as any.
1408         // another possible choice would be package main,
1409         // but using runtime means fewer copies in object files.
1410         if base.Ctxt.Pkgpath == "runtime" {
1411                 for i := types.Kind(1); i <= types.TBOOL; i++ {
1412                         writeType(types.NewPtr(types.Types[i]))
1413                 }
1414                 writeType(types.NewPtr(types.Types[types.TSTRING]))
1415                 writeType(types.NewPtr(types.Types[types.TUNSAFEPTR]))
1416
1417                 // emit type structs for error and func(error) string.
1418                 // The latter is the type of an auto-generated wrapper.
1419                 writeType(types.NewPtr(types.ErrorType))
1420
1421                 writeType(types.NewSignature(types.NoPkg, nil, nil, []*types.Field{
1422                         types.NewField(base.Pos, nil, types.ErrorType),
1423                 }, []*types.Field{
1424                         types.NewField(base.Pos, nil, types.Types[types.TSTRING]),
1425                 }))
1426
1427                 // add paths for runtime and main, which 6l imports implicitly.
1428                 dimportpath(ir.Pkgs.Runtime)
1429
1430                 if base.Flag.Race {
1431                         dimportpath(types.NewPkg("runtime/race", ""))
1432                 }
1433                 if base.Flag.MSan {
1434                         dimportpath(types.NewPkg("runtime/msan", ""))
1435                 }
1436
1437                 dimportpath(types.NewPkg("main", ""))
1438         }
1439 }
1440
1441 type typeAndStr struct {
1442         t       *types.Type
1443         short   string // "short" here means NameString
1444         regular string
1445 }
1446
1447 type typesByString []typeAndStr
1448
1449 func (a typesByString) Len() int { return len(a) }
1450 func (a typesByString) Less(i, j int) bool {
1451         if a[i].short != a[j].short {
1452                 return a[i].short < a[j].short
1453         }
1454         // When the only difference between the types is whether
1455         // they refer to byte or uint8, such as **byte vs **uint8,
1456         // the types' NameStrings can be identical.
1457         // To preserve deterministic sort ordering, sort these by String().
1458         //
1459         // TODO(mdempsky): This all seems suspect. Using LinkString would
1460         // avoid naming collisions, and there shouldn't be a reason to care
1461         // about "byte" vs "uint8": they share the same runtime type
1462         // descriptor anyway.
1463         if a[i].regular != a[j].regular {
1464                 return a[i].regular < a[j].regular
1465         }
1466         // Identical anonymous interfaces defined in different locations
1467         // will be equal for the above checks, but different in DWARF output.
1468         // Sort by source position to ensure deterministic order.
1469         // See issues 27013 and 30202.
1470         if a[i].t.Kind() == types.TINTER && a[i].t.AllMethods().Len() > 0 {
1471                 return a[i].t.AllMethods().Index(0).Pos.Before(a[j].t.AllMethods().Index(0).Pos)
1472         }
1473         return false
1474 }
1475 func (a typesByString) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1476
1477 // maxPtrmaskBytes is the maximum length of a GC ptrmask bitmap,
1478 // which holds 1-bit entries describing where pointers are in a given type.
1479 // Above this length, the GC information is recorded as a GC program,
1480 // which can express repetition compactly. In either form, the
1481 // information is used by the runtime to initialize the heap bitmap,
1482 // and for large types (like 128 or more words), they are roughly the
1483 // same speed. GC programs are never much larger and often more
1484 // compact. (If large arrays are involved, they can be arbitrarily
1485 // more compact.)
1486 //
1487 // The cutoff must be large enough that any allocation large enough to
1488 // use a GC program is large enough that it does not share heap bitmap
1489 // bytes with any other objects, allowing the GC program execution to
1490 // assume an aligned start and not use atomic operations. In the current
1491 // runtime, this means all malloc size classes larger than the cutoff must
1492 // be multiples of four words. On 32-bit systems that's 16 bytes, and
1493 // all size classes >= 16 bytes are 16-byte aligned, so no real constraint.
1494 // On 64-bit systems, that's 32 bytes, and 32-byte alignment is guaranteed
1495 // for size classes >= 256 bytes. On a 64-bit system, 256 bytes allocated
1496 // is 32 pointers, the bits for which fit in 4 bytes. So maxPtrmaskBytes
1497 // must be >= 4.
1498 //
1499 // We used to use 16 because the GC programs do have some constant overhead
1500 // to get started, and processing 128 pointers seems to be enough to
1501 // amortize that overhead well.
1502 //
1503 // To make sure that the runtime's chansend can call typeBitsBulkBarrier,
1504 // we raised the limit to 2048, so that even 32-bit systems are guaranteed to
1505 // use bitmaps for objects up to 64 kB in size.
1506 //
1507 // Also known to reflect/type.go.
1508 //
1509 const maxPtrmaskBytes = 2048
1510
1511 // GCSym returns a data symbol containing GC information for type t, along
1512 // with a boolean reporting whether the UseGCProg bit should be set in the
1513 // type kind, and the ptrdata field to record in the reflect type information.
1514 // GCSym may be called in concurrent backend, so it does not emit the symbol
1515 // content.
1516 func GCSym(t *types.Type) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1517         // Record that we need to emit the GC symbol.
1518         gcsymmu.Lock()
1519         if _, ok := gcsymset[t]; !ok {
1520                 gcsymset[t] = struct{}{}
1521         }
1522         gcsymmu.Unlock()
1523
1524         return dgcsym(t, false)
1525 }
1526
1527 // dgcsym returns a data symbol containing GC information for type t, along
1528 // with a boolean reporting whether the UseGCProg bit should be set in the
1529 // type kind, and the ptrdata field to record in the reflect type information.
1530 // When write is true, it writes the symbol data.
1531 func dgcsym(t *types.Type, write bool) (lsym *obj.LSym, useGCProg bool, ptrdata int64) {
1532         ptrdata = types.PtrDataSize(t)
1533         if ptrdata/int64(types.PtrSize) <= maxPtrmaskBytes*8 {
1534                 lsym = dgcptrmask(t, write)
1535                 return
1536         }
1537
1538         useGCProg = true
1539         lsym, ptrdata = dgcprog(t, write)
1540         return
1541 }
1542
1543 // dgcptrmask emits and returns the symbol containing a pointer mask for type t.
1544 func dgcptrmask(t *types.Type, write bool) *obj.LSym {
1545         ptrmask := make([]byte, (types.PtrDataSize(t)/int64(types.PtrSize)+7)/8)
1546         fillptrmask(t, ptrmask)
1547         p := fmt.Sprintf("runtime.gcbits.%x", ptrmask)
1548
1549         lsym := base.Ctxt.Lookup(p)
1550         if write && !lsym.OnList() {
1551                 for i, x := range ptrmask {
1552                         objw.Uint8(lsym, i, x)
1553                 }
1554                 objw.Global(lsym, int32(len(ptrmask)), obj.DUPOK|obj.RODATA|obj.LOCAL)
1555                 lsym.Set(obj.AttrContentAddressable, true)
1556         }
1557         return lsym
1558 }
1559
1560 // fillptrmask fills in ptrmask with 1s corresponding to the
1561 // word offsets in t that hold pointers.
1562 // ptrmask is assumed to fit at least types.PtrDataSize(t)/PtrSize bits.
1563 func fillptrmask(t *types.Type, ptrmask []byte) {
1564         for i := range ptrmask {
1565                 ptrmask[i] = 0
1566         }
1567         if !t.HasPointers() {
1568                 return
1569         }
1570
1571         vec := bitvec.New(8 * int32(len(ptrmask)))
1572         typebits.Set(t, 0, vec)
1573
1574         nptr := types.PtrDataSize(t) / int64(types.PtrSize)
1575         for i := int64(0); i < nptr; i++ {
1576                 if vec.Get(int32(i)) {
1577                         ptrmask[i/8] |= 1 << (uint(i) % 8)
1578                 }
1579         }
1580 }
1581
1582 // dgcprog emits and returns the symbol containing a GC program for type t
1583 // along with the size of the data described by the program (in the range
1584 // [types.PtrDataSize(t), t.Width]).
1585 // In practice, the size is types.PtrDataSize(t) except for non-trivial arrays.
1586 // For non-trivial arrays, the program describes the full t.Width size.
1587 func dgcprog(t *types.Type, write bool) (*obj.LSym, int64) {
1588         types.CalcSize(t)
1589         if t.Width == types.BADWIDTH {
1590                 base.Fatalf("dgcprog: %v badwidth", t)
1591         }
1592         lsym := TypeLinksymPrefix(".gcprog", t)
1593         var p gcProg
1594         p.init(lsym, write)
1595         p.emit(t, 0)
1596         offset := p.w.BitIndex() * int64(types.PtrSize)
1597         p.end()
1598         if ptrdata := types.PtrDataSize(t); offset < ptrdata || offset > t.Width {
1599                 base.Fatalf("dgcprog: %v: offset=%d but ptrdata=%d size=%d", t, offset, ptrdata, t.Width)
1600         }
1601         return lsym, offset
1602 }
1603
1604 type gcProg struct {
1605         lsym   *obj.LSym
1606         symoff int
1607         w      gcprog.Writer
1608         write  bool
1609 }
1610
1611 func (p *gcProg) init(lsym *obj.LSym, write bool) {
1612         p.lsym = lsym
1613         p.write = write && !lsym.OnList()
1614         p.symoff = 4 // first 4 bytes hold program length
1615         if !write {
1616                 p.w.Init(func(byte) {})
1617                 return
1618         }
1619         p.w.Init(p.writeByte)
1620         if base.Debug.GCProg > 0 {
1621                 fmt.Fprintf(os.Stderr, "compile: start GCProg for %v\n", lsym)
1622                 p.w.Debug(os.Stderr)
1623         }
1624 }
1625
1626 func (p *gcProg) writeByte(x byte) {
1627         p.symoff = objw.Uint8(p.lsym, p.symoff, x)
1628 }
1629
1630 func (p *gcProg) end() {
1631         p.w.End()
1632         if !p.write {
1633                 return
1634         }
1635         objw.Uint32(p.lsym, 0, uint32(p.symoff-4))
1636         objw.Global(p.lsym, int32(p.symoff), obj.DUPOK|obj.RODATA|obj.LOCAL)
1637         p.lsym.Set(obj.AttrContentAddressable, true)
1638         if base.Debug.GCProg > 0 {
1639                 fmt.Fprintf(os.Stderr, "compile: end GCProg for %v\n", p.lsym)
1640         }
1641 }
1642
1643 func (p *gcProg) emit(t *types.Type, offset int64) {
1644         types.CalcSize(t)
1645         if !t.HasPointers() {
1646                 return
1647         }
1648         if t.Width == int64(types.PtrSize) {
1649                 p.w.Ptr(offset / int64(types.PtrSize))
1650                 return
1651         }
1652         switch t.Kind() {
1653         default:
1654                 base.Fatalf("gcProg.emit: unexpected type %v", t)
1655
1656         case types.TSTRING:
1657                 p.w.Ptr(offset / int64(types.PtrSize))
1658
1659         case types.TINTER:
1660                 // Note: the first word isn't a pointer. See comment in typebits.Set
1661                 p.w.Ptr(offset/int64(types.PtrSize) + 1)
1662
1663         case types.TSLICE:
1664                 p.w.Ptr(offset / int64(types.PtrSize))
1665
1666         case types.TARRAY:
1667                 if t.NumElem() == 0 {
1668                         // should have been handled by haspointers check above
1669                         base.Fatalf("gcProg.emit: empty array")
1670                 }
1671
1672                 // Flatten array-of-array-of-array to just a big array by multiplying counts.
1673                 count := t.NumElem()
1674                 elem := t.Elem()
1675                 for elem.IsArray() {
1676                         count *= elem.NumElem()
1677                         elem = elem.Elem()
1678                 }
1679
1680                 if !p.w.ShouldRepeat(elem.Width/int64(types.PtrSize), count) {
1681                         // Cheaper to just emit the bits.
1682                         for i := int64(0); i < count; i++ {
1683                                 p.emit(elem, offset+i*elem.Width)
1684                         }
1685                         return
1686                 }
1687                 p.emit(elem, offset)
1688                 p.w.ZeroUntil((offset + elem.Width) / int64(types.PtrSize))
1689                 p.w.Repeat(elem.Width/int64(types.PtrSize), count-1)
1690
1691         case types.TSTRUCT:
1692                 for _, t1 := range t.Fields().Slice() {
1693                         p.emit(t1.Type, offset+t1.Offset)
1694                 }
1695         }
1696 }
1697
1698 // ZeroAddr returns the address of a symbol with at least
1699 // size bytes of zeros.
1700 func ZeroAddr(size int64) ir.Node {
1701         if size >= 1<<31 {
1702                 base.Fatalf("map elem too big %d", size)
1703         }
1704         if ZeroSize < size {
1705                 ZeroSize = size
1706         }
1707         lsym := base.PkgLinksym("go.map", "zero", obj.ABI0)
1708         x := ir.NewLinksymExpr(base.Pos, lsym, types.Types[types.TUINT8])
1709         return typecheck.Expr(typecheck.NodAddr(x))
1710 }
1711
1712 func CollectPTabs() {
1713         if !base.Ctxt.Flag_dynlink || types.LocalPkg.Name != "main" {
1714                 return
1715         }
1716         for _, exportn := range typecheck.Target.Exports {
1717                 s := exportn.Sym()
1718                 nn := ir.AsNode(s.Def)
1719                 if nn == nil {
1720                         continue
1721                 }
1722                 if nn.Op() != ir.ONAME {
1723                         continue
1724                 }
1725                 n := nn.(*ir.Name)
1726                 if !types.IsExported(s.Name) {
1727                         continue
1728                 }
1729                 if s.Pkg.Name != "main" {
1730                         continue
1731                 }
1732                 ptabs = append(ptabs, n)
1733         }
1734 }
1735
1736 // NeedEmit reports whether typ is a type that we need to emit code
1737 // for (e.g., runtime type descriptors, method wrappers).
1738 func NeedEmit(typ *types.Type) bool {
1739         // TODO(mdempsky): Export data should keep track of which anonymous
1740         // and instantiated types were emitted, so at least downstream
1741         // packages can skip re-emitting them.
1742         //
1743         // Perhaps we can just generalize the linker-symbol indexing to
1744         // track the index of arbitrary types, not just defined types, and
1745         // use its presence to detect this. The same idea would work for
1746         // instantiated generic functions too.
1747
1748         switch sym := typ.Sym(); {
1749         case sym == nil:
1750                 // Anonymous type; possibly never seen before or ever again.
1751                 // Need to emit to be safe (however, see TODO above).
1752                 return true
1753
1754         case sym.Pkg == types.LocalPkg:
1755                 // Local defined type; our responsibility.
1756                 return true
1757
1758         case base.Ctxt.Pkgpath == "runtime" && (sym.Pkg == types.BuiltinPkg || sym.Pkg == ir.Pkgs.Unsafe):
1759                 // Package runtime is responsible for including code for builtin
1760                 // types (predeclared and package unsafe).
1761                 return true
1762
1763         case typ.IsFullyInstantiated():
1764                 // Instantiated type; possibly instantiated with unique type arguments.
1765                 // Need to emit to be safe (however, see TODO above).
1766                 return true
1767
1768         case typ.HasShape():
1769                 // Shape type; need to emit even though it lives in the .shape package.
1770                 // TODO: make sure the linker deduplicates them (see dupok in writeType above).
1771                 return true
1772
1773         default:
1774                 // Should have been emitted by an imported package.
1775                 return false
1776         }
1777 }
1778
1779 // Generate a wrapper function to convert from
1780 // a receiver of type T to a receiver of type U.
1781 // That is,
1782 //
1783 //      func (t T) M() {
1784 //              ...
1785 //      }
1786 //
1787 // already exists; this function generates
1788 //
1789 //      func (u U) M() {
1790 //              u.M()
1791 //      }
1792 //
1793 // where the types T and U are such that u.M() is valid
1794 // and calls the T.M method.
1795 // The resulting function is for use in method tables.
1796 //
1797 //      rcvr - U
1798 //      method - M func (t T)(), a TFIELD type struct
1799 //
1800 // Also wraps methods on instantiated generic types for use in itab entries.
1801 // For an instantiated generic type G[int], we generate wrappers like:
1802 // G[int] pointer shaped:
1803 //      func (x G[int]) f(arg) {
1804 //              .inst.G[int].f(dictionary, x, arg)
1805 //      }
1806 // G[int] not pointer shaped:
1807 //      func (x *G[int]) f(arg) {
1808 //              .inst.G[int].f(dictionary, *x, arg)
1809 //      }
1810 // These wrappers are always fully stenciled.
1811 func methodWrapper(rcvr *types.Type, method *types.Field, forItab bool) *obj.LSym {
1812         orig := rcvr
1813         if forItab && !types.IsDirectIface(rcvr) {
1814                 rcvr = rcvr.PtrTo()
1815         }
1816
1817         generic := false
1818         // We don't need a dictionary if we are reaching a method (possibly via an
1819         // embedded field) which is an interface method.
1820         if !types.IsInterfaceMethod(method.Type) {
1821                 rcvr1 := rcvr
1822                 if rcvr1.IsPtr() {
1823                         rcvr1 = rcvr.Elem()
1824                 }
1825                 if len(rcvr1.RParams()) > 0 {
1826                         // If rcvr has rparams, remember method as generic, which
1827                         // means we need to add a dictionary to the wrapper.
1828                         generic = true
1829                         targs := rcvr1.RParams()
1830                         for _, t := range targs {
1831                                 if t.HasShape() {
1832                                         base.Fatalf("method on type instantiated with shapes targ:%+v rcvr:%+v", t, rcvr)
1833                                 }
1834                         }
1835                 }
1836         }
1837
1838         newnam := ir.MethodSym(rcvr, method.Sym)
1839         lsym := newnam.Linksym()
1840         if newnam.Siggen() {
1841                 return lsym
1842         }
1843         newnam.SetSiggen(true)
1844
1845         // Except in quirks mode, unified IR creates its own wrappers.
1846         if base.Debug.Unified != 0 && base.Debug.UnifiedQuirks == 0 {
1847                 return lsym
1848         }
1849
1850         // For generic methods, we need to generate the wrapper even if the receiver
1851         // types are identical, because we want to add the dictionary.
1852         if !generic && types.Identical(rcvr, method.Type.Recv().Type) {
1853                 return lsym
1854         }
1855
1856         if !NeedEmit(rcvr) || rcvr.IsPtr() && !NeedEmit(rcvr.Elem()) {
1857                 return lsym
1858         }
1859
1860         base.Pos = base.AutogeneratedPos
1861         typecheck.DeclContext = ir.PEXTERN
1862
1863         tfn := ir.NewFuncType(base.Pos,
1864                 ir.NewField(base.Pos, typecheck.Lookup(".this"), nil, rcvr),
1865                 typecheck.NewFuncParams(method.Type.Params(), true),
1866                 typecheck.NewFuncParams(method.Type.Results(), false))
1867
1868         // TODO(austin): SelectorExpr may have created one or more
1869         // ir.Names for these already with a nil Func field. We should
1870         // consolidate these and always attach a Func to the Name.
1871         fn := typecheck.DeclFunc(newnam, tfn)
1872         fn.SetDupok(true)
1873
1874         nthis := ir.AsNode(tfn.Type().Recv().Nname)
1875
1876         methodrcvr := method.Type.Recv().Type
1877         indirect := rcvr.IsPtr() && rcvr.Elem() == methodrcvr
1878
1879         // generate nil pointer check for better error
1880         if indirect {
1881                 // generating wrapper from *T to T.
1882                 n := ir.NewIfStmt(base.Pos, nil, nil, nil)
1883                 n.Cond = ir.NewBinaryExpr(base.Pos, ir.OEQ, nthis, typecheck.NodNil())
1884                 call := ir.NewCallExpr(base.Pos, ir.OCALL, typecheck.LookupRuntime("panicwrap"), nil)
1885                 n.Body = []ir.Node{call}
1886                 fn.Body.Append(n)
1887         }
1888
1889         dot := typecheck.AddImplicitDots(ir.NewSelectorExpr(base.Pos, ir.OXDOT, nthis, method.Sym))
1890         // generate call
1891         // It's not possible to use a tail call when dynamic linking on ppc64le. The
1892         // bad scenario is when a local call is made to the wrapper: the wrapper will
1893         // call the implementation, which might be in a different module and so set
1894         // the TOC to the appropriate value for that module. But if it returns
1895         // directly to the wrapper's caller, nothing will reset it to the correct
1896         // value for that function.
1897         //
1898         // Disable tailcall for RegabiArgs for now. The IR does not connect the
1899         // arguments with the OTAILCALL node, and the arguments are not marshaled
1900         // correctly.
1901         if !base.Flag.Cfg.Instrumenting && rcvr.IsPtr() && methodrcvr.IsPtr() && method.Embedded != 0 && !types.IsInterfaceMethod(method.Type) && !(base.Ctxt.Arch.Name == "ppc64le" && base.Ctxt.Flag_dynlink) && !buildcfg.Experiment.RegabiArgs && !generic {
1902                 // generate tail call: adjust pointer receiver and jump to embedded method.
1903                 left := dot.X // skip final .M
1904                 if !left.Type().IsPtr() {
1905                         left = typecheck.NodAddr(left)
1906                 }
1907                 as := ir.NewAssignStmt(base.Pos, nthis, typecheck.ConvNop(left, rcvr))
1908                 fn.Body.Append(as)
1909                 fn.Body.Append(ir.NewTailCallStmt(base.Pos, method.Nname.(*ir.Name)))
1910         } else {
1911                 fn.SetWrapper(true) // ignore frame for panic+recover matching
1912                 var call *ir.CallExpr
1913
1914                 if generic && dot.X != nthis {
1915                         // TODO: for now, we don't try to generate dictionary wrappers for
1916                         // any methods involving embedded fields, because we're not
1917                         // generating the needed dictionaries in instantiateMethods.
1918                         generic = false
1919                 }
1920
1921                 if generic {
1922                         var args []ir.Node
1923                         var targs []*types.Type
1924                         if rcvr.IsPtr() {
1925                                 targs = rcvr.Elem().RParams()
1926                         } else {
1927                                 targs = rcvr.RParams()
1928                         }
1929                         if strings.HasPrefix(ir.MethodSym(orig, method.Sym).Name, ".inst.") {
1930                                 fmt.Printf("%s\n", ir.MethodSym(orig, method.Sym).Name)
1931                                 panic("multiple .inst.")
1932                         }
1933                         // The wrapper for an auto-generated pointer/non-pointer
1934                         // receiver method should share the same dictionary as the
1935                         // corresponding original (user-written) method.
1936                         baseOrig := orig
1937                         if baseOrig.IsPtr() && !method.Type.Recv().Type.IsPtr() {
1938                                 baseOrig = baseOrig.Elem()
1939                         } else if !baseOrig.IsPtr() && method.Type.Recv().Type.IsPtr() {
1940                                 baseOrig = types.NewPtr(baseOrig)
1941                         }
1942                         args = append(args, getDictionary(ir.MethodSym(baseOrig, method.Sym), targs))
1943                         if indirect {
1944                                 args = append(args, ir.NewStarExpr(base.Pos, dot.X))
1945                         } else if methodrcvr.IsPtr() && methodrcvr.Elem() == dot.X.Type() {
1946                                 // Case where method call is via a non-pointer
1947                                 // embedded field with a pointer method.
1948                                 args = append(args, typecheck.NodAddrAt(base.Pos, dot.X))
1949                         } else {
1950                                 args = append(args, dot.X)
1951                         }
1952                         args = append(args, ir.ParamNames(tfn.Type())...)
1953
1954                         // Target method uses shaped names.
1955                         targs2 := make([]*types.Type, len(targs))
1956                         for i, t := range targs {
1957                                 targs2[i] = typecheck.Shapify(t)
1958                         }
1959                         targs = targs2
1960
1961                         sym := typecheck.MakeInstName(ir.MethodSym(methodrcvr, method.Sym), targs, true)
1962                         if sym.Def == nil {
1963                                 // Currently we make sure that we have all the instantiations
1964                                 // we need by generating them all in ../noder/stencil.go:instantiateMethods
1965                                 // TODO: maybe there's a better, more incremental way to generate
1966                                 // only the instantiations we need?
1967                                 base.Fatalf("instantiation %s not found", sym.Name)
1968                         }
1969                         target := ir.AsNode(sym.Def)
1970                         call = ir.NewCallExpr(base.Pos, ir.OCALL, target, args)
1971                         // Fill-in the generic method node that was not filled in
1972                         // in instantiateMethod.
1973                         method.Nname = fn.Nname
1974                 } else {
1975                         call = ir.NewCallExpr(base.Pos, ir.OCALL, dot, nil)
1976                         call.Args = ir.ParamNames(tfn.Type())
1977                 }
1978                 call.IsDDD = tfn.Type().IsVariadic()
1979                 if method.Type.NumResults() > 0 {
1980                         ret := ir.NewReturnStmt(base.Pos, nil)
1981                         ret.Results = []ir.Node{call}
1982                         fn.Body.Append(ret)
1983                 } else {
1984                         fn.Body.Append(call)
1985                 }
1986         }
1987
1988         typecheck.FinishFuncBody()
1989         if base.Debug.DclStack != 0 {
1990                 types.CheckDclstack()
1991         }
1992
1993         typecheck.Func(fn)
1994         ir.CurFunc = fn
1995         typecheck.Stmts(fn.Body)
1996
1997         if AfterGlobalEscapeAnalysis {
1998                 inline.InlineCalls(fn)
1999                 escape.Batch([]*ir.Func{fn}, false)
2000         }
2001
2002         ir.CurFunc = nil
2003         typecheck.Target.Decls = append(typecheck.Target.Decls, fn)
2004
2005         return lsym
2006 }
2007
2008 // AfterGlobalEscapeAnalysis tracks whether package gc has already
2009 // performed the main, global escape analysis pass. If so,
2010 // methodWrapper takes responsibility for escape analyzing any
2011 // generated wrappers.
2012 var AfterGlobalEscapeAnalysis bool
2013
2014 var ZeroSize int64
2015
2016 // MarkTypeUsedInInterface marks that type t is converted to an interface.
2017 // This information is used in the linker in dead method elimination.
2018 func MarkTypeUsedInInterface(t *types.Type, from *obj.LSym) {
2019         if t.HasShape() {
2020                 // Shape types shouldn't be put in interfaces, so we shouldn't ever get here.
2021                 base.Fatalf("shape types have no methods %+v", t)
2022         }
2023         tsym := TypeLinksym(t)
2024         // Emit a marker relocation. The linker will know the type is converted
2025         // to an interface if "from" is reachable.
2026         r := obj.Addrel(from)
2027         r.Sym = tsym
2028         r.Type = objabi.R_USEIFACE
2029 }
2030
2031 // MarkUsedIfaceMethod marks that an interface method is used in the current
2032 // function. n is OCALLINTER node.
2033 func MarkUsedIfaceMethod(n *ir.CallExpr) {
2034         // skip unnamed functions (func _())
2035         if ir.CurFunc.LSym == nil {
2036                 return
2037         }
2038         dot := n.X.(*ir.SelectorExpr)
2039         ityp := dot.X.Type()
2040         tsym := TypeLinksym(ityp)
2041         r := obj.Addrel(ir.CurFunc.LSym)
2042         r.Sym = tsym
2043         // dot.Offset() is the method index * PtrSize (the offset of code pointer
2044         // in itab).
2045         midx := dot.Offset() / int64(types.PtrSize)
2046         r.Add = InterfaceMethodOffset(ityp, midx)
2047         r.Type = objabi.R_USEIFACEMETHOD
2048 }
2049
2050 // MarkUsedIfaceMethodIndex marks that that method number ix (in the AllMethods list)
2051 // of interface type ityp is used, and should be attached to lsym.
2052 func MarkUsedIfaceMethodIndex(lsym *obj.LSym, ityp *types.Type, ix int) {
2053         tsym := TypeLinksym(ityp)
2054         r := obj.Addrel(lsym)
2055         r.Sym = tsym
2056         r.Add = InterfaceMethodOffset(ityp, int64(ix))
2057         r.Type = objabi.R_USEIFACEMETHOD
2058 }
2059
2060 // getDictionary returns the dictionary for the given named generic function
2061 // or method, with the given type arguments.
2062 func getDictionary(gf *types.Sym, targs []*types.Type) ir.Node {
2063         if len(targs) == 0 {
2064                 base.Fatalf("%s should have type arguments", gf.Name)
2065         }
2066         for _, t := range targs {
2067                 if t.HasShape() {
2068                         base.Fatalf("dictionary for %s should only use concrete types: %+v", gf.Name, t)
2069                 }
2070         }
2071
2072         sym := typecheck.MakeDictName(gf, targs, true)
2073
2074         // Initialize the dictionary, if we haven't yet already.
2075         if lsym := sym.Linksym(); len(lsym.P) == 0 {
2076                 base.Fatalf("Dictionary should have already been generated: %s.%s", sym.Pkg.Path, sym.Name)
2077         }
2078
2079         // Make a node referencing the dictionary symbol.
2080         n := typecheck.NewName(sym)
2081         n.SetType(types.Types[types.TUINTPTR]) // should probably be [...]uintptr, but doesn't really matter
2082         n.SetTypecheck(1)
2083         n.Class = ir.PEXTERN
2084         sym.Def = n
2085
2086         // Return the address of the dictionary.
2087         np := typecheck.NodAddr(n)
2088         // Note: treat dictionary pointers as uintptrs, so they aren't pointers
2089         // with respect to GC. That saves on stack scanning work, write barriers, etc.
2090         // We can get away with it because dictionaries are global variables.
2091         np.SetType(types.Types[types.TUINTPTR])
2092         np.SetTypecheck(1)
2093         return np
2094 }