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