1 package transform
2 3 // This file provides function to lower interface intrinsics to their final LLVM
4 // form, optimizing them in the process.
5 //
6 // During SSA construction, the following pseudo-call is created (see
7 // src/runtime/interface.go):
8 // runtime.typeAssert(typecode, assertedType)
9 // Additionally, interface type asserts and interface invoke functions are
10 // declared but not defined, so the optimizer will leave them alone.
11 //
12 // This pass lowers these functions to their final form:
13 //
14 // typeAssert:
15 // Replaced with an icmp instruction so it can be directly used in a type
16 // switch.
17 //
18 // interface type assert:
19 // These functions are defined by creating a big type switch over all the
20 // concrete types implementing this interface.
21 //
22 // interface invoke:
23 // These functions are defined with a similar type switch, but instead of
24 // checking for the appropriate type, these functions will call the
25 // underlying method instead.
26 //
27 // Note that this way of implementing interfaces is very different from how the
28 // main Go compiler implements them. For more details on how the main Go
29 // compiler does it: https://research.swtch.com/interfaces
30 31 import (
32 "sort"
33 "strings"
34 35 "moxie/compileopts"
36 "tinygo.org/x/go-llvm"
37 )
38 39 // signatureInfo is a Go signature of an interface method. It does not represent
40 // any method in particular.
41 type signatureInfo struct {
42 name string
43 methods []*methodInfo
44 interfaces []*interfaceInfo
45 }
46 47 // methodInfo describes a single method on a concrete type.
48 type methodInfo struct {
49 *signatureInfo
50 function llvm.Value
51 }
52 53 // typeInfo describes a single concrete Go type, which can be a basic or a named
54 // type. If it is a named type, it may have methods.
55 type typeInfo struct {
56 name string
57 typecode llvm.Value
58 typecodeGEP llvm.Value
59 methodSet llvm.Value
60 methods []*methodInfo
61 }
62 63 // getMethod looks up the method on this type with the given signature and
64 // returns it. The method must exist on this type, otherwise getMethod will
65 // panic.
66 func (t *typeInfo) getMethod(signature *signatureInfo) *methodInfo {
67 for _, method := range t.methods {
68 if method.signatureInfo == signature {
69 return method
70 }
71 }
72 panic("could not find method")
73 }
74 75 // interfaceInfo keeps information about a Go interface type, including all
76 // methods it has.
77 type interfaceInfo struct {
78 name string // "moxie-methods" attribute
79 signatures map[string]*signatureInfo // method set
80 types []*typeInfo // types this interface implements
81 }
82 83 // lowerInterfacesPass keeps state related to the interface lowering pass. The
84 // pass has been implemented as an object type because of its complexity, but
85 // should be seen as a regular function call (see LowerInterfaces).
86 type lowerInterfacesPass struct {
87 mod llvm.Module
88 config *compileopts.Config
89 builder llvm.Builder
90 dibuilder *llvm.DIBuilder
91 difiles map[string]llvm.Metadata
92 ctx llvm.Context
93 uintptrType llvm.Type
94 targetData llvm.TargetData
95 ptrType llvm.Type
96 types map[string]*typeInfo
97 signatures map[string]*signatureInfo
98 interfaces map[string]*interfaceInfo
99 }
100 101 // LowerInterfaces lowers all intermediate interface calls and globals that are
102 // emitted by the compiler as higher-level intrinsics. They need some lowering
103 // before LLVM can work on them. This is done so that a few cleanup passes can
104 // run before assigning the final type codes.
105 func LowerInterfaces(mod llvm.Module, config *compileopts.Config) error {
106 ctx := mod.Context()
107 targetData := llvm.NewTargetData(mod.DataLayout())
108 defer targetData.Dispose()
109 p := &lowerInterfacesPass{
110 mod: mod,
111 config: config,
112 builder: ctx.NewBuilder(),
113 ctx: ctx,
114 targetData: targetData,
115 uintptrType: mod.Context().IntType(targetData.PointerSize() * 8),
116 ptrType: llvm.PointerType(ctx.Int8Type(), 0),
117 types: make(map[string]*typeInfo),
118 signatures: make(map[string]*signatureInfo),
119 interfaces: make(map[string]*interfaceInfo),
120 }
121 defer p.builder.Dispose()
122 123 if config.Debug() {
124 p.dibuilder = llvm.NewDIBuilder(mod)
125 defer p.dibuilder.Destroy()
126 defer p.dibuilder.Finalize()
127 p.difiles = make(map[string]llvm.Metadata)
128 }
129 130 return p.run()
131 }
132 133 // run runs the pass itself.
134 func (p *lowerInterfacesPass) run() error {
135 if p.dibuilder != nil {
136 p.dibuilder.CreateCompileUnit(llvm.DICompileUnit{
137 Language: 0xb, // DW_LANG_C99 (0xc, off-by-one?)
138 File: "<unknown>",
139 Dir: "",
140 Producer: "Moxie",
141 Optimized: true,
142 })
143 }
144 145 // Collect all type codes.
146 for global := p.mod.FirstGlobal(); !global.IsNil(); global = llvm.NextGlobal(global) {
147 if strings.HasPrefix(global.Name(), "reflect/types.type:") {
148 // Retrieve Go type information based on an opaque global variable.
149 // Only the name of the global is relevant, the object itself is
150 // discarded afterwards.
151 name := strings.TrimPrefix(global.Name(), "reflect/types.type:")
152 if _, ok := p.types[name]; !ok {
153 t := &typeInfo{
154 name: name,
155 typecode: global,
156 }
157 p.types[name] = t
158 initializer := global.Initializer()
159 firstField := p.builder.CreateExtractValue(initializer, 0, "")
160 if firstField.Type() != p.ctx.Int8Type() {
161 // This type has a method set at index 0. Change the GEP to
162 // point to index 1 (the meta byte).
163 t.typecodeGEP = llvm.ConstGEP(global.GlobalValueType(), global, []llvm.Value{
164 llvm.ConstInt(p.ctx.Int32Type(), 0, false),
165 llvm.ConstInt(p.ctx.Int32Type(), 1, false),
166 })
167 methodSet := stripPointerCasts(firstField)
168 if !strings.HasSuffix(methodSet.Name(), "$methodset") {
169 panic("expected method set")
170 }
171 p.addTypeMethods(t, methodSet)
172 } else {
173 // This type has no method set.
174 t.typecodeGEP = llvm.ConstGEP(global.GlobalValueType(), global, []llvm.Value{
175 llvm.ConstInt(p.ctx.Int32Type(), 0, false),
176 llvm.ConstInt(p.ctx.Int32Type(), 0, false),
177 })
178 }
179 }
180 }
181 }
182 183 // Find all interface type asserts and interface method thunks.
184 var interfaceAssertFunctions []llvm.Value
185 var interfaceInvokeFunctions []llvm.Value
186 for fn := p.mod.FirstFunction(); !fn.IsNil(); fn = llvm.NextFunction(fn) {
187 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
188 if methodsAttr.IsNil() {
189 continue
190 }
191 if !hasUses(fn) {
192 // Don't bother defining this function.
193 continue
194 }
195 p.addInterface(methodsAttr.GetStringValue())
196 invokeAttr := fn.GetStringAttributeAtIndex(-1, "moxie-invoke")
197 if invokeAttr.IsNil() {
198 // Type assert.
199 interfaceAssertFunctions = append(interfaceAssertFunctions, fn)
200 } else {
201 // Interface invoke.
202 interfaceInvokeFunctions = append(interfaceInvokeFunctions, fn)
203 }
204 }
205 206 // Find all the interfaces that are implemented per type.
207 for _, t := range p.types {
208 // This type has no methods, so don't spend time calculating them.
209 if len(t.methods) == 0 {
210 continue
211 }
212 213 // Pre-calculate a set of signatures that this type has, for easy
214 // lookup/check.
215 typeSignatureSet := make(map[*signatureInfo]struct{})
216 for _, method := range t.methods {
217 typeSignatureSet[method.signatureInfo] = struct{}{}
218 }
219 220 // A set of interfaces, mapped from the name to the info.
221 // When the name maps to a nil pointer, one of the methods of this type
222 // exists in the given interface but not all of them so this type
223 // doesn't implement the interface.
224 satisfiesInterfaces := make(map[string]*interfaceInfo)
225 226 for _, method := range t.methods {
227 for _, itf := range method.interfaces {
228 if _, ok := satisfiesInterfaces[itf.name]; ok {
229 // interface already checked with a different method
230 continue
231 }
232 // check whether this interface satisfies this type
233 satisfies := true
234 for _, itfSignature := range itf.signatures {
235 if _, ok := typeSignatureSet[itfSignature]; !ok {
236 satisfiesInterfaces[itf.name] = nil // does not satisfy
237 satisfies = false
238 break
239 }
240 }
241 if !satisfies {
242 continue
243 }
244 satisfiesInterfaces[itf.name] = itf
245 }
246 }
247 248 // Add this type to all interfaces that satisfy this type.
249 for _, itf := range satisfiesInterfaces {
250 if itf == nil {
251 // Interface does not implement this type, but one of the
252 // methods on this type also exists on the interface.
253 continue
254 }
255 itf.types = append(itf.types, t)
256 }
257 }
258 259 // Sort all types added to the interfaces.
260 for _, itf := range p.interfaces {
261 sort.Slice(itf.types, func(i, j int) bool {
262 return itf.types[i].name > itf.types[j].name
263 })
264 }
265 266 // Define all interface invoke thunks.
267 for _, fn := range interfaceInvokeFunctions {
268 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
269 invokeAttr := fn.GetStringAttributeAtIndex(-1, "moxie-invoke")
270 itf := p.interfaces[methodsAttr.GetStringValue()]
271 signature := itf.signatures[invokeAttr.GetStringValue()]
272 p.defineInterfaceMethodFunc(fn, itf, signature)
273 }
274 275 // Define all interface type assert functions.
276 for _, fn := range interfaceAssertFunctions {
277 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
278 itf := p.interfaces[methodsAttr.GetStringValue()]
279 p.defineInterfaceImplementsFunc(fn, itf)
280 }
281 282 // Replace each type assert with an actual type comparison or (if the type
283 // assert is impossible) the constant false.
284 llvmFalse := llvm.ConstInt(p.ctx.Int1Type(), 0, false)
285 for _, use := range getUses(p.mod.NamedFunction("runtime.typeAssert")) {
286 actualType := use.Operand(0)
287 name := strings.TrimPrefix(use.Operand(1).Name(), "reflect/types.typeid:")
288 gepOffset := uint64(0)
289 for strings.HasPrefix(name, "pointer:pointer:") {
290 // This is a type like **int, which has the name pointer:pointer:int
291 // but is encoded using pointer tagging.
292 // Calculate the pointer tag, which is emitted as a GEP instruction.
293 name = name[len("pointer:"):]
294 gepOffset++
295 }
296 297 if t, ok := p.types[name]; ok {
298 // The type exists in the program, so lower to a regular pointer
299 // comparison.
300 p.builder.SetInsertPointBefore(use)
301 typecodeGEP := t.typecodeGEP
302 if gepOffset != 0 {
303 // This is a tagged pointer.
304 typecodeGEP = llvm.ConstInBoundsGEP(p.ctx.Int8Type(), typecodeGEP, []llvm.Value{
305 llvm.ConstInt(p.ctx.Int64Type(), gepOffset, false),
306 })
307 }
308 commaOk := p.builder.CreateICmp(llvm.IntEQ, typecodeGEP, actualType, "typeassert.ok")
309 use.ReplaceAllUsesWith(commaOk)
310 } else {
311 // The type does not exist in the program, so lower to a constant
312 // false. This is trivially further optimized.
313 // TODO: eventually it'll be necessary to handle reflect.PtrTo and
314 // reflect.New calls which create new types not present in the
315 // original program.
316 use.ReplaceAllUsesWith(llvmFalse)
317 }
318 use.EraseFromParentAsInstruction()
319 }
320 321 // Create a sorted list of type names, for predictable iteration.
322 var typeNames []string
323 for name := range p.types {
324 typeNames = append(typeNames, name)
325 }
326 sort.Strings(typeNames)
327 328 // Remove all method sets, which are now unnecessary and inhibit later
329 // optimizations if they are left in place.
330 zero := llvm.ConstInt(p.ctx.Int32Type(), 0, false)
331 for _, name := range typeNames {
332 t := p.types[name]
333 if !t.methodSet.IsNil() {
334 initializer := t.typecode.Initializer()
335 var newInitializerFields []llvm.Value
336 for i := 1; i < initializer.Type().StructElementTypesCount(); i++ {
337 newInitializerFields = append(newInitializerFields, p.builder.CreateExtractValue(initializer, i, ""))
338 }
339 newInitializer := p.ctx.ConstStruct(newInitializerFields, false)
340 typecodeName := t.typecode.Name()
341 newGlobal := llvm.AddGlobal(p.mod, newInitializer.Type(), typecodeName+".tmp")
342 newGlobal.SetInitializer(newInitializer)
343 newGlobal.SetLinkage(t.typecode.Linkage())
344 newGlobal.SetGlobalConstant(true)
345 newGlobal.SetAlignment(t.typecode.Alignment())
346 for _, use := range getUses(t.typecode) {
347 if !use.IsAConstantExpr().IsNil() {
348 opcode := use.Opcode()
349 if opcode == llvm.GetElementPtr && use.OperandsCount() == 3 {
350 if use.Operand(1).ZExtValue() == 0 && use.Operand(2).ZExtValue() == 1 {
351 gep := p.builder.CreateInBoundsGEP(newGlobal.GlobalValueType(), newGlobal, []llvm.Value{zero, zero}, "")
352 use.ReplaceAllUsesWith(gep)
353 }
354 }
355 }
356 }
357 // Fallback.
358 if hasUses(t.typecode) {
359 negativeOffset := -int64(p.targetData.TypeAllocSize(p.ptrType))
360 gep := p.builder.CreateInBoundsGEP(p.ctx.Int8Type(), newGlobal, []llvm.Value{llvm.ConstInt(p.ctx.Int32Type(), uint64(negativeOffset), true)}, "")
361 t.typecode.ReplaceAllUsesWith(gep)
362 }
363 t.typecode.EraseFromParentAsGlobal()
364 newGlobal.SetName(typecodeName)
365 t.typecode = newGlobal
366 }
367 }
368 369 return nil
370 }
371 372 // addTypeMethods reads the method set of the given type info struct. It
373 // retrieves the signatures and the references to the method functions
374 // themselves for later type<->interface matching.
375 func (p *lowerInterfacesPass) addTypeMethods(t *typeInfo, methodSet llvm.Value) {
376 if !t.methodSet.IsNil() {
377 // no methods or methods already read
378 return
379 }
380 381 // This type has methods, collect all methods of this type.
382 t.methodSet = methodSet
383 set := methodSet.Initializer() // get value from global
384 signatures := p.builder.CreateExtractValue(set, 1, "")
385 wrappers := p.builder.CreateExtractValue(set, 2, "")
386 numMethods := signatures.Type().ArrayLength()
387 for i := 0; i < numMethods; i++ {
388 signatureGlobal := p.builder.CreateExtractValue(signatures, i, "")
389 function := p.builder.CreateExtractValue(wrappers, i, "")
390 function = stripPointerCasts(function) // strip bitcasts
391 signatureName := signatureGlobal.Name()
392 signature := p.getSignature(signatureName)
393 method := &methodInfo{
394 function: function,
395 signatureInfo: signature,
396 }
397 signature.methods = append(signature.methods, method)
398 t.methods = append(t.methods, method)
399 }
400 }
401 402 // addInterface reads information about an interface, which is the
403 // fully-qualified name and the signatures of all methods it has.
404 func (p *lowerInterfacesPass) addInterface(methodsString string) {
405 if _, ok := p.interfaces[methodsString]; ok {
406 return
407 }
408 t := &interfaceInfo{
409 name: methodsString,
410 signatures: make(map[string]*signatureInfo),
411 }
412 p.interfaces[methodsString] = t
413 for _, method := range strings.Split(methodsString, "; ") {
414 signature := p.getSignature(method)
415 signature.interfaces = append(signature.interfaces, t)
416 t.signatures[method] = signature
417 }
418 }
419 420 // getSignature returns a new *signatureInfo, creating it if it doesn't already
421 // exist.
422 func (p *lowerInterfacesPass) getSignature(name string) *signatureInfo {
423 if _, ok := p.signatures[name]; !ok {
424 p.signatures[name] = &signatureInfo{
425 name: name,
426 }
427 }
428 return p.signatures[name]
429 }
430 431 // defineInterfaceImplementsFunc defines the interface type assert function. It
432 // checks whether the given interface type (passed as an argument) is one of the
433 // types it implements.
434 //
435 // The type match is implemented using an if/else chain over all possible types.
436 // This if/else chain is easily converted to a big switch over all possible
437 // types by the LLVM simplifycfg pass.
438 func (p *lowerInterfacesPass) defineInterfaceImplementsFunc(fn llvm.Value, itf *interfaceInfo) {
439 // Create the function and function signature.
440 fn.Param(0).SetName("actualType")
441 fn.SetLinkage(llvm.InternalLinkage)
442 fn.SetUnnamedAddr(true)
443 AddStandardAttributes(fn, p.config)
444 445 // Start the if/else chain at the entry block.
446 entry := p.ctx.AddBasicBlock(fn, "entry")
447 thenBlock := p.ctx.AddBasicBlock(fn, "then")
448 p.builder.SetInsertPointAtEnd(entry)
449 450 if p.dibuilder != nil {
451 difile := p.getDIFile("<Go interface assert>")
452 diFuncType := p.dibuilder.CreateSubroutineType(llvm.DISubroutineType{
453 File: difile,
454 })
455 difunc := p.dibuilder.CreateFunction(difile, llvm.DIFunction{
456 Name: "(Go interface assert)",
457 File: difile,
458 Line: 0,
459 Type: diFuncType,
460 LocalToUnit: true,
461 IsDefinition: true,
462 ScopeLine: 0,
463 Flags: llvm.FlagPrototyped,
464 Optimized: true,
465 })
466 fn.SetSubprogram(difunc)
467 p.builder.SetCurrentDebugLocation(0, 0, difunc, llvm.Metadata{})
468 }
469 470 // Iterate over all possible types. Each iteration creates a new branch
471 // either to the 'then' block (success) or the .next block, for the next
472 // check.
473 actualType := fn.Param(0)
474 for _, typ := range itf.types {
475 nextBlock := p.ctx.AddBasicBlock(fn, typ.name+".next")
476 cmp := p.builder.CreateICmp(llvm.IntEQ, actualType, typ.typecodeGEP, typ.name+".icmp")
477 p.builder.CreateCondBr(cmp, thenBlock, nextBlock)
478 p.builder.SetInsertPointAtEnd(nextBlock)
479 }
480 481 // The builder is now inserting at the last *.next block. Once we reach
482 // this point, all types have been checked so the type assert will have
483 // failed.
484 p.builder.CreateRet(llvm.ConstInt(p.ctx.Int1Type(), 0, false))
485 486 // Fill 'then' block (type assert was successful).
487 p.builder.SetInsertPointAtEnd(thenBlock)
488 p.builder.CreateRet(llvm.ConstInt(p.ctx.Int1Type(), 1, false))
489 }
490 491 // defineInterfaceMethodFunc defines this thunk by calling the concrete method
492 // of the type that implements this interface.
493 //
494 // Matching the actual type is implemented using an if/else chain over all
495 // possible types. This is later converted to a switch statement by the LLVM
496 // simplifycfg pass.
497 func (p *lowerInterfacesPass) defineInterfaceMethodFunc(fn llvm.Value, itf *interfaceInfo, signature *signatureInfo) {
498 context := fn.LastParam()
499 actualType := llvm.PrevParam(context)
500 returnType := fn.GlobalValueType().ReturnType()
501 context.SetName("context")
502 actualType.SetName("actualType")
503 fn.SetLinkage(llvm.InternalLinkage)
504 fn.SetUnnamedAddr(true)
505 AddStandardAttributes(fn, p.config)
506 507 // Collect the params that will be passed to the functions to call.
508 // These params exclude the receiver (which may actually consist of multiple
509 // parts).
510 params := make([]llvm.Value, fn.ParamsCount()-3)
511 for i := range params {
512 params[i] = fn.Param(i + 1)
513 }
514 params = append(params,
515 llvm.Undef(p.ptrType),
516 )
517 518 // Start chain in the entry block.
519 entry := p.ctx.AddBasicBlock(fn, "entry")
520 p.builder.SetInsertPointAtEnd(entry)
521 522 if p.dibuilder != nil {
523 difile := p.getDIFile("<Go interface method>")
524 diFuncType := p.dibuilder.CreateSubroutineType(llvm.DISubroutineType{
525 File: difile,
526 })
527 difunc := p.dibuilder.CreateFunction(difile, llvm.DIFunction{
528 Name: "(Go interface method)",
529 File: difile,
530 Line: 0,
531 Type: diFuncType,
532 LocalToUnit: true,
533 IsDefinition: true,
534 ScopeLine: 0,
535 Flags: llvm.FlagPrototyped,
536 Optimized: true,
537 })
538 fn.SetSubprogram(difunc)
539 p.builder.SetCurrentDebugLocation(0, 0, difunc, llvm.Metadata{})
540 }
541 542 // Define all possible functions that can be called.
543 for _, typ := range itf.types {
544 // Create type check (if/else).
545 bb := p.ctx.AddBasicBlock(fn, typ.name)
546 next := p.ctx.AddBasicBlock(fn, typ.name+".next")
547 cmp := p.builder.CreateICmp(llvm.IntEQ, actualType, typ.typecodeGEP, typ.name+".icmp")
548 p.builder.CreateCondBr(cmp, bb, next)
549 550 // The function we will redirect to when the interface has this type.
551 function := typ.getMethod(signature).function
552 553 p.builder.SetInsertPointAtEnd(bb)
554 receiver := fn.FirstParam()
555 556 paramTypes := []llvm.Type{receiver.Type()}
557 for _, param := range params {
558 paramTypes = append(paramTypes, param.Type())
559 }
560 functionType := llvm.FunctionType(returnType, paramTypes, false)
561 retval := p.builder.CreateCall(functionType, function, append([]llvm.Value{receiver}, params...), "")
562 if retval.Type().TypeKind() == llvm.VoidTypeKind {
563 p.builder.CreateRetVoid()
564 } else {
565 p.builder.CreateRet(retval)
566 }
567 568 // Start next comparison in the 'next' block (which is jumped to when
569 // the type doesn't match).
570 p.builder.SetInsertPointAtEnd(next)
571 }
572 573 // The builder now points to the last *.then block, after all types have
574 // been checked. Call runtime.nilPanic here.
575 // The only other possible value remaining is nil for nil interfaces. We
576 // could panic with a different message here such as "nil interface" but
577 // that would increase code size and "nil panic" is close enough. Most
578 // importantly, it avoids undefined behavior when accidentally calling a
579 // method on a nil interface.
580 nilPanic := p.mod.NamedFunction("runtime.nilPanic")
581 p.builder.CreateCall(nilPanic.GlobalValueType(), nilPanic, []llvm.Value{
582 llvm.Undef(p.ptrType),
583 }, "")
584 p.builder.CreateUnreachable()
585 }
586 587 func (p *lowerInterfacesPass) getDIFile(file string) llvm.Metadata {
588 difile, ok := p.difiles[file]
589 if !ok {
590 difile = p.dibuilder.CreateFile(file, "")
591 p.difiles[file] = difile
592 }
593 return difile
594 }
595