transform: optimize reflect.Type Implements() method

This commit adds a new transform that converts reflect Implements()
calls to runtime.interfaceImplements. At the moment, the Implements()
method is not yet implemented (how ironic) but if the value passed to
Implements is known at compile time the method call can be optimized to
runtime.interfaceImplements to make it a regular interface assert.

This commit is the last change necessary to add basic support for the
encoding/json package. The json package is certainly not yet fully
supported, but some trivial objects can be converted to JSON.

12 files changed, 242 insertions, 8 deletions

diff --git a/compiler/compiler.go b/compiler/compiler.go
index 8a6992240..d012724b7 100644
--- a/compiler/compiler.go
+++ b/compiler/compiler.go
@@ -23,7 +23,7 @@ import (
 // Version of the compiler pacakge. Must be incremented each time the compiler
 // package changes in a way that affects the generated LLVM module.
 // This version is independent of the TinyGo version number.
-const Version = 4 // last change: runtime.typeAssert signature
+const Version = 5 // last change: add method set to interface types
 
 func init() {
 	llvm.InitializeAllTargets()
diff --git a/compiler/interface.go b/compiler/interface.go
index ed75b3577..dae098577 100644
--- a/compiler/interface.go
+++ b/compiler/interface.go
@@ -62,6 +62,9 @@ func (c *compilerContext) getTypeCode(typ types.Type) llvm.Value {
 			// Take a pointer to the typecodeID of the first field (if it exists).
 			structGlobal := c.makeStructTypeFields(typ)
 			references = llvm.ConstBitCast(structGlobal, global.Type())
+		case *types.Interface:
+			methodSetGlobal := c.getInterfaceMethodSet(typ)
+			references = llvm.ConstBitCast(methodSetGlobal, global.Type())
 		}
 		if _, ok := typ.Underlying().(*types.Interface); !ok {
 			methodSet = c.getTypeMethodSet(typ)
diff --git a/compiler/testdata/interface.ll b/compiler/testdata/interface.ll
index b3c2f86a6..1405abf18 100644
--- a/compiler/testdata/interface.ll
+++ b/compiler/testdata/interface.ll
@@ -12,14 +12,15 @@ target triple = "i686--linux"
 @"reflect/types.type:pointer:basic:int" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:basic:int", i32 0, %runtime.interfaceMethodInfo* null }
 @"reflect/types.type:pointer:named:error" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:named:error", i32 0, %runtime.interfaceMethodInfo* null }
 @"reflect/types.type:named:error" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{Error:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null }
-@"reflect/types.type:interface:{Error:func:{}{basic:string}}" = external constant %runtime.typecodeID
-@"reflect/types.type:pointer:interface:{String:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{String:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null }
-@"reflect/types.type:interface:{String:func:{}{basic:string}}" = external constant %runtime.typecodeID
-@"reflect/types.type:basic:int$id" = external constant i8
+@"reflect/types.type:interface:{Error:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* bitcast ([1 x i8*]* @"reflect/types.interface:interface{Error() string}$interface" to %runtime.typecodeID*), i32 0, %runtime.interfaceMethodInfo* null }
 @"func Error() string" = external constant i8
-@"error$interface" = linkonce_odr constant [1 x i8*] [i8* @"func Error() string"]
+@"reflect/types.interface:interface{Error() string}$interface" = linkonce_odr constant [1 x i8*] [i8* @"func Error() string"]
+@"reflect/types.type:pointer:interface:{String:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{String:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null }
+@"reflect/types.type:interface:{String:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* bitcast ([1 x i8*]* @"reflect/types.interface:interface{String() string}$interface" to %runtime.typecodeID*), i32 0, %runtime.interfaceMethodInfo* null }
 @"func String() string" = external constant i8
 @"reflect/types.interface:interface{String() string}$interface" = linkonce_odr constant [1 x i8*] [i8* @"func String() string"]
+@"reflect/types.type:basic:int$id" = external constant i8
+@"error$interface" = linkonce_odr constant [1 x i8*] [i8* @"func Error() string"]
 
 declare noalias nonnull i8* @runtime.alloc(i32, i8*, i8*)
 
diff --git a/testdata/json.go b/testdata/json.go
new file mode 100644
index 000000000..598f8cbe3
--- /dev/null
+++ b/testdata/json.go
@@ -0,0 +1,20 @@
+package main
+
+import (
+	"encoding/json"
+)
+
+func main() {
+	println("int:", encode(3))
+	println("float64:", encode(3.14))
+	println("string:", encode("foo"))
+	println("slice of strings:", encode([]string{"foo", "bar"}))
+}
+
+func encode(itf interface{}) string {
+	buf, err := json.Marshal(itf)
+	if err != nil {
+		panic("failed to JSON encode: " + err.Error())
+	}
+	return string(buf)
+}
diff --git a/testdata/json.txt b/testdata/json.txt
new file mode 100644
index 000000000..d162d9e6f
--- /dev/null
+++ b/testdata/json.txt
@@ -0,0 +1,4 @@
+int: 3
+float64: 3.14
+string: "foo"
+slice of strings: ["foo","bar"]
diff --git a/testdata/reflect.go b/testdata/reflect.go
index ba81fe968..3d4b65fb6 100644
--- a/testdata/reflect.go
+++ b/testdata/reflect.go
@@ -1,6 +1,7 @@
 package main
 
 import (
+	"errors"
 	"reflect"
 	"unsafe"
 )
@@ -28,6 +29,14 @@ type (
 	}
 )
 
+var (
+	errorValue   = errors.New("test error")
+	errorType    = reflect.TypeOf((*error)(nil)).Elem()
+	stringerType = reflect.TypeOf((*interface {
+		String() string
+	})(nil)).Elem()
+)
+
 func main() {
 	println("matching types")
 	println(reflect.TypeOf(int(3)) == reflect.TypeOf(int(5)))
@@ -285,6 +294,13 @@ func main() {
 		println("PtrTo failed for type myslice")
 	}
 
+	if reflect.TypeOf(errorValue).Implements(errorType) != true {
+		println("errorValue.Implements(errorType) was false, expected true")
+	}
+	if reflect.TypeOf(errorValue).Implements(stringerType) != false {
+		println("errorValue.Implements(errorType) was true, expected false")
+	}
+
 	println("\nstruct tags")
 	TestStructTag()
 }
diff --git a/transform/interface-lowering.go b/transform/interface-lowering.go
index ee384f837..3da4f0f49 100644
--- a/transform/interface-lowering.go
+++ b/transform/interface-lowering.go
@@ -428,7 +428,7 @@ func (p *lowerInterfacesPass) run() error {
 		if !initializer.IsNil() {
 			references := llvm.ConstExtractValue(initializer, []uint32{0})
 			typ.typecode.SetInitializer(zeroTypeCode)
-			if !references.IsAConstantExpr().IsNil() && references.Opcode() == llvm.BitCast {
+			if strings.HasPrefix(typ.name, "reflect/types.type:struct:") {
 				// Structs have a 'references' field that is not a typecode but
 				// a pointer to a runtime.structField array and therefore a
 				// bitcast. This global should be erased separately, otherwise
diff --git a/transform/optimizer.go b/transform/optimizer.go
index 7ff7874f1..e10144b92 100644
--- a/transform/optimizer.go
+++ b/transform/optimizer.go
@@ -74,6 +74,7 @@ func Optimize(mod llvm.Module, config *compileopts.Config, optLevel, sizeLevel i
 		// Run Go-specific optimization passes.
 		OptimizeMaps(mod)
 		OptimizeStringToBytes(mod)
+		OptimizeReflectImplements(mod)
 		OptimizeAllocs(mod)
 		err := LowerInterfaces(mod)
 		if err != nil {
diff --git a/transform/rtcalls.go b/transform/rtcalls.go
index aac00d157..0ced0bfea 100644
--- a/transform/rtcalls.go
+++ b/transform/rtcalls.go
@@ -1,8 +1,11 @@
 package transform
 
-// This file implements several small optimizations of runtime calls.
+// This file implements several small optimizations of runtime and reflect
+// calls.
 
 import (
+	"strings"
+
 	"tinygo.org/x/go-llvm"
 )
 
@@ -85,3 +88,98 @@ func OptimizeStringEqual(mod llvm.Module) {
 		}
 	}
 }
+
+// OptimizeReflectImplements optimizes the following code:
+//
+//     implements := someType.Implements(someInterfaceType)
+//
+// where someType is an arbitrary reflect.Type and someInterfaceType is a
+// reflect.Type of interface kind, to the following code:
+//
+//     _, implements := someType.(interfaceType)
+//
+// if the interface type is known at compile time (that is, someInterfaceType is
+// a LLVM constant aggregate). This optimization is especially important for the
+// encoding/json package, which uses this method.
+//
+// As of this writing, the (reflect.Type).Interface method has not yet been
+// implemented so this optimization is critical for the encoding/json package.
+func OptimizeReflectImplements(mod llvm.Module) {
+	implementsSignature := mod.NamedGlobal("func Implements(reflect.Type) bool")
+	if implementsSignature.IsNil() {
+		return
+	}
+	interfaceMethod := mod.NamedFunction("runtime.interfaceMethod")
+	if interfaceMethod.IsNil() {
+		return
+	}
+	interfaceImplements := mod.NamedFunction("runtime.interfaceImplements")
+	if interfaceImplements.IsNil() {
+		return
+	}
+
+	builder := mod.Context().NewBuilder()
+	defer builder.Dispose()
+
+	// Get a few useful object for use later.
+	zero := llvm.ConstInt(mod.Context().Int32Type(), 0, false)
+	uintptrType := mod.Context().IntType(llvm.NewTargetData(mod.DataLayout()).PointerSize() * 8)
+
+	defer llvm.VerifyModule(mod, llvm.PrintMessageAction)
+
+	for _, use := range getUses(implementsSignature) {
+		if use.IsACallInst().IsNil() {
+			continue
+		}
+		if use.CalledValue() != interfaceMethod {
+			continue
+		}
+		for _, bitcast := range getUses(use) {
+			if !bitcast.IsABitCastInst().IsNil() {
+				continue
+			}
+			for _, call := range getUses(bitcast) {
+				// Try to get the interface method set.
+				interfaceTypeBitCast := call.Operand(2)
+				if interfaceTypeBitCast.IsAConstantExpr().IsNil() || interfaceTypeBitCast.Opcode() != llvm.BitCast {
+					continue
+				}
+				interfaceType := interfaceTypeBitCast.Operand(0)
+				if strings.HasPrefix(interfaceType.Name(), "reflect/types.type:named:") {
+					// Get the underlying type.
+					interfaceType = llvm.ConstExtractValue(interfaceType.Initializer(), []uint32{0})
+				}
+				if !strings.HasPrefix(interfaceType.Name(), "reflect/types.type:interface:") {
+					// This is an error. The Type passed to Implements should be
+					// of interface type. Ignore it here (don't report it), it
+					// will be reported at runtime.
+					continue
+				}
+				if interfaceType.IsAGlobalVariable().IsNil() {
+					// Interface is unknown at compile time. This can't be
+					// optimized.
+					continue
+				}
+				// Get the 'references' field of the runtime.typecodeID, which
+				// is a bitcast of an interface method set.
+				interfaceMethodSet := llvm.ConstExtractValue(interfaceType.Initializer(), []uint32{0}).Operand(0)
+
+				builder.SetInsertPointBefore(call)
+				implements := builder.CreateCall(interfaceImplements, []llvm.Value{
+					builder.CreatePtrToInt(call.Operand(0), uintptrType, ""),    // typecode to check
+					llvm.ConstGEP(interfaceMethodSet, []llvm.Value{zero, zero}), // method set to check against
+					llvm.Undef(llvm.PointerType(mod.Context().Int8Type(), 0)),
+					llvm.Undef(llvm.PointerType(mod.Context().Int8Type(), 0)),
+				}, "")
+				call.ReplaceAllUsesWith(implements)
+				call.EraseFromParentAsInstruction()
+			}
+			if !hasUses(bitcast) {
+				bitcast.EraseFromParentAsInstruction()
+			}
+		}
+		if !hasUses(use) {
+			use.EraseFromParentAsInstruction()
+		}
+	}
+}
diff --git a/transform/rtcalls_test.go b/transform/rtcalls_test.go
index b414fc10a..819dc5acb 100644
--- a/transform/rtcalls_test.go
+++ b/transform/rtcalls_test.go
@@ -21,3 +21,11 @@ func TestOptimizeStringEqual(t *testing.T) {
 		OptimizeStringEqual(mod)
 	})
 }
+
+func TestOptimizeReflectImplements(t *testing.T) {
+	t.Parallel()
+	testTransform(t, "testdata/reflect-implements", func(mod llvm.Module) {
+		// Run optimization pass.
+		OptimizeReflectImplements(mod)
+	})
+}
diff --git a/transform/testdata/reflect-implements.ll b/transform/testdata/reflect-implements.ll
new file mode 100644
index 000000000..22c76485d
--- /dev/null
+++ b/transform/testdata/reflect-implements.ll
@@ -0,0 +1,48 @@
+target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-f64:32:64-f80:32-n8:16:32-S128"
+target triple = "i686--linux"
+
+%runtime.typecodeID = type { %runtime.typecodeID*, i32, %runtime.interfaceMethodInfo* }
+%runtime.interfaceMethodInfo = type { i8*, i32 }
+
+@"reflect/types.type:named:error" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{Error:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null }
+@"reflect/types.type:interface:{Error:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* bitcast ([1 x i8*]* @"reflect/types.interface:interface{Error() string}$interface" to %runtime.typecodeID*), i32 0, %runtime.interfaceMethodInfo* null }
+@"func Error() string" = external constant i8
+@"reflect/types.interface:interface{Error() string}$interface" = linkonce_odr constant [1 x i8*] [i8* @"func Error() string"]
+@"func Align() int" = external constant i8
+@"func Implements(reflect.Type) bool" = external constant i8
+@"reflect.Type$interface" = linkonce_odr constant [2 x i8*] [i8* @"func Align() int", i8* @"func Implements(reflect.Type) bool"]
+@"reflect/types.type:named:reflect.rawType" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:basic:uintptr", i32 0, %runtime.interfaceMethodInfo* getelementptr inbounds ([20 x %runtime.interfaceMethodInfo], [20 x %runtime.interfaceMethodInfo]* @"reflect.rawType$methodset", i32 0, i32 0) }
+@"reflect.rawType$methodset" = linkonce_odr constant [20 x %runtime.interfaceMethodInfo] zeroinitializer
+@"reflect/types.type:basic:uintptr" = linkonce_odr constant %runtime.typecodeID zeroinitializer
+
+declare i1 @runtime.interfaceImplements(i32, i8**, i8*, i8*)
+
+declare i32 @runtime.interfaceMethod(i32, i8**, i8*, i8*, i8*)
+
+; var errorType = reflect.TypeOf((*error)(nil)).Elem()
+; func isError(typ reflect.Type) bool {
+;   return typ.Implements(errorType)
+; }
+; The type itself is stored in %typ.value, %typ.typecode just refers to the
+; type of reflect.Type. This function can be optimized because errorType is
+; known at compile time (after the interp pass has run).
+define i1 @main.isError(i32 %typ.typecode, i8* %typ.value, i8* %context, i8* %parentHandle) {
+entry:
+  %invoke.func = call i32 @runtime.interfaceMethod(i32 %typ.typecode, i8** getelementptr inbounds ([2 x i8*], [2 x i8*]* @"reflect.Type$interface", i32 0, i32 0), i8* nonnull @"func Implements(reflect.Type) bool", i8* undef, i8* null)
+  %invoke.func.cast = inttoptr i32 %invoke.func to i1 (i8*, i32, i8*, i8*, i8*)*
+  %result = call i1 %invoke.func.cast(i8* %typ.value, i32 ptrtoint (%runtime.typecodeID* @"reflect/types.type:named:reflect.rawType" to i32), i8* bitcast (%runtime.typecodeID* @"reflect/types.type:named:error" to i8*), i8* undef, i8* undef)
+  ret i1 %result
+}
+
+; This Implements method call can not be optimized because itf is not known at
+; compile time.
+; func isUnknown(typ, itf reflect.Type) bool {
+;   return typ.Implements(itf)
+; }
+define i1 @main.isUnknown(i32 %typ.typecode, i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i8* %context, i8* %parentHandle) {
+entry:
+  %invoke.func = call i32 @runtime.interfaceMethod(i32 %typ.typecode, i8** getelementptr inbounds ([2 x i8*], [2 x i8*]* @"reflect.Type$interface", i32 0, i32 0), i8* nonnull @"func Implements(reflect.Type) bool", i8* undef, i8* null)
+  %invoke.func.cast = inttoptr i32 %invoke.func to i1 (i8*, i32, i8*, i8*, i8*)*
+  %result = call i1 %invoke.func.cast(i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i8* undef, i8* undef)
+  ret i1 %result
+}
diff --git a/transform/testdata/reflect-implements.out.ll b/transform/testdata/reflect-implements.out.ll
new file mode 100644
index 000000000..03d977699
--- /dev/null
+++ b/transform/testdata/reflect-implements.out.ll
@@ -0,0 +1,35 @@
+target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-f64:32:64-f80:32-n8:16:32-S128"
+target triple = "i686--linux"
+
+%runtime.typecodeID = type { %runtime.typecodeID*, i32, %runtime.interfaceMethodInfo* }
+%runtime.interfaceMethodInfo = type { i8*, i32 }
+
+@"reflect/types.type:named:error" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{Error:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null }
+@"reflect/types.type:interface:{Error:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* bitcast ([1 x i8*]* @"reflect/types.interface:interface{Error() string}$interface" to %runtime.typecodeID*), i32 0, %runtime.interfaceMethodInfo* null }
+@"func Error() string" = external constant i8
+@"reflect/types.interface:interface{Error() string}$interface" = linkonce_odr constant [1 x i8*] [i8* @"func Error() string"]
+@"func Align() int" = external constant i8
+@"func Implements(reflect.Type) bool" = external constant i8
+@"reflect.Type$interface" = linkonce_odr constant [2 x i8*] [i8* @"func Align() int", i8* @"func Implements(reflect.Type) bool"]
+@"reflect/types.type:named:reflect.rawType" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:basic:uintptr", i32 0, %runtime.interfaceMethodInfo* getelementptr inbounds ([20 x %runtime.interfaceMethodInfo], [20 x %runtime.interfaceMethodInfo]* @"reflect.rawType$methodset", i32 0, i32 0) }
+@"reflect.rawType$methodset" = linkonce_odr constant [20 x %runtime.interfaceMethodInfo] zeroinitializer
+@"reflect/types.type:basic:uintptr" = linkonce_odr constant %runtime.typecodeID zeroinitializer
+
+declare i1 @runtime.interfaceImplements(i32, i8**, i8*, i8*)
+
+declare i32 @runtime.interfaceMethod(i32, i8**, i8*, i8*, i8*)
+
+define i1 @main.isError(i32 %typ.typecode, i8* %typ.value, i8* %context, i8* %parentHandle) {
+entry:
+  %0 = ptrtoint i8* %typ.value to i32
+  %1 = call i1 @runtime.interfaceImplements(i32 %0, i8** getelementptr inbounds ([1 x i8*], [1 x i8*]* @"reflect/types.interface:interface{Error() string}$interface", i32 0, i32 0), i8* undef, i8* undef)
+  ret i1 %1
+}
+
+define i1 @main.isUnknown(i32 %typ.typecode, i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i8* %context, i8* %parentHandle) {
+entry:
+  %invoke.func = call i32 @runtime.interfaceMethod(i32 %typ.typecode, i8** getelementptr inbounds ([2 x i8*], [2 x i8*]* @"reflect.Type$interface", i32 0, i32 0), i8* nonnull @"func Implements(reflect.Type) bool", i8* undef, i8* null)
+  %invoke.func.cast = inttoptr i32 %invoke.func to i1 (i8*, i32, i8*, i8*, i8*)*
+  %result = call i1 %invoke.func.cast(i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i8* undef, i8* undef)
+  ret i1 %result
+}