interface.go raw
1 package compiler
2
3 // This file transforms interface-related instructions (*ssa.MakeInterface,
4 // *ssa.TypeAssert, calls on interface types) to an intermediate IR form, to be
5 // lowered to the final form by the interface lowering pass. See
6 // interface-lowering.go for more details.
7
8 import (
9 "encoding/binary"
10 "fmt"
11 "go/token"
12 "go/types"
13 "strconv"
14 "strings"
15
16 "golang.org/x/tools/go/ssa"
17 "tinygo.org/x/go-llvm"
18 )
19
20 // Type kinds for basic types.
21 // They must match the constants for the Kind type in src/reflect/type.go.
22 var basicTypes = [...]uint8{
23 types.Bool: 1,
24 types.Int: 2,
25 types.Int8: 3,
26 types.Int16: 4,
27 types.Int32: 5,
28 types.Int64: 6,
29 types.Uint: 7,
30 types.Uint8: 8,
31 types.Uint16: 9,
32 types.Uint32: 10,
33 types.Uint64: 11,
34 types.Uintptr: 12,
35 types.Float32: 13,
36 types.Float64: 14,
37 types.Complex64: 15,
38 types.Complex128: 16,
39 types.String: 17, // Moxie: kind 17 is Bytes (string=[]byte unified)
40 types.UnsafePointer: 18,
41 }
42
43 // These must also match the constants for the Kind type in src/reflect/type.go.
44 const (
45 typeKindChan = 19
46 typeKindInterface = 20
47 typeKindPointer = 21
48 typeKindSlice = 22
49 typeKindArray = 23
50 typeKindSignature = 24
51 typeKindMap = 25
52 typeKindStruct = 26
53 )
54
55 // Flags stored in the first byte of the struct field byte array. Must be kept
56 // up to date with src/reflect/type.go.
57 const (
58 structFieldFlagAnonymous = 1 << iota
59 structFieldFlagHasTag
60 structFieldFlagIsExported
61 structFieldFlagIsEmbedded
62 )
63
64 type reflectChanDir int
65
66 const (
67 refRecvDir reflectChanDir = 1 << iota // <-chan
68 refSendDir // chan<-
69 refBothDir = refRecvDir | refSendDir // chan
70 )
71
72 // createMakeInterface emits the LLVM IR for the *ssa.MakeInterface instruction.
73 // It tries to put the type in the interface value, but if that's not possible,
74 // it will do an allocation of the right size and put that in the interface
75 // value field.
76 //
77 // An interface value is a {typecode, value} tuple named runtime._interface.
78 func (b *builder) createMakeInterface(val llvm.Value, typ types.Type, pos token.Pos) llvm.Value {
79 itfValue := b.emitPointerPack([]llvm.Value{val})
80 itfType := b.getTypeCode(typ)
81 itf := llvm.Undef(b.getLLVMRuntimeType("_interface"))
82 itf = b.CreateInsertValue(itf, itfType, 0, "")
83 itf = b.CreateInsertValue(itf, itfValue, 1, "")
84 return itf
85 }
86
87 // extractValueFromInterface extract the value from an interface value
88 // (runtime._interface) under the assumption that it is of the type given in
89 // llvmType. The behavior is undefined if the interface is nil or llvmType
90 // doesn't match the underlying type of the interface.
91 func (b *builder) extractValueFromInterface(itf llvm.Value, llvmType llvm.Type) llvm.Value {
92 valuePtr := b.CreateExtractValue(itf, 1, "typeassert.value.ptr")
93 return b.emitPointerUnpack(valuePtr, []llvm.Type{llvmType})[0]
94 }
95
96 func (c *compilerContext) pkgPathPtr(pkgpath string) llvm.Value {
97 pkgpathName := "reflect/types.type.pkgpath.empty"
98 if pkgpath != "" {
99 pkgpathName = "reflect/types.type.pkgpath:" + pkgpath
100 }
101
102 pkgpathGlobal := c.mod.NamedGlobal(pkgpathName)
103 if pkgpathGlobal.IsNil() {
104 pkgpathInitializer := c.ctx.ConstString(pkgpath+"\x00", false)
105 pkgpathGlobal = llvm.AddGlobal(c.mod, pkgpathInitializer.Type(), pkgpathName)
106 pkgpathGlobal.SetInitializer(pkgpathInitializer)
107 pkgpathGlobal.SetAlignment(1)
108 pkgpathGlobal.SetUnnamedAddr(true)
109 pkgpathGlobal.SetLinkage(llvm.LinkOnceODRLinkage)
110 pkgpathGlobal.SetGlobalConstant(true)
111 }
112 pkgPathPtr := llvm.ConstGEP(pkgpathGlobal.GlobalValueType(), pkgpathGlobal, []llvm.Value{
113 llvm.ConstInt(c.ctx.Int32Type(), 0, false),
114 llvm.ConstInt(c.ctx.Int32Type(), 0, false),
115 })
116
117 return pkgPathPtr
118 }
119
120 // getTypeCode returns a reference to a type code.
121 // A type code is a pointer to a constant global that describes the type.
122 // This function returns a pointer to the 'kind' field (which might not be the
123 // first field in the struct).
124 func (c *compilerContext) getTypeCode(typ types.Type) llvm.Value {
125 // Resolve alias types: alias types are resolved at compile time.
126 typ = types.Unalias(typ)
127
128 ms := c.program.MethodSets.MethodSet(typ)
129 hasMethodSet := ms.Len() != 0
130 _, isInterface := typ.Underlying().(*types.Interface)
131 if isInterface {
132 hasMethodSet = false
133 }
134
135 // As defined in https://pkg.go.dev/reflect#Type:
136 // NumMethod returns the number of methods accessible using Method.
137 // For a non-interface type, it returns the number of exported methods.
138 // For an interface type, it returns the number of exported and unexported methods.
139 var numMethods int
140 for i := 0; i < ms.Len(); i++ {
141 if isInterface || ms.At(i).Obj().Exported() {
142 numMethods++
143 }
144 }
145
146 // Short-circuit all the global pointer logic here for pointers to pointers.
147 if typ, ok := typ.(*types.Pointer); ok {
148 if _, ok := typ.Elem().(*types.Pointer); ok {
149 // For a pointer to a pointer, we just increase the pointer by 1
150 ptr := c.getTypeCode(typ.Elem())
151 // if the type is already *****T or higher, we can't make it.
152 if typstr := typ.String(); strings.HasPrefix(typstr, "*****") {
153 c.addError(token.NoPos, fmt.Sprintf("too many levels of pointers for typecode: %s", typstr))
154 }
155 return llvm.ConstGEP(c.ctx.Int8Type(), ptr, []llvm.Value{
156 llvm.ConstInt(c.ctx.Int32Type(), 1, false),
157 })
158 }
159 }
160
161 typeCodeName, isLocal := getTypeCodeName(typ)
162 globalName := "reflect/types.type:" + typeCodeName
163 var global llvm.Value
164 if isLocal {
165 // This type is a named type inside a function, like this:
166 //
167 // func foo() any {
168 // type named int
169 // return named(0)
170 // }
171 if obj := c.interfaceTypes.At(typ); obj != nil {
172 global = obj.(llvm.Value)
173 }
174 } else {
175 // Regular type (named or otherwise).
176 global = c.mod.NamedGlobal(globalName)
177 }
178 if global.IsNil() {
179 var typeFields []llvm.Value
180 // Define the type fields. These must match the structs in
181 // src/reflect/type.go (ptrType, arrayType, etc). See the comment at the
182 // top of src/reflect/type.go for more information on the layout of these structs.
183 typeFieldTypes := []*types.Var{
184 types.NewVar(token.NoPos, nil, "kind", types.Typ[types.Int8]),
185 }
186 switch typ := typ.(type) {
187 case *types.Basic:
188 typeFieldTypes = append(typeFieldTypes,
189 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
190 )
191 case *types.Named:
192 name := typ.Obj().Name()
193 var pkgname string
194 if pkg := typ.Obj().Pkg(); pkg != nil {
195 pkgname = pkg.Name()
196 }
197 typeFieldTypes = append(typeFieldTypes,
198 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
199 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
200 types.NewVar(token.NoPos, nil, "underlying", types.Typ[types.UnsafePointer]),
201 types.NewVar(token.NoPos, nil, "pkgpath", types.Typ[types.UnsafePointer]),
202 types.NewVar(token.NoPos, nil, "name", types.NewArray(types.Typ[types.Int8], int64(len(pkgname)+1+len(name)+1))),
203 )
204 case *types.Chan:
205 typeFieldTypes = append(typeFieldTypes,
206 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]), // reuse for select chan direction
207 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
208 types.NewVar(token.NoPos, nil, "elementType", types.Typ[types.UnsafePointer]),
209 )
210 case *types.Slice:
211 typeFieldTypes = append(typeFieldTypes,
212 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
213 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
214 types.NewVar(token.NoPos, nil, "elementType", types.Typ[types.UnsafePointer]),
215 )
216 case *types.Pointer:
217 typeFieldTypes = append(typeFieldTypes,
218 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
219 types.NewVar(token.NoPos, nil, "elementType", types.Typ[types.UnsafePointer]),
220 )
221 case *types.Array:
222 typeFieldTypes = append(typeFieldTypes,
223 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
224 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
225 types.NewVar(token.NoPos, nil, "elementType", types.Typ[types.UnsafePointer]),
226 types.NewVar(token.NoPos, nil, "length", types.Typ[types.Uintptr]),
227 types.NewVar(token.NoPos, nil, "sliceOf", types.Typ[types.UnsafePointer]),
228 )
229 case *types.Map:
230 typeFieldTypes = append(typeFieldTypes,
231 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
232 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
233 types.NewVar(token.NoPos, nil, "elementType", types.Typ[types.UnsafePointer]),
234 types.NewVar(token.NoPos, nil, "keyType", types.Typ[types.UnsafePointer]),
235 )
236 case *types.Struct:
237 typeFieldTypes = append(typeFieldTypes,
238 types.NewVar(token.NoPos, nil, "numMethods", types.Typ[types.Uint16]),
239 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
240 types.NewVar(token.NoPos, nil, "pkgpath", types.Typ[types.UnsafePointer]),
241 types.NewVar(token.NoPos, nil, "size", types.Typ[types.Uint32]),
242 types.NewVar(token.NoPos, nil, "numFields", types.Typ[types.Uint16]),
243 types.NewVar(token.NoPos, nil, "fields", types.NewArray(c.getRuntimeType("structField"), int64(typ.NumFields()))),
244 )
245 case *types.Interface:
246 typeFieldTypes = append(typeFieldTypes,
247 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
248 )
249 // TODO: methods
250 case *types.Signature:
251 typeFieldTypes = append(typeFieldTypes,
252 types.NewVar(token.NoPos, nil, "ptrTo", types.Typ[types.UnsafePointer]),
253 )
254 // TODO: signature params and return values
255 }
256 if hasMethodSet {
257 // This method set is appended at the start of the struct. It is
258 // removed in the interface lowering pass.
259 // TODO: don't remove these and instead do what upstream Go is doing
260 // instead. See: https://research.swtch.com/interfaces. This can
261 // likely be optimized in LLVM using
262 // https://llvm.org/docs/TypeMetadata.html.
263 typeFieldTypes = append([]*types.Var{
264 types.NewVar(token.NoPos, nil, "methodSet", types.Typ[types.UnsafePointer]),
265 }, typeFieldTypes...)
266 }
267 globalType := types.NewStruct(typeFieldTypes, nil)
268 global = llvm.AddGlobal(c.mod, c.getLLVMType(globalType), globalName)
269 if isLocal {
270 c.interfaceTypes.Set(typ, global)
271 }
272 metabyte := getTypeKind(typ)
273
274 // Precompute these so we don't have to calculate them at runtime.
275 if types.Comparable(typ) {
276 metabyte |= 1 << 6
277 }
278
279 if hashmapIsBinaryKey(typ) {
280 metabyte |= 1 << 7
281 }
282
283 switch typ := typ.(type) {
284 case *types.Basic:
285 typeFields = []llvm.Value{c.getTypeCode(types.NewPointer(typ))}
286 case *types.Named:
287 name := typ.Obj().Name()
288 var pkgpath string
289 var pkgname string
290 if pkg := typ.Obj().Pkg(); pkg != nil {
291 pkgpath = pkg.Path()
292 pkgname = pkg.Name()
293 }
294 pkgPathPtr := c.pkgPathPtr(pkgpath)
295 typeFields = []llvm.Value{
296 llvm.ConstInt(c.ctx.Int16Type(), uint64(numMethods), false), // numMethods
297 c.getTypeCode(types.NewPointer(typ)), // ptrTo
298 c.getTypeCode(typ.Underlying()), // underlying
299 pkgPathPtr, // pkgpath pointer
300 c.ctx.ConstString(pkgname+"."+name+"\x00", false), // name
301 }
302 metabyte |= 1 << 5 // "named" flag
303 case *types.Chan:
304 var dir reflectChanDir
305 switch typ.Dir() {
306 case types.SendRecv:
307 dir = refBothDir
308 case types.RecvOnly:
309 dir = refRecvDir
310 case types.SendOnly:
311 dir = refSendDir
312 }
313
314 typeFields = []llvm.Value{
315 llvm.ConstInt(c.ctx.Int16Type(), uint64(dir), false), // actually channel direction
316 c.getTypeCode(types.NewPointer(typ)), // ptrTo
317 c.getTypeCode(typ.Elem()), // elementType
318 }
319 case *types.Slice:
320 typeFields = []llvm.Value{
321 llvm.ConstInt(c.ctx.Int16Type(), 0, false), // numMethods
322 c.getTypeCode(types.NewPointer(typ)), // ptrTo
323 c.getTypeCode(typ.Elem()), // elementType
324 }
325 case *types.Pointer:
326 typeFields = []llvm.Value{
327 llvm.ConstInt(c.ctx.Int16Type(), uint64(numMethods), false), // numMethods
328 c.getTypeCode(typ.Elem()),
329 }
330 case *types.Array:
331 typeFields = []llvm.Value{
332 llvm.ConstInt(c.ctx.Int16Type(), 0, false), // numMethods
333 c.getTypeCode(types.NewPointer(typ)), // ptrTo
334 c.getTypeCode(typ.Elem()), // elementType
335 llvm.ConstInt(c.uintptrType, uint64(typ.Len()), false), // length
336 c.getTypeCode(types.NewSlice(typ.Elem())), // slicePtr
337 }
338 case *types.Map:
339 typeFields = []llvm.Value{
340 llvm.ConstInt(c.ctx.Int16Type(), 0, false), // numMethods
341 c.getTypeCode(types.NewPointer(typ)), // ptrTo
342 c.getTypeCode(typ.Elem()), // elem
343 c.getTypeCode(typ.Key()), // key
344 }
345 case *types.Struct:
346 var pkgpath string
347 if typ.NumFields() > 0 {
348 if pkg := typ.Field(0).Pkg(); pkg != nil {
349 pkgpath = pkg.Path()
350 }
351 }
352 pkgPathPtr := c.pkgPathPtr(pkgpath)
353
354 llvmStructType := c.getLLVMType(typ)
355 size := c.targetData.TypeStoreSize(llvmStructType)
356 typeFields = []llvm.Value{
357 llvm.ConstInt(c.ctx.Int16Type(), uint64(numMethods), false), // numMethods
358 c.getTypeCode(types.NewPointer(typ)), // ptrTo
359 pkgPathPtr,
360 llvm.ConstInt(c.ctx.Int32Type(), uint64(size), false), // size
361 llvm.ConstInt(c.ctx.Int16Type(), uint64(typ.NumFields()), false), // numFields
362 }
363 structFieldType := c.getLLVMRuntimeType("structField")
364
365 var fields []llvm.Value
366 for i := 0; i < typ.NumFields(); i++ {
367 field := typ.Field(i)
368 offset := c.targetData.ElementOffset(llvmStructType, i)
369 var flags uint8
370 if field.Anonymous() {
371 flags |= structFieldFlagAnonymous
372 }
373 if typ.Tag(i) != "" {
374 flags |= structFieldFlagHasTag
375 }
376 if token.IsExported(field.Name()) {
377 flags |= structFieldFlagIsExported
378 }
379 if field.Embedded() {
380 flags |= structFieldFlagIsEmbedded
381 }
382
383 var offsBytes [binary.MaxVarintLen32]byte
384 offLen := binary.PutUvarint(offsBytes[:], offset)
385
386 data := string(flags) + string(offsBytes[:offLen]) + field.Name() + "\x00"
387 if typ.Tag(i) != "" {
388 if len(typ.Tag(i)) > 0xff {
389 c.addError(field.Pos(), fmt.Sprintf("struct tag is %d bytes which is too long, max is 255", len(typ.Tag(i))))
390 }
391 data += string([]byte{byte(len(typ.Tag(i)))}) + typ.Tag(i)
392 }
393 dataInitializer := c.ctx.ConstString(data, false)
394 dataGlobal := llvm.AddGlobal(c.mod, dataInitializer.Type(), globalName+"."+field.Name())
395 dataGlobal.SetInitializer(dataInitializer)
396 dataGlobal.SetAlignment(1)
397 dataGlobal.SetUnnamedAddr(true)
398 dataGlobal.SetLinkage(llvm.InternalLinkage)
399 dataGlobal.SetGlobalConstant(true)
400 fieldType := c.getTypeCode(field.Type())
401 fields = append(fields, llvm.ConstNamedStruct(structFieldType, []llvm.Value{
402 fieldType,
403 llvm.ConstGEP(dataGlobal.GlobalValueType(), dataGlobal, []llvm.Value{
404 llvm.ConstInt(c.ctx.Int32Type(), 0, false),
405 llvm.ConstInt(c.ctx.Int32Type(), 0, false),
406 }),
407 }))
408 }
409 typeFields = append(typeFields, llvm.ConstArray(structFieldType, fields))
410 case *types.Interface:
411 typeFields = []llvm.Value{c.getTypeCode(types.NewPointer(typ))}
412 // TODO: methods
413 case *types.Signature:
414 typeFields = []llvm.Value{c.getTypeCode(types.NewPointer(typ))}
415 // TODO: params, return values, etc
416 }
417 // Prepend metadata byte.
418 typeFields = append([]llvm.Value{
419 llvm.ConstInt(c.ctx.Int8Type(), uint64(metabyte), false),
420 }, typeFields...)
421 if hasMethodSet {
422 typeFields = append([]llvm.Value{
423 c.getTypeMethodSet(typ),
424 }, typeFields...)
425 }
426 alignment := c.targetData.TypeAllocSize(c.dataPtrType)
427 if alignment < 4 {
428 alignment = 4
429 }
430 globalValue := c.ctx.ConstStruct(typeFields, false)
431 global.SetInitializer(globalValue)
432 if isLocal {
433 global.SetLinkage(llvm.InternalLinkage)
434 } else {
435 global.SetLinkage(llvm.LinkOnceODRLinkage)
436 }
437 global.SetGlobalConstant(true)
438 global.SetAlignment(int(alignment))
439 if c.Debug {
440 file := c.getDIFile("<Go type>")
441 diglobal := c.dibuilder.CreateGlobalVariableExpression(file, llvm.DIGlobalVariableExpression{
442 Name: "type " + typ.String(),
443 File: file,
444 Line: 1,
445 Type: c.getDIType(globalType),
446 LocalToUnit: false,
447 Expr: c.dibuilder.CreateExpression(nil),
448 AlignInBits: uint32(alignment * 8),
449 })
450 global.AddMetadata(0, diglobal)
451 }
452 }
453 offset := uint64(0)
454 if hasMethodSet {
455 // The pointer to the method set is always the first element of the
456 // global (if there is a method set). However, the pointer we return
457 // should point to the 'kind' field not the method set.
458 offset = 1
459 }
460 return llvm.ConstGEP(global.GlobalValueType(), global, []llvm.Value{
461 llvm.ConstInt(c.ctx.Int32Type(), 0, false),
462 llvm.ConstInt(c.ctx.Int32Type(), offset, false),
463 })
464 }
465
466 // getTypeKind returns the type kind for the given type, as defined by
467 // reflect.Kind.
468 func getTypeKind(t types.Type) uint8 {
469 switch t := t.Underlying().(type) {
470 case *types.Basic:
471 return basicTypes[t.Kind()]
472 case *types.Chan:
473 return typeKindChan
474 case *types.Interface:
475 return typeKindInterface
476 case *types.Pointer:
477 return typeKindPointer
478 case *types.Slice:
479 // Moxie: []byte reports as String kind (string=[]byte unification).
480 if b, ok := t.Elem().(*types.Basic); ok && b.Kind() == types.Byte {
481 return basicTypes[types.String]
482 }
483 return typeKindSlice
484 case *types.Array:
485 return typeKindArray
486 case *types.Signature:
487 return typeKindSignature
488 case *types.Map:
489 return typeKindMap
490 case *types.Struct:
491 return typeKindStruct
492 default:
493 panic("unknown type")
494 }
495 }
496
497 var basicTypeNames = [...]string{
498 types.Bool: "bool",
499 types.Int: "int",
500 types.Int8: "int8",
501 types.Int16: "int16",
502 types.Int32: "int32",
503 types.Int64: "int64",
504 types.Uint: "uint",
505 types.Uint8: "uint8",
506 types.Uint16: "uint16",
507 types.Uint32: "uint32",
508 types.Uint64: "uint64",
509 types.Uintptr: "uintptr",
510 types.Float32: "float32",
511 types.Float64: "float64",
512 types.Complex64: "complex64",
513 types.Complex128: "complex128",
514 types.String: "bytes", // Moxie: unified string=[]byte type
515 types.UnsafePointer: "unsafe.Pointer",
516 }
517
518 // getTypeCodeName returns a name for this type that can be used in the
519 // interface lowering pass to assign type codes as expected by the reflect
520 // package. See getTypeCodeNum.
521 func getTypeCodeName(t types.Type) (string, bool) {
522 switch t := types.Unalias(t).(type) {
523 case *types.Named:
524 if t.Obj().Parent() != t.Obj().Pkg().Scope() {
525 return "named:" + t.String() + "$local", true
526 }
527 return "named:" + t.String(), false
528 case *types.Array:
529 s, isLocal := getTypeCodeName(t.Elem())
530 return "array:" + strconv.FormatInt(t.Len(), 10) + ":" + s, isLocal
531 case *types.Basic:
532 return "basic:" + basicTypeNames[t.Kind()], false
533 case *types.Chan:
534 s, isLocal := getTypeCodeName(t.Elem())
535 var dir string
536 switch t.Dir() {
537 case types.SendOnly:
538 dir = "s:"
539 case types.RecvOnly:
540 dir = "r:"
541 case types.SendRecv:
542 dir = "sr:"
543 }
544
545 return "chan:" + dir + s, isLocal
546 case *types.Interface:
547 isLocal := false
548 methods := make([]string, t.NumMethods())
549 for i := 0; i < t.NumMethods(); i++ {
550 name := t.Method(i).Name()
551 if !token.IsExported(name) {
552 name = t.Method(i).Pkg().Path() + "." + name
553 }
554 s, local := getTypeCodeName(t.Method(i).Type())
555 if local {
556 isLocal = true
557 }
558 methods[i] = name + ":" + s
559 }
560 return "interface:" + "{" + strings.Join(methods, ",") + "}", isLocal
561 case *types.Map:
562 keyType, keyLocal := getTypeCodeName(t.Key())
563 elemType, elemLocal := getTypeCodeName(t.Elem())
564 return "map:" + "{" + keyType + "," + elemType + "}", keyLocal || elemLocal
565 case *types.Pointer:
566 s, isLocal := getTypeCodeName(t.Elem())
567 return "pointer:" + s, isLocal
568 case *types.Signature:
569 isLocal := false
570 params := make([]string, t.Params().Len())
571 for i := 0; i < t.Params().Len(); i++ {
572 s, local := getTypeCodeName(t.Params().At(i).Type())
573 if local {
574 isLocal = true
575 }
576 params[i] = s
577 }
578 results := make([]string, t.Results().Len())
579 for i := 0; i < t.Results().Len(); i++ {
580 s, local := getTypeCodeName(t.Results().At(i).Type())
581 if local {
582 isLocal = true
583 }
584 results[i] = s
585 }
586 return "func:" + "{" + strings.Join(params, ",") + "}{" + strings.Join(results, ",") + "}", isLocal
587 case *types.Slice:
588 // Moxie: []byte uses the unified bytes type code name.
589 if b, ok := t.Elem().(*types.Basic); ok && b.Kind() == types.Byte {
590 return "basic:bytes", false
591 }
592 s, isLocal := getTypeCodeName(t.Elem())
593 return "slice:" + s, isLocal
594 case *types.Struct:
595 elems := make([]string, t.NumFields())
596 isLocal := false
597 for i := 0; i < t.NumFields(); i++ {
598 embedded := ""
599 if t.Field(i).Embedded() {
600 embedded = "#"
601 }
602 s, local := getTypeCodeName(t.Field(i).Type())
603 if local {
604 isLocal = true
605 }
606 elems[i] = embedded + t.Field(i).Name() + ":" + s
607 if t.Tag(i) != "" {
608 elems[i] += "`" + t.Tag(i) + "`"
609 }
610 }
611 return "struct:" + "{" + strings.Join(elems, ",") + "}", isLocal
612 default:
613 panic("unknown type: " + t.String())
614 }
615 }
616
617 // getTypeMethodSet returns a reference (GEP) to a global method set. This
618 // method set should be unreferenced after the interface lowering pass.
619 func (c *compilerContext) getTypeMethodSet(typ types.Type) llvm.Value {
620 globalName := typ.String() + "$methodset"
621 global := c.mod.NamedGlobal(globalName)
622 if global.IsNil() {
623 ms := c.program.MethodSets.MethodSet(typ)
624
625 // Create method set.
626 var signatures, wrappers []llvm.Value
627 for i := 0; i < ms.Len(); i++ {
628 method := ms.At(i)
629 signatureGlobal := c.getMethodSignature(method.Obj().(*types.Func))
630 signatures = append(signatures, signatureGlobal)
631 fn := c.program.MethodValue(method)
632 llvmFnType, llvmFn := c.getFunction(fn)
633 if llvmFn.IsNil() {
634 // compiler error, so panic
635 panic("cannot find function: " + c.getFunctionInfo(fn).linkName)
636 }
637 wrapper := c.getInterfaceInvokeWrapper(fn, llvmFnType, llvmFn)
638 wrappers = append(wrappers, wrapper)
639 }
640
641 // Construct global value.
642 globalValue := c.ctx.ConstStruct([]llvm.Value{
643 llvm.ConstInt(c.uintptrType, uint64(ms.Len()), false),
644 llvm.ConstArray(c.dataPtrType, signatures),
645 c.ctx.ConstStruct(wrappers, false),
646 }, false)
647 global = llvm.AddGlobal(c.mod, globalValue.Type(), globalName)
648 global.SetInitializer(globalValue)
649 global.SetGlobalConstant(true)
650 global.SetUnnamedAddr(true)
651 global.SetLinkage(llvm.LinkOnceODRLinkage)
652 }
653 return global
654 }
655
656 // getMethodSignatureName returns a unique name (that can be used as the name of
657 // a global) for the given method.
658 func (c *compilerContext) getMethodSignatureName(method *types.Func) string {
659 signature := methodSignature(method)
660 var globalName string
661 if token.IsExported(method.Name()) {
662 globalName = "reflect/methods." + signature
663 } else {
664 globalName = method.Type().(*types.Signature).Recv().Pkg().Path() + ".$methods." + signature
665 }
666 return globalName
667 }
668
669 // getMethodSignature returns a global variable which is a reference to an
670 // external *i8 indicating the indicating the signature of this method. It is
671 // used during the interface lowering pass.
672 func (c *compilerContext) getMethodSignature(method *types.Func) llvm.Value {
673 globalName := c.getMethodSignatureName(method)
674 signatureGlobal := c.mod.NamedGlobal(globalName)
675 if signatureGlobal.IsNil() {
676 // TODO: put something useful in these globals, such as the method
677 // signature. Useful to one day implement reflect.Value.Method(n).
678 signatureGlobal = llvm.AddGlobal(c.mod, c.ctx.Int8Type(), globalName)
679 signatureGlobal.SetInitializer(llvm.ConstInt(c.ctx.Int8Type(), 0, false))
680 signatureGlobal.SetLinkage(llvm.LinkOnceODRLinkage)
681 signatureGlobal.SetGlobalConstant(true)
682 signatureGlobal.SetAlignment(1)
683 }
684 return signatureGlobal
685 }
686
687 // createTypeAssert will emit the code for a typeassert, used in if statements
688 // and in type switches (Go SSA does not have type switches, only if/else
689 // chains). Note that even though the Go SSA does not contain type switches,
690 // LLVM will recognize the pattern and make it a real switch in many cases.
691 //
692 // Type asserts on concrete types are trivial: just compare type numbers. Type
693 // asserts on interfaces are more difficult, see the comments in the function.
694 func (b *builder) createTypeAssert(expr *ssa.TypeAssert) llvm.Value {
695 itf := b.getValue(expr.X, getPos(expr))
696 assertedType := b.getLLVMType(expr.AssertedType)
697
698 actualTypeNum := b.CreateExtractValue(itf, 0, "interface.type")
699 commaOk := llvm.Value{}
700
701 if intf, ok := expr.AssertedType.Underlying().(*types.Interface); ok {
702 if intf.Empty() {
703 // intf is the empty interface => no methods
704 // This type assertion always succeeds, so we can just set commaOk to true.
705 commaOk = llvm.ConstInt(b.ctx.Int1Type(), 1, true)
706 } else {
707 // Type assert on interface type with methods.
708 // This is a call to an interface type assert function.
709 // The interface lowering pass will define this function by filling it
710 // with a type switch over all concrete types that implement this
711 // interface, and returning whether it's one of the matched types.
712 // This is very different from how interface asserts are implemented in
713 // the main Go compiler, where the runtime checks whether the type
714 // implements each method of the interface. See:
715 // https://research.swtch.com/interfaces
716 fn := b.getInterfaceImplementsFunc(expr.AssertedType)
717 commaOk = b.CreateCall(fn.GlobalValueType(), fn, []llvm.Value{actualTypeNum}, "")
718 }
719 } else {
720 name, _ := getTypeCodeName(expr.AssertedType)
721 globalName := "reflect/types.typeid:" + name
722 assertedTypeCodeGlobal := b.mod.NamedGlobal(globalName)
723 if assertedTypeCodeGlobal.IsNil() {
724 // Create a new typecode global.
725 assertedTypeCodeGlobal = llvm.AddGlobal(b.mod, b.ctx.Int8Type(), globalName)
726 assertedTypeCodeGlobal.SetGlobalConstant(true)
727 }
728 // Type assert on concrete type.
729 // Call runtime.typeAssert, which will be lowered to a simple icmp or
730 // const false in the interface lowering pass.
731 commaOk = b.createRuntimeCall("typeAssert", []llvm.Value{actualTypeNum, assertedTypeCodeGlobal}, "typecode")
732 }
733
734 // Add 2 new basic blocks (that should get optimized away): one for the
735 // 'ok' case and one for all instructions following this type assert.
736 // This is necessary because we need to insert the casted value or the
737 // nil value based on whether the assert was successful. Casting before
738 // this check tells LLVM that it can use this value and may
739 // speculatively dereference pointers before the check. This can lead to
740 // a miscompilation resulting in a segfault at runtime.
741 // Additionally, this is even required by the Go spec: a failed
742 // typeassert should return a zero value, not an incorrectly casted
743 // value.
744
745 prevBlock := b.GetInsertBlock()
746 okBlock := b.insertBasicBlock("typeassert.ok")
747 nextBlock := b.insertBasicBlock("typeassert.next")
748 b.currentBlockInfo.exit = nextBlock // adjust outgoing block for phi nodes
749 b.CreateCondBr(commaOk, okBlock, nextBlock)
750
751 // Retrieve the value from the interface if the type assert was
752 // successful.
753 b.SetInsertPointAtEnd(okBlock)
754 var valueOk llvm.Value
755 if _, ok := expr.AssertedType.Underlying().(*types.Interface); ok {
756 // Type assert on interface type. Easy: just return the same
757 // interface value.
758 valueOk = itf
759 } else {
760 // Type assert on concrete type. Extract the underlying type from
761 // the interface (but only after checking it matches).
762 valueOk = b.extractValueFromInterface(itf, assertedType)
763 }
764 b.CreateBr(nextBlock)
765
766 // Continue after the if statement.
767 b.SetInsertPointAtEnd(nextBlock)
768 phi := b.CreatePHI(assertedType, "typeassert.value")
769 phi.AddIncoming([]llvm.Value{llvm.ConstNull(assertedType), valueOk}, []llvm.BasicBlock{prevBlock, okBlock})
770
771 if expr.CommaOk {
772 tuple := b.ctx.ConstStruct([]llvm.Value{llvm.Undef(assertedType), llvm.Undef(b.ctx.Int1Type())}, false) // create empty tuple
773 tuple = b.CreateInsertValue(tuple, phi, 0, "") // insert value
774 tuple = b.CreateInsertValue(tuple, commaOk, 1, "") // insert 'comma ok' boolean
775 return tuple
776 } else {
777 // This is kind of dirty as the branch above becomes mostly useless,
778 // but hopefully this gets optimized away.
779 b.createRuntimeCall("interfaceTypeAssert", []llvm.Value{commaOk}, "")
780 return phi
781 }
782 }
783
784 // getMethodsString returns a string to be used in the "moxie-methods" string
785 // attribute for interface functions.
786 func (c *compilerContext) getMethodsString(itf *types.Interface) string {
787 methods := make([]string, itf.NumMethods())
788 for i := range methods {
789 methods[i] = c.getMethodSignatureName(itf.Method(i))
790 }
791 return strings.Join(methods, "; ")
792 }
793
794 // getInterfaceImplementsFunc returns a declared function that works as a type
795 // switch. The interface lowering pass will define this function.
796 func (c *compilerContext) getInterfaceImplementsFunc(assertedType types.Type) llvm.Value {
797 s, _ := getTypeCodeName(assertedType.Underlying())
798 fnName := s + ".$typeassert"
799 llvmFn := c.mod.NamedFunction(fnName)
800 if llvmFn.IsNil() {
801 llvmFnType := llvm.FunctionType(c.ctx.Int1Type(), []llvm.Type{c.dataPtrType}, false)
802 llvmFn = llvm.AddFunction(c.mod, fnName, llvmFnType)
803 c.addStandardDeclaredAttributes(llvmFn)
804 methods := c.getMethodsString(assertedType.Underlying().(*types.Interface))
805 llvmFn.AddFunctionAttr(c.ctx.CreateStringAttribute("moxie-methods", methods))
806 }
807 return llvmFn
808 }
809
810 // getInvokeFunction returns the thunk to call the given interface method. The
811 // thunk is declared, not defined: it will be defined by the interface lowering
812 // pass.
813 func (c *compilerContext) getInvokeFunction(instr *ssa.CallCommon) llvm.Value {
814 s, _ := getTypeCodeName(instr.Value.Type().Underlying())
815 fnName := s + "." + instr.Method.Name() + "$invoke"
816 llvmFn := c.mod.NamedFunction(fnName)
817 if llvmFn.IsNil() {
818 sig := instr.Method.Type().(*types.Signature)
819 var paramTuple []*types.Var
820 for i := 0; i < sig.Params().Len(); i++ {
821 paramTuple = append(paramTuple, sig.Params().At(i))
822 }
823 paramTuple = append(paramTuple, types.NewVar(token.NoPos, nil, "$typecode", types.Typ[types.UnsafePointer]))
824 llvmFnType := c.getLLVMFunctionType(types.NewSignature(sig.Recv(), types.NewTuple(paramTuple...), sig.Results(), false))
825 llvmFn = llvm.AddFunction(c.mod, fnName, llvmFnType)
826 c.addStandardDeclaredAttributes(llvmFn)
827 llvmFn.AddFunctionAttr(c.ctx.CreateStringAttribute("moxie-invoke", c.getMethodSignatureName(instr.Method)))
828 methods := c.getMethodsString(instr.Value.Type().Underlying().(*types.Interface))
829 llvmFn.AddFunctionAttr(c.ctx.CreateStringAttribute("moxie-methods", methods))
830 }
831 return llvmFn
832 }
833
834 // getInterfaceInvokeWrapper returns a wrapper for the given method so it can be
835 // invoked from an interface. The wrapper takes in a pointer to the underlying
836 // value, dereferences or unpacks it if necessary, and calls the real method.
837 // If the method to wrap has a pointer receiver, no wrapping is necessary and
838 // the function is returned directly.
839 func (c *compilerContext) getInterfaceInvokeWrapper(fn *ssa.Function, llvmFnType llvm.Type, llvmFn llvm.Value) llvm.Value {
840 wrapperName := llvmFn.Name() + "$invoke"
841 wrapper := c.mod.NamedFunction(wrapperName)
842 if !wrapper.IsNil() {
843 // Wrapper already created. Return it directly.
844 return wrapper
845 }
846
847 // Get the expanded receiver type.
848 receiverType := c.getLLVMType(fn.Signature.Recv().Type())
849 var expandedReceiverType []llvm.Type
850 for _, info := range c.expandFormalParamType(receiverType, "", nil) {
851 expandedReceiverType = append(expandedReceiverType, info.llvmType)
852 }
853
854 // Does this method even need any wrapping?
855 if len(expandedReceiverType) == 1 && receiverType.TypeKind() == llvm.PointerTypeKind {
856 // Nothing to wrap.
857 // Casting a function signature to a different signature and calling it
858 // with a receiver pointer bitcasted to *i8 (as done in calls on an
859 // interface) is hopefully a safe (defined) operation.
860 return llvmFn
861 }
862
863 // create wrapper function
864 paramTypes := append([]llvm.Type{c.dataPtrType}, llvmFnType.ParamTypes()[len(expandedReceiverType):]...)
865 wrapFnType := llvm.FunctionType(llvmFnType.ReturnType(), paramTypes, false)
866 wrapper = llvm.AddFunction(c.mod, wrapperName, wrapFnType)
867 c.addStandardAttributes(wrapper)
868
869 wrapper.SetLinkage(llvm.LinkOnceODRLinkage)
870 wrapper.SetUnnamedAddr(true)
871
872 // Create a new builder just to create this wrapper.
873 b := builder{
874 compilerContext: c,
875 Builder: c.ctx.NewBuilder(),
876 }
877 defer b.Builder.Dispose()
878
879 // add debug info if needed
880 if c.Debug {
881 pos := c.program.Fset.Position(fn.Pos())
882 difunc := c.attachDebugInfoRaw(fn, wrapper, "$invoke", pos.Filename, pos.Line)
883 b.SetCurrentDebugLocation(uint(pos.Line), uint(pos.Column), difunc, llvm.Metadata{})
884 }
885
886 // set up IR builder
887 block := b.ctx.AddBasicBlock(wrapper, "entry")
888 b.SetInsertPointAtEnd(block)
889
890 receiverValue := b.emitPointerUnpack(wrapper.Param(0), []llvm.Type{receiverType})[0]
891 params := append(b.expandFormalParam(receiverValue), wrapper.Params()[1:]...)
892 if llvmFnType.ReturnType().TypeKind() == llvm.VoidTypeKind {
893 b.CreateCall(llvmFnType, llvmFn, params, "")
894 b.CreateRetVoid()
895 } else {
896 ret := b.CreateCall(llvmFnType, llvmFn, params, "ret")
897 b.CreateRet(ret)
898 }
899
900 return wrapper
901 }
902
903 // methodSignature creates a readable version of a method signature (including
904 // the function name, excluding the receiver name). This string is used
905 // internally to match interfaces and to call the correct method on an
906 // interface. Examples:
907 //
908 // String() string
909 // Read([]byte) (int, error)
910 func methodSignature(method *types.Func) string {
911 return method.Name() + signature(method.Type().(*types.Signature))
912 }
913
914 // Make a readable version of a function (pointer) signature.
915 // Examples:
916 //
917 // () string
918 // (string, int) (int, error)
919 func signature(sig *types.Signature) string {
920 s := ""
921 if sig.Params().Len() == 0 {
922 s += "()"
923 } else {
924 s += "("
925 for i := 0; i < sig.Params().Len(); i++ {
926 if i > 0 {
927 s += ", "
928 }
929 s += typestring(sig.Params().At(i).Type())
930 }
931 s += ")"
932 }
933 if sig.Results().Len() == 0 {
934 // keep as-is
935 } else if sig.Results().Len() == 1 {
936 s += " " + typestring(sig.Results().At(0).Type())
937 } else {
938 s += " ("
939 for i := 0; i < sig.Results().Len(); i++ {
940 if i > 0 {
941 s += ", "
942 }
943 s += typestring(sig.Results().At(i).Type())
944 }
945 s += ")"
946 }
947 return s
948 }
949
950 // typestring returns a stable (human-readable) type string for the given type
951 // that can be used for interface equality checks. It is almost (but not
952 // exactly) the same as calling t.String(). The main difference is some
953 // normalization around `byte` vs `uint8` for example.
954 func typestring(t types.Type) string {
955 // See: https://github.com/golang/go/blob/master/src/go/types/typestring.go
956 switch t := types.Unalias(t).(type) {
957 case *types.Array:
958 return "[" + strconv.FormatInt(t.Len(), 10) + "]" + typestring(t.Elem())
959 case *types.Basic:
960 return basicTypeNames[t.Kind()]
961 case *types.Chan:
962 switch t.Dir() {
963 case types.SendRecv:
964 return "chan (" + typestring(t.Elem()) + ")"
965 case types.SendOnly:
966 return "chan<- (" + typestring(t.Elem()) + ")"
967 case types.RecvOnly:
968 return "<-chan (" + typestring(t.Elem()) + ")"
969 default:
970 panic("unknown channel direction")
971 }
972 case *types.Interface:
973 methods := make([]string, t.NumMethods())
974 for i := range methods {
975 method := t.Method(i)
976 methods[i] = method.Name() + signature(method.Type().(*types.Signature))
977 }
978 return "interface{" + strings.Join(methods, ";") + "}"
979 case *types.Map:
980 return "map[" + typestring(t.Key()) + "]" + typestring(t.Elem())
981 case *types.Named:
982 return t.String()
983 case *types.Pointer:
984 return "*" + typestring(t.Elem())
985 case *types.Signature:
986 return "func" + signature(t)
987 case *types.Slice:
988 return "[]" + typestring(t.Elem())
989 case *types.Struct:
990 fields := make([]string, t.NumFields())
991 for i := range fields {
992 field := t.Field(i)
993 fields[i] = field.Name() + " " + typestring(field.Type())
994 if tag := t.Tag(i); tag != "" {
995 fields[i] += " " + strconv.Quote(tag)
996 }
997 }
998 return "struct{" + strings.Join(fields, ";") + "}"
999 default:
1000 panic("unknown type: " + t.String())
1001 }
1002 }
1003