compiler: include type information about the runtime in the compiler

These types are often known to the compiler already. Moving them into
the compiler is an important step for two related reasons:

  * It makes the compiler better testable. Together with
    https://github.com/tinygo-org/tinygo/pull/1008 it will make it
    possible to test the compiler without having to load the runtime
    package.
  * It makes it easier to compile packages independently as the type
    information of the runtime package doesn't need to be present.

I had to use hack to get this to work well: internal/task.Task is now an
opaque struct. This is necessary because there is a dependency from
*runtime.channel -> *runtime.channelBlockedList -> *internal/task.Task.
I don't want to include the definition of the internal/task.Task struct
in the compiler directly as that would make changing the internal/task
package a lot harder and the compiler doesn't need to know the layout of
that struct anyway.

8 files changed, 822 insertions, 42 deletions

diff --git a/compiler/calls.go b/compiler/calls.go
index 87eab6048..7706a3125 100644
--- a/compiler/calls.go
+++ b/compiler/calls.go
@@ -4,7 +4,6 @@ import (
 	"go/types"
 	"strconv"
 
-	"golang.org/x/tools/go/ssa"
 	"tinygo.org/x/go-llvm"
 )
 
@@ -35,11 +34,9 @@ const (
 
 // createCall creates a new call to runtime.<fnName> with the given arguments.
 func (b *builder) createRuntimeCall(fnName string, args []llvm.Value, name string) llvm.Value {
-	fn := b.program.ImportedPackage("runtime").Members[fnName].(*ssa.Function)
-	llvmFn := b.getFunction(fn)
-	if llvmFn.IsNil() {
-		panic("trying to call non-existent function: " + fn.RelString(nil))
-	}
+	llvmFn := b.getFunctionRaw(b.getRuntimeFuncType(fnName), functionInfo{
+		linkName: "runtime." + fnName,
+	})
 	args = append(args, llvm.Undef(b.i8ptrType))            // unused context parameter
 	args = append(args, llvm.ConstPointerNull(b.i8ptrType)) // coroutine handle
 	return b.createCall(llvmFn, args, name)
diff --git a/compiler/compiler.go b/compiler/compiler.go
index 45bba1146..e0479ced8 100644
--- a/compiler/compiler.go
+++ b/compiler/compiler.go
@@ -1,5 +1,7 @@
 package compiler
 
+//go:generate go run ./mkruntimetypes.go
+
 import (
 	"debug/dwarf"
 	"errors"
@@ -49,11 +51,14 @@ type compilerContext struct {
 	targetData       llvm.TargetData
 	intType          llvm.Type
 	i8ptrType        llvm.Type // for convenience
+	runtimeTypes     map[string]types.Type
 	funcPtrAddrSpace int
 	uintptrType      llvm.Type
 	program          *ssa.Program
 	diagnostics      []error
 	astComments      map[string]*ast.CommentGroup
+	runtimePkg       *types.Package // package runtime
+	taskPkg          *types.Package // package internal/task
 }
 
 // builder contains all information relevant to build a single function.
@@ -101,11 +106,12 @@ func NewTargetMachine(config *compileopts.Config) (llvm.TargetMachine, error) {
 // configuration, ready to compile Go SSA to LLVM IR.
 func newCompilerContext(pkgName string, machine llvm.TargetMachine, config *compileopts.Config) *compilerContext {
 	c := &compilerContext{
-		Config:     config,
-		difiles:    make(map[string]llvm.Metadata),
-		ditypes:    make(map[types.Type]llvm.Metadata),
-		machine:    machine,
-		targetData: machine.CreateTargetData(),
+		Config:       config,
+		difiles:      make(map[string]llvm.Metadata),
+		ditypes:      make(map[types.Type]llvm.Metadata),
+		machine:      machine,
+		targetData:   machine.CreateTargetData(),
+		runtimeTypes: make(map[string]types.Type),
 	}
 
 	c.ctx = llvm.NewContext()
@@ -246,6 +252,8 @@ func Compile(pkgName string, machine llvm.TargetMachine, config *compileopts.Con
 
 	c.program = lprogram.LoadSSA()
 	c.program.Build()
+	c.runtimePkg = c.program.ImportedPackage("runtime").Pkg
+	c.taskPkg = c.program.ImportedPackage("internal/task").Pkg
 
 	// Initialize debug information.
 	if c.Debug() {
@@ -260,20 +268,6 @@ func Compile(pkgName string, machine llvm.TargetMachine, config *compileopts.Con
 
 	c.loadASTComments(lprogram)
 
-	// Declare runtime types.
-	// TODO: lazily create runtime types in getLLVMRuntimeType when they are
-	// needed. Eventually this will be required anyway, when packages are
-	// compiled independently (and the runtime types are not available).
-	for _, member := range c.program.ImportedPackage("runtime").Members {
-		if member, ok := member.(*ssa.Type); ok {
-			if typ, ok := member.Type().(*types.Named); ok {
-				if _, ok := typ.Underlying().(*types.Struct); ok {
-					c.getLLVMType(typ)
-				}
-			}
-		}
-	}
-
 	// Predeclare the runtime.alloc function, which is used by the wordpack
 	// functionality.
 	c.getFunction(c.program.ImportedPackage("runtime").Members["alloc"].(*ssa.Function))
@@ -453,16 +447,14 @@ func sortPackages(program *ssa.Program, mainPath string) []*ssa.Package {
 }
 
 // getLLVMRuntimeType obtains a named type from the runtime package and returns
-// it as a LLVM type, creating it if necessary. It is a shorthand for
-// getLLVMType(getRuntimeType(name)).
+// it as a LLVM type, creating it if necessary.
 func (c *compilerContext) getLLVMRuntimeType(name string) llvm.Type {
 	fullName := "runtime." + name
-	typ := c.mod.GetTypeByName(fullName)
-	if typ.IsNil() {
-		println(c.mod.String())
-		panic("could not find runtime type: " + fullName)
+	llvmType := c.mod.GetTypeByName(fullName)
+	if llvmType.IsNil() {
+		llvmType = c.getLLVMType(c.getRuntimeType(name))
 	}
-	return typ
+	return llvmType
 }
 
 // getLLVMType creates and returns a LLVM type for a Go type. In the case of
@@ -522,6 +514,10 @@ func (c *compilerContext) getLLVMType(goType types.Type) llvm.Type {
 				llvmType = c.ctx.StructCreateNamed(llvmName)
 				underlying := c.getLLVMType(st)
 				llvmType.StructSetBody(underlying.StructElementTypes(), false)
+			} else if typ.String() == "internal/task.Task" && llvmType.StructElementTypesCount() == 0 {
+				// Note: this struct is an opaque struct. Give it a body.
+				underlying := c.getLLVMType(st)
+				llvmType.StructSetBody(underlying.StructElementTypes(), false)
 			}
 			return llvmType
 		}
@@ -542,6 +538,23 @@ func (c *compilerContext) getLLVMType(goType types.Type) llvm.Type {
 	case *types.Struct:
 		members := make([]llvm.Type, typ.NumFields())
 		for i := 0; i < typ.NumFields(); i++ {
+			if ptr, ok := typ.Field(i).Type().(*types.Pointer); ok {
+				if named, ok := ptr.Elem().(*types.Named); ok && named.String() == "internal/task.Task" {
+					// Special workaround for internal/task.Task. It is
+					// referenced from the runtime.channel type, which
+					// references runtime.channelBlockedList, which references
+					// internal/task.Task. To avoid having to define
+					// internal/task.Task as a compiler-internal type, make the
+					// type opaque.
+					ptrTo := c.mod.GetTypeByName(named.String())
+					if ptrTo.IsNil() {
+						ptrTo = c.ctx.StructCreateNamed(named.String())
+					}
+					members[i] = llvm.PointerType(ptrTo, 0)
+					continue
+				}
+			}
+
 			members[i] = c.getLLVMType(typ.Field(i).Type())
 		}
 		return c.ctx.StructType(members, false)
@@ -645,11 +658,11 @@ func (c *compilerContext) createDIType(typ types.Type) llvm.Metadata {
 			Encoding:   encoding,
 		})
 	case *types.Chan:
-		return c.getDIType(types.NewPointer(c.program.ImportedPackage("runtime").Members["channel"].(*ssa.Type).Type()))
+		return c.getDIType(types.NewPointer(c.getRuntimeType("channel")))
 	case *types.Interface:
-		return c.getDIType(c.program.ImportedPackage("runtime").Members["_interface"].(*ssa.Type).Type())
+		return c.getDIType(c.getRuntimeType("_interface"))
 	case *types.Map:
-		return c.getDIType(types.NewPointer(c.program.ImportedPackage("runtime").Members["hashmap"].(*ssa.Type).Type()))
+		return c.getDIType(types.NewPointer(c.getRuntimeType("hashmap")))
 	case *types.Named:
 		return c.dibuilder.CreateTypedef(llvm.DITypedef{
 			Type: c.getDIType(typ.Underlying()),
diff --git a/compiler/compiler_test.go b/compiler/compiler_test.go
index 1607f624e..dbe4590ff 100644
--- a/compiler/compiler_test.go
+++ b/compiler/compiler_test.go
@@ -81,6 +81,8 @@ func runCompilerTest(t *testing.T, name string) {
 		t.Fatal(err)
 	}
 	c := newCompilerContext("main", machine, &config)
+	c.runtimePkg = types.NewPackage("runtime", "runtime")
+	c.taskPkg = types.NewPackage("internal/task", "task")
 	irbuilder := c.ctx.NewBuilder()
 	defer irbuilder.Dispose()
 
diff --git a/compiler/mkruntimetypes.go b/compiler/mkruntimetypes.go
new file mode 100644
index 000000000..97afd9000
--- /dev/null
+++ b/compiler/mkruntimetypes.go
@@ -0,0 +1,344 @@
+// +build none
+
+// This file generates runtimetypes.go from the AST of the TinyGo runtime
+// package. This type information is necessary to avoid having to compile the
+// runtime to compile any package.
+
+package main
+
+import (
+	"bytes"
+	"fmt"
+	"go/ast"
+	"go/format"
+	"go/token"
+	"io"
+	"io/ioutil"
+	"os"
+	"strings"
+
+	"golang.org/x/tools/go/packages"
+)
+
+// The list of runtime types known by the compiler.
+var runtimeTypes = []string{
+	// panic, recover
+	"_defer",
+	// strings
+	"_string", "stringIterator",
+	// map
+	"hashmap", "hashmapBucket", "hashmapIterator",
+	// channel
+	"channel", "channelBlockedList", "chanSelectState",
+	// interface
+	"_interface", "interfaceMethodInfo", "typecodeID", "structField", "typeInInterface",
+	// func
+	"funcValue", "funcValueWithSignature",
+}
+
+// The list of runtime calls known to the compiler.
+var runtimeCalls = []string{
+	// panic, recover
+	"_panic", "_recover",
+	"nilPanic", "lookupPanic", "slicePanic", "chanMakePanic", "negativeShiftPanic",
+	// string
+	"stringEqual", "stringLess",
+	"stringConcat",
+	"stringFromBytes", "stringToBytes",
+	"stringFromRunes", "stringToRunes",
+	"stringFromUnicode",
+	"stringNext",
+	// complex
+	"complex64div", "complex128div",
+	// slice
+	"sliceAppend", "sliceCopy",
+	// memory
+	"alloc", "trackPointer",
+	// print builtin
+	"printbool",
+	"printint8", "printuint8",
+	"printint16", "printuint16",
+	"printint32", "printuint32",
+	"printint64", "printuint64",
+	"printfloat32", "printfloat64",
+	"printcomplex64", "printcomplex128",
+	"printstring", "printspace", "printnl",
+	"printptr", "printmap", "printitf",
+	// hashmap
+	"hashmapMake", "hashmapLen", "hashmapNext",
+	"hashmapStringGet", "hashmapStringSet", "hashmapStringDelete",
+	"hashmapInterfaceGet", "hashmapInterfaceSet", "hashmapInterfaceDelete",
+	"hashmapBinaryGet", "hashmapBinarySet", "hashmapBinaryDelete",
+	// channel, concurrency
+	"tryChanSelect", "chanMake", "chanSend", "chanRecv", "chanClose", "chanSelect",
+	"deadlock",
+	// interface, reflect
+	"interfaceEqual", "interfaceImplements", "interfaceMethod",
+	"typeAssert", "interfaceTypeAssert",
+	// func
+	"getFuncPtr",
+}
+
+// makeDefs generates runtimetypes.go and writes it out after formatting it.
+func makeDefs() error {
+	// Load the runtime package.
+	pkgs, err := packages.Load(&packages.Config{
+		Mode:       packages.NeedSyntax,
+		BuildFlags: []string{"-tags=gc.extalloc"},
+	}, "../src/runtime")
+	if err != nil {
+		return err
+	}
+	if len(pkgs) != 1 {
+		return fmt.Errorf("expected 1 package, got %d", len(pkgs))
+	}
+	runtimePkg := pkgs[0]
+	if len(runtimePkg.Errors) != 0 {
+		return runtimePkg.Errors[0]
+	}
+
+	// Start creating the new Go file.
+	buf := &bytes.Buffer{}
+	buf.WriteString(`// Autogenerated by mkruntimetypes.go, DO NOT EDIT.
+
+package compiler
+
+// This file contains definitions for runtime types and functions, so that the
+// runtime package can be compiled independently of other packages.
+
+import (
+	"go/token"
+	"go/types"
+	"strconv"
+)
+
+// getRuntimeType constructs a new runtime type with the given name. The types
+// constructed here must match the types in the runtime package.
+func (c *compilerContext) getRuntimeType(name string) types.Type {
+	if c.program != nil {
+		return c.program.ImportedPackage("runtime").Type(name).Type()
+	}
+	if typ, ok := c.runtimeTypes[name]; ok {
+		// This type was already created.
+		return typ
+	}
+
+	typeName := types.NewTypeName(token.NoPos, c.runtimePkg, name, nil)
+	named := types.NewNamed(typeName, nil, nil)
+
+	// Make sure recursive types are only defined once.
+	c.runtimeTypes[name] = named
+
+	var fieldTypes []types.Type
+	switch name {
+`)
+	err = makeTypeDefs(buf, runtimePkg)
+	if err != nil {
+		return err
+	}
+	buf.WriteString(`		default:
+		panic("could not find runtime type: runtime." + name)
+	}
+
+	// Create the named struct type.
+	var fields []*types.Var
+	for i, t := range fieldTypes {
+		// Field name doesn't matter: this type is only used to create a LLVM
+		// struct type which don't have field names.
+		fields = append(fields, types.NewField(token.NoPos, nil, "field"+strconv.Itoa(i), t, false))
+	}
+	named.SetUnderlying(types.NewStruct(fields, nil))
+	return named
+}
+
+// getRuntimeFuncType constructs a new runtime function signature with the given
+// name. The function signatures constructed here must match the functions in
+// the runtime package.
+func (c *compilerContext) getRuntimeFuncType(name string) *types.Signature {
+	var params []*types.Var
+	addParam := func(name string, typ types.Type) {
+		params = append(params, types.NewParam(token.NoPos, c.runtimePkg, name, typ))
+	}
+	var results []*types.Var
+	addResult := func(typ types.Type) {
+		results = append(results, types.NewParam(token.NoPos, c.runtimePkg, "", typ))
+	}
+	switch name {
+`)
+
+	err = makeFuncDefs(buf, runtimePkg)
+	if err != nil {
+		return err
+	}
+	buf.WriteString(`	default:
+		panic("unknown runtime call: runtime." + name)
+	}
+	return types.NewSignature(nil, types.NewTuple(params...), types.NewTuple(results...), false)
+}
+`)
+
+	source, err := format.Source(buf.Bytes())
+	if err != nil {
+		// Fallback (useful for investigating errors).
+		source = buf.Bytes()
+	}
+	err2 := ioutil.WriteFile("runtimetypes.go", source, 0666)
+	if err2 != nil {
+		return err2 // error from ioutil.WriteFile
+	}
+	return err // error from format.Source (if any)
+}
+
+// makeTypeDefs generates the switch body of the getRuntimeType function.
+func makeTypeDefs(w io.Writer, runtimePkg *packages.Package) error {
+	typeSpecs := map[string]*ast.TypeSpec{}
+	for _, file := range runtimePkg.Syntax {
+		for _, decl := range file.Decls {
+			switch decl := decl.(type) {
+			case *ast.GenDecl:
+				if decl.Tok != token.TYPE {
+					continue
+				}
+				for _, spec := range decl.Specs {
+					typeSpec := spec.(*ast.TypeSpec)
+					typeSpecs[typeSpec.Name.Name] = typeSpec
+				}
+			}
+		}
+	}
+
+	for _, name := range runtimeTypes {
+		typeSpec := typeSpecs[name]
+		if typeSpec == nil {
+			return fmt.Errorf("could not find type: %s", name)
+		}
+		fmt.Fprintf(w, "\tcase %#v:\n", typeSpec.Name.Name)
+		if name == "channelBlockedList" {
+			fmt.Fprintf(w, "\t\ttaskType := types.NewNamed(types.NewTypeName(token.NoPos, c.taskPkg, \"Task\", nil), nil, nil)\n")
+		}
+		fmt.Fprintf(w, "\t\tfieldTypes = []types.Type{\n")
+		for _, field := range typeSpec.Type.(*ast.StructType).Fields.List {
+			fieldType := getTypeFromExpr(field.Type, typeSpec.Name.Name)
+			for _, ident := range field.Names {
+				fmt.Fprintf(w, "\t\t\t%s, // %s\n", fieldType, ident.Name)
+			}
+		}
+		fmt.Fprintf(w, "\t\t}\n")
+	}
+	return nil
+}
+
+// makeFuncDefs generates the switch body of the getRuntimeFuncType function.
+func makeFuncDefs(w io.Writer, runtimePkg *packages.Package) error {
+	functions := map[string]*ast.FuncDecl{}
+	for _, file := range runtimePkg.Syntax {
+		for _, decl := range file.Decls {
+			switch decl := decl.(type) {
+			case *ast.FuncDecl:
+				functions[decl.Name.Name] = decl
+			default:
+			}
+		}
+	}
+
+	for _, name := range runtimeCalls {
+		decl := functions[name]
+		if decl == nil {
+			return fmt.Errorf("could not find function: %s", name)
+		}
+		fmt.Fprintf(w, "\tcase %#v:\n", decl.Name.Name)
+		for _, field := range decl.Type.Params.List {
+			typeString := getTypeFromExpr(field.Type, "")
+			for _, name := range field.Names {
+				fmt.Fprintf(w, "\t\taddParam(%#v, %s)\n", name.Name, typeString)
+			}
+		}
+		if decl.Type.Results != nil {
+			for _, field := range decl.Type.Results.List {
+				typeString := getTypeFromExpr(field.Type, "")
+				for range field.Names {
+					fmt.Fprintf(w, "\t\taddResult(%s)\n", typeString)
+				}
+				if len(field.Names) == 0 {
+					fmt.Fprintf(w, "\t\taddResult(%s)\n", typeString)
+				}
+			}
+		}
+	}
+	return nil
+}
+
+// getTypeFromExpr returns a string which is a piece of Go code that constructs
+// the type (as given in ast.Expr) using the go/types package.
+func getTypeFromExpr(typ ast.Expr, currentTypeName string) string {
+	switch typ := typ.(type) {
+	case *ast.Ident:
+		if typ.Name == currentTypeName {
+			// Assume a global named "named" which refers to the currently
+			// created named type.
+			return "named"
+		}
+		switch typ.Name {
+		case "bool", "int", "int8", "int16", "int32", "int64", "uint", "uint8", "uint16", "uint32", "uint64", "uintptr", "float32", "float64", "complex64", "complex128", "string", "byte", "rune":
+			// Built-in types.
+			return fmt.Sprintf("types.Typ[types.%s]", strings.Title(typ.Name))
+		case "chanState":
+			// runtime.chanState is a named type, but that doesn't matter when
+			// generating LLVM IR.
+			return fmt.Sprintf("types.Typ[types.Uint8]")
+		default:
+			// Assume that we can simply get the type recursively.
+			return fmt.Sprintf("c.getRuntimeType(%#v)", typ.Name)
+		}
+	case *ast.StarExpr:
+		return fmt.Sprintf("types.NewPointer(%s)", getTypeFromExpr(typ.X, currentTypeName))
+	case *ast.InterfaceType:
+		if len(typ.Methods.List) != 0 {
+			// Unimplemented: interfaces with methods.
+			return "interface{?}"
+		}
+		return "types.NewInterfaceType(nil, nil)"
+	case *ast.ArrayType:
+		// Slices and arrays. Assume the array length is a numeric constant and
+		// not a Go named constant for example.
+		elementType := getTypeFromExpr(typ.Elt, currentTypeName)
+		if typ.Len == nil {
+			return fmt.Sprintf("types.NewSlice(%s)", elementType)
+		}
+		length := typ.Len.(*ast.BasicLit).Value
+		return fmt.Sprintf("types.NewArray(%s, %s)", elementType, length)
+	case *ast.SelectorExpr:
+		s := typ.X.(*ast.Ident).Name + "." + typ.Sel.Name
+		switch s {
+		case "unsafe.Pointer":
+			return "types.Typ[types.UnsafePointer]"
+		case "task.Task":
+			// Assume there is a variable taskType which refers to the task.Task
+			// structure.
+			return "taskType"
+		default:
+			return fmt.Sprintf("<unknown %s>", s)
+		}
+	case *ast.StructType:
+		// Inline struct type.
+		var fields string
+		for _, field := range typ.Fields.List {
+			fieldType := getTypeFromExpr(field.Type, currentTypeName)
+			for _, ident := range field.Names {
+				fields += fmt.Sprintf("\t\t\ttypes.NewField(token.NoPos, nil, %#v, %s, false),\n", ident.Name, fieldType)
+			}
+		}
+		return fmt.Sprintf("types.NewStruct([]*types.Var{\n%s\t\t}, nil)", fields)
+	default:
+		// Dump the raw typ value, for debugging.
+		return fmt.Sprintf("%#v", typ)
+	}
+}
+
+func main() {
+	err := makeDefs()
+	if err != nil {
+		fmt.Fprintln(os.Stderr, "could not create defs:", err)
+		os.Exit(1)
+	}
+}
diff --git a/compiler/runtimetypes.go b/compiler/runtimetypes.go
new file mode 100644
index 000000000..0ce1ab95f
--- /dev/null
+++ b/compiler/runtimetypes.go
@@ -0,0 +1,377 @@
+// Autogenerated by mkruntimetypes.go, DO NOT EDIT.
+
+package compiler
+
+// This file contains definitions for runtime types and functions, so that the
+// runtime package can be compiled independently of other packages.
+
+import (
+	"go/token"
+	"go/types"
+	"strconv"
+)
+
+// getRuntimeType constructs a new runtime type with the given name. The types
+// constructed here must match the types in the runtime package.
+func (c *compilerContext) getRuntimeType(name string) types.Type {
+	if c.program != nil {
+		return c.program.ImportedPackage("runtime").Type(name).Type()
+	}
+	if typ, ok := c.runtimeTypes[name]; ok {
+		// This type was already created.
+		return typ
+	}
+
+	typeName := types.NewTypeName(token.NoPos, c.runtimePkg, name, nil)
+	named := types.NewNamed(typeName, nil, nil)
+
+	// Make sure recursive types are only defined once.
+	c.runtimeTypes[name] = named
+
+	var fieldTypes []types.Type
+	switch name {
+	case "_defer":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr], // callback
+			types.NewPointer(named),  // next
+		}
+	case "_string":
+		fieldTypes = []types.Type{
+			types.NewPointer(types.Typ[types.Byte]), // ptr
+			types.Typ[types.Uintptr],                // length
+		}
+	case "stringIterator":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr], // byteindex
+		}
+	case "hashmap":
+		fieldTypes = []types.Type{
+			types.NewPointer(named),        // next
+			types.Typ[types.UnsafePointer], // buckets
+			types.Typ[types.Uintptr],       // count
+			types.Typ[types.Uint8],         // keySize
+			types.Typ[types.Uint8],         // valueSize
+			types.Typ[types.Uint8],         // bucketBits
+		}
+	case "hashmapBucket":
+		fieldTypes = []types.Type{
+			types.NewArray(types.Typ[types.Uint8], 8), // tophash
+			types.NewPointer(named),                   // next
+		}
+	case "hashmapIterator":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr],                            // bucketNumber
+			types.NewPointer(c.getRuntimeType("hashmapBucket")), // bucket
+			types.Typ[types.Uint8],                              // bucketIndex
+		}
+	case "channel":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr],                                 // elementSize
+			types.Typ[types.Uintptr],                                 // bufSize
+			types.Typ[types.Uint8],                                   // state
+			types.NewPointer(c.getRuntimeType("channelBlockedList")), // blocked
+			types.Typ[types.Uintptr],                                 // bufHead
+			types.Typ[types.Uintptr],                                 // bufTail
+			types.Typ[types.Uintptr],                                 // bufUsed
+			types.Typ[types.UnsafePointer],                           // buf
+		}
+	case "channelBlockedList":
+		taskType := types.NewNamed(types.NewTypeName(token.NoPos, c.taskPkg, "Task", nil), nil, nil)
+		fieldTypes = []types.Type{
+			types.NewPointer(named),                               // next
+			types.NewPointer(taskType),                            // t
+			types.NewPointer(c.getRuntimeType("chanSelectState")), // s
+			types.NewSlice(named),                                 // allSelectOps
+		}
+	case "chanSelectState":
+		fieldTypes = []types.Type{
+			types.NewPointer(c.getRuntimeType("channel")), // ch
+			types.Typ[types.UnsafePointer],                // value
+		}
+	case "_interface":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr],       // typecode
+			types.Typ[types.UnsafePointer], // value
+		}
+	case "interfaceMethodInfo":
+		fieldTypes = []types.Type{
+			types.NewPointer(types.Typ[types.Uint8]), // signature
+			types.Typ[types.Uintptr],                 // funcptr
+		}
+	case "typecodeID":
+		fieldTypes = []types.Type{
+			types.NewPointer(named),  // references
+			types.Typ[types.Uintptr], // length
+		}
+	case "structField":
+		fieldTypes = []types.Type{
+			types.NewPointer(c.getRuntimeType("typecodeID")), // typecode
+			types.NewPointer(types.Typ[types.Uint8]),         // name
+			types.NewPointer(types.Typ[types.Uint8]),         // tag
+			types.Typ[types.Bool],                            // embedded
+		}
+	case "typeInInterface":
+		fieldTypes = []types.Type{
+			types.NewPointer(c.getRuntimeType("typecodeID")),          // typecode
+			types.NewPointer(c.getRuntimeType("interfaceMethodInfo")), // methodSet
+		}
+	case "funcValue":
+		fieldTypes = []types.Type{
+			types.Typ[types.UnsafePointer], // context
+			types.Typ[types.Uintptr],       // id
+		}
+	case "funcValueWithSignature":
+		fieldTypes = []types.Type{
+			types.Typ[types.Uintptr],                         // funcPtr
+			types.NewPointer(c.getRuntimeType("typecodeID")), // signature
+		}
+	default:
+		panic("could not find runtime type: runtime." + name)
+	}
+
+	// Create the named struct type.
+	var fields []*types.Var
+	for i, t := range fieldTypes {
+		// Field name doesn't matter: this type is only used to create a LLVM
+		// struct type which don't have field names.
+		fields = append(fields, types.NewField(token.NoPos, nil, "field"+strconv.Itoa(i), t, false))
+	}
+	named.SetUnderlying(types.NewStruct(fields, nil))
+	return named
+}
+
+// getRuntimeFuncType constructs a new runtime function signature with the given
+// name. The function signatures constructed here must match the functions in
+// the runtime package.
+func (c *compilerContext) getRuntimeFuncType(name string) *types.Signature {
+	var params []*types.Var
+	addParam := func(name string, typ types.Type) {
+		params = append(params, types.NewParam(token.NoPos, c.runtimePkg, name, typ))
+	}
+	var results []*types.Var
+	addResult := func(typ types.Type) {
+		results = append(results, types.NewParam(token.NoPos, c.runtimePkg, "", typ))
+	}
+	switch name {
+	case "_panic":
+		addParam("message", types.NewInterfaceType(nil, nil))
+	case "_recover":
+		addResult(types.NewInterfaceType(nil, nil))
+	case "nilPanic":
+	case "lookupPanic":
+	case "slicePanic":
+	case "chanMakePanic":
+	case "negativeShiftPanic":
+	case "stringEqual":
+		addParam("x", types.Typ[types.String])
+		addParam("y", types.Typ[types.String])
+		addResult(types.Typ[types.Bool])
+	case "stringLess":
+		addParam("x", types.Typ[types.String])
+		addParam("y", types.Typ[types.String])
+		addResult(types.Typ[types.Bool])
+	case "stringConcat":
+		addParam("x", c.getRuntimeType("_string"))
+		addParam("y", c.getRuntimeType("_string"))
+		addResult(c.getRuntimeType("_string"))
+	case "stringFromBytes":
+		addParam("x", types.NewStruct([]*types.Var{
+			types.NewField(token.NoPos, nil, "ptr", types.NewPointer(types.Typ[types.Byte]), false),
+			types.NewField(token.NoPos, nil, "len", types.Typ[types.Uintptr], false),
+			types.NewField(token.NoPos, nil, "cap", types.Typ[types.Uintptr], false),
+		}, nil))
+		addResult(c.getRuntimeType("_string"))
+	case "stringToBytes":
+		addParam("x", c.getRuntimeType("_string"))
+		addResult(types.NewStruct([]*types.Var{
+			types.NewField(token.NoPos, nil, "ptr", types.NewPointer(types.Typ[types.Byte]), false),
+			types.NewField(token.NoPos, nil, "len", types.Typ[types.Uintptr], false),
+			types.NewField(token.NoPos, nil, "cap", types.Typ[types.Uintptr], false),
+		}, nil))
+	case "stringFromRunes":
+		addParam("runeSlice", types.NewSlice(types.Typ[types.Rune]))
+		addResult(c.getRuntimeType("_string"))
+	case "stringToRunes":
+		addParam("s", types.Typ[types.String])
+		addResult(types.NewSlice(types.Typ[types.Rune]))
+	case "stringFromUnicode":
+		addParam("x", types.Typ[types.Rune])
+		addResult(c.getRuntimeType("_string"))
+	case "stringNext":
+		addParam("s", types.Typ[types.String])
+		addParam("it", types.NewPointer(c.getRuntimeType("stringIterator")))
+		addResult(types.Typ[types.Bool])
+		addResult(types.Typ[types.Int])
+		addResult(types.Typ[types.Rune])
+	case "complex64div":
+		addParam("n", types.Typ[types.Complex64])
+		addParam("m", types.Typ[types.Complex64])
+		addResult(types.Typ[types.Complex64])
+	case "complex128div":
+		addParam("n", types.Typ[types.Complex128])
+		addParam("m", types.Typ[types.Complex128])
+		addResult(types.Typ[types.Complex128])
+	case "sliceAppend":
+		addParam("srcBuf", types.Typ[types.UnsafePointer])
+		addParam("elemsBuf", types.Typ[types.UnsafePointer])
+		addParam("srcLen", types.Typ[types.Uintptr])
+		addParam("srcCap", types.Typ[types.Uintptr])
+		addParam("elemsLen", types.Typ[types.Uintptr])
+		addParam("elemSize", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.UnsafePointer])
+		addResult(types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Uintptr])
+	case "sliceCopy":
+		addParam("dst", types.Typ[types.UnsafePointer])
+		addParam("src", types.Typ[types.UnsafePointer])
+		addParam("dstLen", types.Typ[types.Uintptr])
+		addParam("srcLen", types.Typ[types.Uintptr])
+		addParam("elemSize", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Int])
+	case "alloc":
+		addParam("size", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.UnsafePointer])
+	case "trackPointer":
+		addParam("ptr", types.Typ[types.UnsafePointer])
+	case "printbool":
+		addParam("b", types.Typ[types.Bool])
+	case "printint8":
+		addParam("n", types.Typ[types.Int8])
+	case "printuint8":
+		addParam("n", types.Typ[types.Uint8])
+	case "printint16":
+		addParam("n", types.Typ[types.Int16])
+	case "printuint16":
+		addParam("n", types.Typ[types.Uint16])
+	case "printint32":
+		addParam("n", types.Typ[types.Int32])
+	case "printuint32":
+		addParam("n", types.Typ[types.Uint32])
+	case "printint64":
+		addParam("n", types.Typ[types.Int64])
+	case "printuint64":
+		addParam("n", types.Typ[types.Uint64])
+	case "printfloat32":
+		addParam("v", types.Typ[types.Float32])
+	case "printfloat64":
+		addParam("v", types.Typ[types.Float64])
+	case "printcomplex64":
+		addParam("c", types.Typ[types.Complex64])
+	case "printcomplex128":
+		addParam("c", types.Typ[types.Complex128])
+	case "printstring":
+		addParam("s", types.Typ[types.String])
+	case "printspace":
+	case "printnl":
+	case "printptr":
+		addParam("ptr", types.Typ[types.Uintptr])
+	case "printmap":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+	case "printitf":
+		addParam("msg", types.NewInterfaceType(nil, nil))
+	case "hashmapMake":
+		addParam("keySize", types.Typ[types.Uint8])
+		addParam("valueSize", types.Typ[types.Uint8])
+		addParam("sizeHint", types.Typ[types.Uintptr])
+		addResult(types.NewPointer(c.getRuntimeType("hashmap")))
+	case "hashmapLen":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addResult(types.Typ[types.Int])
+	case "hashmapNext":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("it", types.NewPointer(c.getRuntimeType("hashmapIterator")))
+		addParam("key", types.Typ[types.UnsafePointer])
+		addParam("value", types.Typ[types.UnsafePointer])
+		addResult(types.Typ[types.Bool])
+	case "hashmapStringGet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.String])
+		addParam("value", types.Typ[types.UnsafePointer])
+		addParam("valueSize", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Bool])
+	case "hashmapStringSet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.String])
+		addParam("value", types.Typ[types.UnsafePointer])
+	case "hashmapStringDelete":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.String])
+	case "hashmapInterfaceGet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.NewInterfaceType(nil, nil))
+		addParam("value", types.Typ[types.UnsafePointer])
+		addParam("valueSize", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Bool])
+	case "hashmapInterfaceSet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.NewInterfaceType(nil, nil))
+		addParam("value", types.Typ[types.UnsafePointer])
+	case "hashmapInterfaceDelete":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.NewInterfaceType(nil, nil))
+	case "hashmapBinaryGet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.UnsafePointer])
+		addParam("value", types.Typ[types.UnsafePointer])
+		addParam("valueSize", types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Bool])
+	case "hashmapBinarySet":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.UnsafePointer])
+		addParam("value", types.Typ[types.UnsafePointer])
+	case "hashmapBinaryDelete":
+		addParam("m", types.NewPointer(c.getRuntimeType("hashmap")))
+		addParam("key", types.Typ[types.UnsafePointer])
+	case "tryChanSelect":
+		addParam("recvbuf", types.Typ[types.UnsafePointer])
+		addParam("states", types.NewSlice(c.getRuntimeType("chanSelectState")))
+		addResult(types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Bool])
+	case "chanMake":
+		addParam("elementSize", types.Typ[types.Uintptr])
+		addParam("bufSize", types.Typ[types.Uintptr])
+		addResult(types.NewPointer(c.getRuntimeType("channel")))
+	case "chanSend":
+		addParam("ch", types.NewPointer(c.getRuntimeType("channel")))
+		addParam("value", types.Typ[types.UnsafePointer])
+	case "chanRecv":
+		addParam("ch", types.NewPointer(c.getRuntimeType("channel")))
+		addParam("value", types.Typ[types.UnsafePointer])
+		addResult(types.Typ[types.Bool])
+	case "chanClose":
+		addParam("ch", types.NewPointer(c.getRuntimeType("channel")))
+	case "chanSelect":
+		addParam("recvbuf", types.Typ[types.UnsafePointer])
+		addParam("states", types.NewSlice(c.getRuntimeType("chanSelectState")))
+		addParam("ops", types.NewSlice(c.getRuntimeType("channelBlockedList")))
+		addResult(types.Typ[types.Uintptr])
+		addResult(types.Typ[types.Bool])
+	case "deadlock":
+	case "interfaceEqual":
+		addParam("x", types.NewInterfaceType(nil, nil))
+		addParam("y", types.NewInterfaceType(nil, nil))
+		addResult(types.Typ[types.Bool])
+	case "interfaceImplements":
+		addParam("typecode", types.Typ[types.Uintptr])
+		addParam("interfaceMethodSet", types.NewPointer(types.NewPointer(types.Typ[types.Uint8])))
+		addResult(types.Typ[types.Bool])
+	case "interfaceMethod":
+		addParam("typecode", types.Typ[types.Uintptr])
+		addParam("interfaceMethodSet", types.NewPointer(types.NewPointer(types.Typ[types.Uint8])))
+		addParam("signature", types.NewPointer(types.Typ[types.Uint8]))
+		addResult(types.Typ[types.Uintptr])
+	case "typeAssert":
+		addParam("actualType", types.Typ[types.Uintptr])
+		addParam("assertedType", types.NewPointer(c.getRuntimeType("typecodeID")))
+		addResult(types.Typ[types.Bool])
+	case "interfaceTypeAssert":
+		addParam("ok", types.Typ[types.Bool])
+	case "getFuncPtr":
+		addParam("val", c.getRuntimeType("funcValue"))
+		addParam("signature", types.NewPointer(c.getRuntimeType("typecodeID")))
+		addResult(types.Typ[types.Uintptr])
+	default:
+		panic("unknown runtime call: runtime." + name)
+	}
+	return types.NewSignature(nil, types.NewTuple(params...), types.NewTuple(results...), false)
+}
diff --git a/compiler/symbol.go b/compiler/symbol.go
index 25b27a947..91005f186 100644
--- a/compiler/symbol.go
+++ b/compiler/symbol.go
@@ -51,26 +51,37 @@ type functionInfo struct {
 // it if needed. It can later be filled with compilerContext.createFunction().
 func (c *compilerContext) getFunction(fn *ssa.Function) llvm.Value {
 	info := c.getFunctionInfo(fn)
+	return c.getFunctionRaw(fn.Signature, info)
+}
+
+func (c *compilerContext) getFunctionRaw(sig *types.Signature, info functionInfo) llvm.Value {
 	llvmFn := c.mod.NamedFunction(info.linkName)
 	if !llvmFn.IsNil() {
 		return llvmFn
 	}
 
 	var retType llvm.Type
-	if fn.Signature.Results() == nil {
+	if sig.Results() == nil {
 		retType = c.ctx.VoidType()
-	} else if fn.Signature.Results().Len() == 1 {
-		retType = c.getLLVMType(fn.Signature.Results().At(0).Type())
+	} else if sig.Results().Len() == 1 {
+		retType = c.getLLVMType(sig.Results().At(0).Type())
 	} else {
-		results := make([]llvm.Type, 0, fn.Signature.Results().Len())
-		for i := 0; i < fn.Signature.Results().Len(); i++ {
-			results = append(results, c.getLLVMType(fn.Signature.Results().At(i).Type()))
+		results := make([]llvm.Type, 0, sig.Results().Len())
+		for i := 0; i < sig.Results().Len(); i++ {
+			results = append(results, c.getLLVMType(sig.Results().At(i).Type()))
 		}
 		retType = c.ctx.StructType(results, false)
 	}
 
 	var paramInfos []paramInfo
-	for _, param := range fn.Params {
+	params := []*types.Var{}
+	if sig.Recv() != nil {
+		params = append(params, sig.Recv())
+	}
+	for i := 0; i < sig.Params().Len(); i++ {
+		params = append(params, sig.Params().At(i))
+	}
+	for _, param := range params {
 		paramType := c.getLLVMType(param.Type())
 		paramFragmentInfos := expandFormalParamType(paramType, param.Name(), param.Type())
 		paramInfos = append(paramInfos, paramFragmentInfos...)
diff --git a/compiler/testdata/basic.go b/compiler/testdata/basic.go
index bcd5a28ed..51a4ef7c1 100644
--- a/compiler/testdata/basic.go
+++ b/compiler/testdata/basic.go
@@ -3,3 +3,11 @@ package main
 func add(x, y int) int {
 	return x + y
 }
+
+func stringEqual(s string) bool {
+	return s == "s"
+}
+
+func closeChan(ch chan int) {
+	close(ch)
+}
diff --git a/compiler/testdata/basic.ll b/compiler/testdata/basic.ll
index c9c9b9e27..52a504676 100644
--- a/compiler/testdata/basic.ll
+++ b/compiler/testdata/basic.ll
@@ -1,13 +1,41 @@
 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "armv7m-none-eabi"
 
+%runtime.channel = type { i32, i32, i8, %runtime.channelBlockedList*, i32, i32, i32, i8* }
+%runtime.channelBlockedList = type { %runtime.channelBlockedList*, %"internal/task.Task"*, %runtime.chanSelectState*, { %runtime.channelBlockedList*, i32, i32 } }
+%"internal/task.Task" = type opaque
+%runtime.chanSelectState = type { %runtime.channel*, i8* }
+%runtime._string = type { i8*, i32 }
+
+@"main.stringEqual$string" = internal unnamed_addr constant [1 x i8] c"s"
+
 define internal i32 @main.add(i32 %x, i32 %y, i8* %context, i8* %parentHandle) unnamed_addr {
 entry:
   %0 = add i32 %x, %y
   ret i32 %0
 }
 
+define internal void @main.closeChan(%runtime.channel* dereferenceable_or_null(32) %ch, i8* %context, i8* %parentHandle) unnamed_addr {
+entry:
+  call void @runtime.chanClose(%runtime.channel* %ch, i8* undef, i8* null)
+  ret void
+}
+
+declare void @runtime.chanClose(%runtime.channel* dereferenceable_or_null(32), i8*, i8*)
+
 define internal void @main.init(i8* %context, i8* %parentHandle) unnamed_addr {
 entry:
   ret void
 }
+
+define internal i1 @main.stringEqual(i8* %s.data, i32 %s.len, i8* %context, i8* %parentHandle) unnamed_addr {
+entry:
+  %0 = insertvalue %runtime._string zeroinitializer, i8* %s.data, 0
+  %1 = insertvalue %runtime._string %0, i32 %s.len, 1
+  %2 = extractvalue %runtime._string %1, 0
+  %3 = extractvalue %runtime._string %1, 1
+  %4 = call i1 @runtime.stringEqual(i8* %2, i32 %3, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @"main.stringEqual$string", i32 0, i32 0), i32 1, i8* undef, i8* null)
+  ret i1 %4
+}
+
+declare i1 @runtime.stringEqual(i8*, i32, i8*, i32, i8*, i8*)