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