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. Kind byte is always field 0 (no method set
146 // in the type descriptor struct). Method sets are separate globals
147 // with naming convention reflect/types.methodset:TYPE_NAME.
148 for global := p.mod.FirstGlobal(); !global.IsNil(); global = llvm.NextGlobal(global) {
149 if strings.HasPrefix(global.Name(), "reflect/types.type:") {
150 name := strings.TrimPrefix(global.Name(), "reflect/types.type:")
151 if _, ok := p.types[name]; !ok {
152 t := &typeInfo{
153 name: name,
154 typecode: global,
155 }
156 p.types[name] = t
157 // Type code is the global pointer itself (no GEP).
158 // getTypeCode returns the global directly, so the
159 // assertion comparison must also use the global directly.
160 t.typecodeGEP = global
161 // Look up separate method set global.
162 msGlobal := p.mod.NamedGlobal("reflect/types.methodset:" + name)
163 if !msGlobal.IsNil() {
164 p.addTypeMethods(t, msGlobal)
165 }
166 }
167 }
168 }
169 170 // Find all interface type asserts and interface method thunks.
171 var interfaceAssertFunctions []llvm.Value
172 var interfaceInvokeFunctions []llvm.Value
173 for fn := p.mod.FirstFunction(); !fn.IsNil(); fn = llvm.NextFunction(fn) {
174 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
175 if methodsAttr.IsNil() {
176 continue
177 }
178 if !hasUses(fn) {
179 // Don't bother defining this function.
180 continue
181 }
182 p.addInterface(methodsAttr.GetStringValue())
183 invokeAttr := fn.GetStringAttributeAtIndex(-1, "moxie-invoke")
184 if invokeAttr.IsNil() {
185 // Type assert.
186 interfaceAssertFunctions = append(interfaceAssertFunctions, fn)
187 } else {
188 // Interface invoke.
189 interfaceInvokeFunctions = append(interfaceInvokeFunctions, fn)
190 }
191 }
192 193 // Find all the interfaces that are implemented per type.
194 for _, t := range p.types {
195 // This type has no methods, so don't spend time calculating them.
196 if len(t.methods) == 0 {
197 continue
198 }
199 200 // Pre-calculate a set of signatures that this type has, for easy
201 // lookup/check.
202 typeSignatureSet := make(map[*signatureInfo]struct{})
203 for _, method := range t.methods {
204 typeSignatureSet[method.signatureInfo] = struct{}{}
205 }
206 207 // A set of interfaces, mapped from the name to the info.
208 // When the name maps to a nil pointer, one of the methods of this type
209 // exists in the given interface but not all of them so this type
210 // doesn't implement the interface.
211 satisfiesInterfaces := make(map[string]*interfaceInfo)
212 213 for _, method := range t.methods {
214 for _, itf := range method.interfaces {
215 if _, ok := satisfiesInterfaces[itf.name]; ok {
216 // interface already checked with a different method
217 continue
218 }
219 // check whether this interface satisfies this type
220 satisfies := true
221 for _, itfSignature := range itf.signatures {
222 if _, ok := typeSignatureSet[itfSignature]; !ok {
223 satisfiesInterfaces[itf.name] = nil // does not satisfy
224 satisfies = false
225 break
226 }
227 }
228 if !satisfies {
229 continue
230 }
231 satisfiesInterfaces[itf.name] = itf
232 }
233 }
234 235 // Add this type to all interfaces that satisfy this type.
236 for _, itf := range satisfiesInterfaces {
237 if itf == nil {
238 // Interface does not implement this type, but one of the
239 // methods on this type also exists on the interface.
240 continue
241 }
242 itf.types = append(itf.types, t)
243 }
244 }
245 246 // Sort all types added to the interfaces.
247 for _, itf := range p.interfaces {
248 sort.Slice(itf.types, func(i, j int) bool {
249 return itf.types[i].name > itf.types[j].name
250 })
251 }
252 253 // Define all interface invoke thunks.
254 for _, fn := range interfaceInvokeFunctions {
255 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
256 invokeAttr := fn.GetStringAttributeAtIndex(-1, "moxie-invoke")
257 itf := p.interfaces[methodsAttr.GetStringValue()]
258 signature := itf.signatures[invokeAttr.GetStringValue()]
259 p.defineInterfaceMethodFunc(fn, itf, signature)
260 }
261 262 // Define all interface type assert functions.
263 for _, fn := range interfaceAssertFunctions {
264 methodsAttr := fn.GetStringAttributeAtIndex(-1, "moxie-methods")
265 itf := p.interfaces[methodsAttr.GetStringValue()]
266 p.defineInterfaceImplementsFunc(fn, itf)
267 }
268 269 // Replace each type assert with an actual type comparison or (if the type
270 // assert is impossible) the constant false.
271 llvmFalse := llvm.ConstInt(p.ctx.Int1Type(), 0, false)
272 for _, use := range getUses(p.mod.NamedFunction("runtime.typeAssert")) {
273 actualType := use.Operand(0)
274 name := strings.TrimPrefix(use.Operand(1).Name(), "reflect/types.typeid:")
275 gepOffset := uint64(0)
276 for strings.HasPrefix(name, "pointer:pointer:") {
277 // This is a type like **int, which has the name pointer:pointer:int
278 // but is encoded using pointer tagging.
279 // Calculate the pointer tag, which is emitted as a GEP instruction.
280 name = name[len("pointer:"):]
281 gepOffset++
282 }
283 284 if t, ok := p.types[name]; ok {
285 // The type exists in the program, so lower to a regular pointer
286 // comparison.
287 p.builder.SetInsertPointBefore(use)
288 typecodeGEP := t.typecodeGEP
289 if gepOffset != 0 {
290 // This is a tagged pointer.
291 typecodeGEP = llvm.ConstInBoundsGEP(p.ctx.Int8Type(), typecodeGEP, []llvm.Value{
292 llvm.ConstInt(p.ctx.Int64Type(), gepOffset, false),
293 })
294 }
295 commaOk := p.builder.CreateICmp(llvm.IntEQ, typecodeGEP, actualType, "typeassert.ok")
296 use.ReplaceAllUsesWith(commaOk)
297 } else {
298 // The type does not exist in the program, so lower to a constant
299 // false.
300 use.ReplaceAllUsesWith(llvmFalse)
301 }
302 use.EraseFromParentAsInstruction()
303 }
304 305 // Create a sorted list of type names, for predictable iteration.
306 var typeNames []string
307 for name := range p.types {
308 typeNames = append(typeNames, name)
309 }
310 sort.Strings(typeNames)
311 312 // Method sets are separate globals - no struct rewriting needed.
313 // Remove method set globals that are no longer referenced.
314 for _, name := range typeNames {
315 t := p.types[name]
316 if !t.methodSet.IsNil() && !hasUses(t.methodSet) {
317 t.methodSet.EraseFromParentAsGlobal()
318 }
319 }
320 321 return nil
322 }
323 324 // addTypeMethods reads the method set of the given type info struct. It
325 // retrieves the signatures and the references to the method functions
326 // themselves for later type<->interface matching.
327 func (p *lowerInterfacesPass) addTypeMethods(t *typeInfo, methodSet llvm.Value) {
328 if !t.methodSet.IsNil() {
329 // no methods or methods already read
330 return
331 }
332 333 // This type has methods, collect all methods of this type.
334 t.methodSet = methodSet
335 set := methodSet.Initializer() // get value from global
336 signatures := p.builder.CreateExtractValue(set, 1, "")
337 wrappers := p.builder.CreateExtractValue(set, 2, "")
338 numMethods := signatures.Type().ArrayLength()
339 for i := 0; i < numMethods; i++ {
340 signatureGlobal := p.builder.CreateExtractValue(signatures, i, "")
341 function := p.builder.CreateExtractValue(wrappers, i, "")
342 function = stripPointerCasts(function) // strip bitcasts
343 signatureName := signatureGlobal.Name()
344 signature := p.getSignature(signatureName)
345 method := &methodInfo{
346 function: function,
347 signatureInfo: signature,
348 }
349 signature.methods = append(signature.methods, method)
350 t.methods = append(t.methods, method)
351 }
352 }
353 354 // addInterface reads information about an interface, which is the
355 // fully-qualified name and the signatures of all methods it has.
356 func (p *lowerInterfacesPass) addInterface(methodsString string) {
357 if _, ok := p.interfaces[methodsString]; ok {
358 return
359 }
360 t := &interfaceInfo{
361 name: methodsString,
362 signatures: make(map[string]*signatureInfo),
363 }
364 p.interfaces[methodsString] = t
365 for _, method := range strings.Split(methodsString, "; ") {
366 signature := p.getSignature(method)
367 signature.interfaces = append(signature.interfaces, t)
368 t.signatures[method] = signature
369 }
370 }
371 372 // getSignature returns a new *signatureInfo, creating it if it doesn't already
373 // exist.
374 func (p *lowerInterfacesPass) getSignature(name string) *signatureInfo {
375 if _, ok := p.signatures[name]; !ok {
376 p.signatures[name] = &signatureInfo{
377 name: name,
378 }
379 }
380 return p.signatures[name]
381 }
382 383 // defineInterfaceImplementsFunc defines the interface type assert function. It
384 // checks whether the given interface type (passed as an argument) is one of the
385 // types it implements.
386 //
387 // The type match is implemented using an if/else chain over all possible types.
388 // This if/else chain is easily converted to a big switch over all possible
389 // types by the LLVM simplifycfg pass.
390 func (p *lowerInterfacesPass) defineInterfaceImplementsFunc(fn llvm.Value, itf *interfaceInfo) {
391 // Create the function and function signature.
392 fn.Param(0).SetName("actualType")
393 fn.SetLinkage(llvm.InternalLinkage)
394 fn.SetUnnamedAddr(true)
395 AddStandardAttributes(fn, p.config)
396 397 // Start the if/else chain at the entry block.
398 entry := p.ctx.AddBasicBlock(fn, "entry")
399 thenBlock := p.ctx.AddBasicBlock(fn, "then")
400 p.builder.SetInsertPointAtEnd(entry)
401 402 if p.dibuilder != nil {
403 difile := p.getDIFile("<Go interface assert>")
404 diFuncType := p.dibuilder.CreateSubroutineType(llvm.DISubroutineType{
405 File: difile,
406 })
407 difunc := p.dibuilder.CreateFunction(difile, llvm.DIFunction{
408 Name: "(Go interface assert)",
409 File: difile,
410 Line: 0,
411 Type: diFuncType,
412 LocalToUnit: true,
413 IsDefinition: true,
414 ScopeLine: 0,
415 Flags: llvm.FlagPrototyped,
416 Optimized: true,
417 })
418 fn.SetSubprogram(difunc)
419 p.builder.SetCurrentDebugLocation(0, 0, difunc, llvm.Metadata{})
420 }
421 422 // Iterate over all possible types. Each iteration creates a new branch
423 // either to the 'then' block (success) or the .next block, for the next
424 // check.
425 actualType := fn.Param(0)
426 for _, typ := range itf.types {
427 nextBlock := p.ctx.AddBasicBlock(fn, typ.name+".next")
428 cmp := p.builder.CreateICmp(llvm.IntEQ, actualType, typ.typecodeGEP, typ.name+".icmp")
429 p.builder.CreateCondBr(cmp, thenBlock, nextBlock)
430 p.builder.SetInsertPointAtEnd(nextBlock)
431 }
432 433 // The builder is now inserting at the last *.next block. Once we reach
434 // this point, all types have been checked so the type assert will have
435 // failed.
436 p.builder.CreateRet(llvm.ConstInt(p.ctx.Int1Type(), 0, false))
437 438 // Fill 'then' block (type assert was successful).
439 p.builder.SetInsertPointAtEnd(thenBlock)
440 p.builder.CreateRet(llvm.ConstInt(p.ctx.Int1Type(), 1, false))
441 }
442 443 // defineInterfaceMethodFunc defines this thunk by calling the concrete method
444 // of the type that implements this interface.
445 //
446 // Matching the actual type is implemented using an if/else chain over all
447 // possible types. This is later converted to a switch statement by the LLVM
448 // simplifycfg pass.
449 func (p *lowerInterfacesPass) defineInterfaceMethodFunc(fn llvm.Value, itf *interfaceInfo, signature *signatureInfo) {
450 context := fn.LastParam()
451 actualType := llvm.PrevParam(context)
452 returnType := fn.GlobalValueType().ReturnType()
453 context.SetName("context")
454 actualType.SetName("actualType")
455 fn.SetLinkage(llvm.InternalLinkage)
456 fn.SetUnnamedAddr(true)
457 AddStandardAttributes(fn, p.config)
458 459 // Collect the params that will be passed to the functions to call.
460 // These params exclude the receiver (which may actually consist of multiple
461 // parts).
462 params := make([]llvm.Value, fn.ParamsCount()-3)
463 for i := range params {
464 params[i] = fn.Param(i + 1)
465 }
466 params = append(params,
467 llvm.Undef(p.ptrType),
468 )
469 470 // Start chain in the entry block.
471 entry := p.ctx.AddBasicBlock(fn, "entry")
472 p.builder.SetInsertPointAtEnd(entry)
473 474 if p.dibuilder != nil {
475 difile := p.getDIFile("<Go interface method>")
476 diFuncType := p.dibuilder.CreateSubroutineType(llvm.DISubroutineType{
477 File: difile,
478 })
479 difunc := p.dibuilder.CreateFunction(difile, llvm.DIFunction{
480 Name: "(Go interface method)",
481 File: difile,
482 Line: 0,
483 Type: diFuncType,
484 LocalToUnit: true,
485 IsDefinition: true,
486 ScopeLine: 0,
487 Flags: llvm.FlagPrototyped,
488 Optimized: true,
489 })
490 fn.SetSubprogram(difunc)
491 p.builder.SetCurrentDebugLocation(0, 0, difunc, llvm.Metadata{})
492 }
493 494 // Define all possible functions that can be called.
495 for _, typ := range itf.types {
496 // Create type check (if/else).
497 bb := p.ctx.AddBasicBlock(fn, typ.name)
498 next := p.ctx.AddBasicBlock(fn, typ.name+".next")
499 cmp := p.builder.CreateICmp(llvm.IntEQ, actualType, typ.typecodeGEP, typ.name+".icmp")
500 p.builder.CreateCondBr(cmp, bb, next)
501 502 // The function we will redirect to when the interface has this type.
503 function := typ.getMethod(signature).function
504 505 p.builder.SetInsertPointAtEnd(bb)
506 receiver := fn.FirstParam()
507 508 paramTypes := []llvm.Type{receiver.Type()}
509 for _, param := range params {
510 paramTypes = append(paramTypes, param.Type())
511 }
512 functionType := llvm.FunctionType(returnType, paramTypes, false)
513 retval := p.builder.CreateCall(functionType, function, append([]llvm.Value{receiver}, params...), "")
514 if retval.Type().TypeKind() == llvm.VoidTypeKind {
515 p.builder.CreateRetVoid()
516 } else {
517 p.builder.CreateRet(retval)
518 }
519 520 // Start next comparison in the 'next' block (which is jumped to when
521 // the type doesn't match).
522 p.builder.SetInsertPointAtEnd(next)
523 }
524 525 // The builder now points to the last *.then block, after all types have
526 // been checked. Call runtime.nilPanic here.
527 // The only other possible value remaining is nil for nil interfaces. We
528 // could panic with a different message here such as "nil interface" but
529 // that would increase code size and "nil panic" is close enough. Most
530 // importantly, it avoids undefined behavior when accidentally calling a
531 // method on a nil interface.
532 nilPanic := p.mod.NamedFunction("runtime.nilPanic")
533 p.builder.CreateCall(nilPanic.GlobalValueType(), nilPanic, []llvm.Value{
534 llvm.Undef(p.ptrType),
535 }, "")
536 p.builder.CreateUnreachable()
537 }
538 539 func (p *lowerInterfacesPass) getDIFile(file string) llvm.Metadata {
540 difile, ok := p.difiles[file]
541 if !ok {
542 difile = p.dibuilder.CreateFile(file, "")
543 p.difiles[file] = difile
544 }
545 return difile
546 }
547