func (tm *TypeMap) interfaceRuntimeType(tstr string, i *types.Interface) (global, ptr llvm.Value) {
	rtype := tm.makeRtype(i, reflect.Interface)
	interfaceType := llvm.ConstNull(tm.runtimeInterfaceType)
	global, ptr = tm.makeRuntimeTypeGlobal(interfaceType)
	tm.types.record(tstr, global, ptr)
	interfaceType = llvm.ConstInsertValue(interfaceType, rtype, []uint32{0})
	methodset := i.MethodSet()
	imethods := make([]llvm.Value, methodset.Len())
	for index := 0; index < methodset.Len(); index++ {
		method := methodset.At(index).Obj()
		imethod := llvm.ConstNull(tm.runtimeImethod)
		name := tm.globalStringPtr(method.Name())
		name = llvm.ConstBitCast(name, tm.runtimeImethod.StructElementTypes()[0])
		//pkgpath := tm.globalStringPtr(tm.functions.objectdata[method].Package.Path())
		//pkgpath = llvm.ConstBitCast(name, tm.runtimeImethod.StructElementTypes()[1])
		mtyp := tm.ToRuntime(method.Type())
		imethod = llvm.ConstInsertValue(imethod, name, []uint32{0})
		//imethod = llvm.ConstInsertValue(imethod, pkgpath, []uint32{1})
		imethod = llvm.ConstInsertValue(imethod, mtyp, []uint32{2})
		imethods[index] = imethod
	}
	imethodsSliceType := tm.runtimeInterfaceType.StructElementTypes()[1]
	imethodsSlice := tm.makeSlice(imethods, imethodsSliceType)
	interfaceType = llvm.ConstInsertValue(interfaceType, imethodsSlice, []uint32{1})
	global.SetInitializer(interfaceType)
	return global, ptr
}

func (tm *TypeMap) interfaceRuntimeType(i *types.Interface) (global, ptr llvm.Value) {
	rtype := tm.makeRtype(i, reflect.Interface)
	interfaceType := llvm.ConstNull(tm.runtime.interfaceType.llvm)
	global, ptr = tm.makeRuntimeTypeGlobal(interfaceType, typeString(i))
	tm.types.Set(i, runtimeTypeInfo{global, ptr})
	interfaceType = llvm.ConstInsertValue(interfaceType, rtype, []uint32{0})
	methodset := i.MethodSet()
	imethods := make([]llvm.Value, methodset.Len())
	for index := 0; index < methodset.Len(); index++ {
		method := methodset.At(index).Obj()
		imethod := llvm.ConstNull(tm.runtime.imethod.llvm)
		name := tm.globalStringPtr(method.Name())
		name = llvm.ConstBitCast(name, tm.runtime.imethod.llvm.StructElementTypes()[0])
		mtyp := tm.ToRuntime(method.Type())
		imethod = llvm.ConstInsertValue(imethod, name, []uint32{0})
		if !ast.IsExported(method.Name()) {
			pkgpath := tm.globalStringPtr(method.Pkg().Path())
			pkgpath = llvm.ConstBitCast(pkgpath, tm.runtime.imethod.llvm.StructElementTypes()[1])
			imethod = llvm.ConstInsertValue(imethod, pkgpath, []uint32{1})
		}
		imethod = llvm.ConstInsertValue(imethod, mtyp, []uint32{2})
		imethods[index] = imethod
	}
	imethodsSliceType := tm.runtime.interfaceType.llvm.StructElementTypes()[1]
	imethodsSlice := tm.makeSlice(imethods, imethodsSliceType)
	interfaceType = llvm.ConstInsertValue(interfaceType, imethodsSlice, []uint32{1})
	global.SetInitializer(interfaceType)
	return global, ptr
}

func sortedMethodNames(typ *types.Interface) []string {
	n := typ.NumMethods()
	list := make([]string, n)
	for i := range list {
		list[i] = typ.Method(i).Name()
	}
	sort.Strings(list)
	return list
}

// TODO interfaces' methods should probably
// out of go/types already sorted. If not,
// cache sortedMethods.
func sortedMethods(iface *types.Interface) []*types.Func {
	objects := make([]types.Object, iface.NumMethods())
	for i := 0; i < len(objects); i++ {
		objects[i] = iface.Method(i)
	}
	sort.Sort(objectsByName(objects))
	methods := make([]*types.Func, len(objects))
	for i, o := range objects {
		methods[i] = o.(*types.Func)
	}
	return methods
}

// checkInterface checks that the method set of x implements the
// interface itype.
// On success it returns "", on failure, an error message.
//
func checkInterface(i *interpreter, itype *types.Interface, x iface) string {
	mset := findMethodSet(i, x.t)
	it := itype.Underlying().(*types.Interface)
	for i, n := 0, it.NumMethods(); i < n; i++ {
		m := it.Method(i)
		id := ssa.MakeId(m.Name(), m.Pkg())
		if mset[id] == nil {
			return fmt.Sprintf("interface conversion: %v is not %v: missing method %v", x.t, itype, id)
		}
	}
	return "" // ok
}

func (tm *llvmTypeMap) interfaceLLVMType(i *types.Interface, name string) llvm.Type {
	if typ, ok := tm.types.At(i).(llvm.Type); ok {
		return typ
	}
	// interface{} is represented as {type, value},
	// and non-empty interfaces are represented as {itab, value}.
	i8ptr := llvm.PointerType(llvm.Int8Type(), 0)
	rtypeType := i8ptr
	valueType := i8ptr
	if name == "" {
		name = i.String()
	}
	typ := llvm.GlobalContext().StructCreateNamed(name)
	typ.StructSetBody([]llvm.Type{rtypeType, valueType}, false)
	return typ
}

func (tm *LLVMTypeMap) interfaceLLVMType(tstr string, i *types.Interface) llvm.Type {
	typ, ok := tm.types[tstr]
	if !ok {
		typ = llvm.GlobalContext().StructCreateNamed("")
		tm.types[tstr] = typ
		valptr_type := llvm.PointerType(llvm.Int8Type(), 0)
		typptr_type := valptr_type // runtimeType may not be defined yet
		elements := make([]llvm.Type, 2+i.NumMethods())
		elements[0] = typptr_type // type
		elements[1] = valptr_type // value
		for n, m := range sortedMethods(i) {
			fntype := m.Type()
			elements[n+2] = tm.ToLLVM(fntype).StructElementTypes()[0]
		}
		typ.StructSetBody(elements, false)
	}
	return typ
}

func (w *Walker) emitIfaceType(name string, typ *types.Interface) {
	pop := w.pushScope("type " + name + " interface")

	var methodNames []string
	complete := true
	mset := typ.MethodSet()
	for i, n := 0, mset.Len(); i < n; i++ {
		m := mset.At(i).Obj().(*types.Func)
		if !m.IsExported() {
			complete = false
			continue
		}
		methodNames = append(methodNames, m.Name())
		w.emitf("%s%s", m.Name(), w.signatureString(m.Type().(*types.Signature)))
	}

	if !complete {
		// The method set has unexported methods, so all the
		// implementations are provided by the same package,
		// so the method set can be extended. Instead of recording
		// the full set of names (below), record only that there were
		// unexported methods. (If the interface shrinks, we will notice
		// because a method signature emitted during the last loop
		// will disappear.)
		w.emitf("unexported methods")
	}

	pop()

	if !complete {
		return
	}

	if len(methodNames) == 0 {
		w.emitf("type %s interface {}", name)
		return
	}

	sort.Strings(methodNames)
	w.emitf("type %s interface { %s }", name, strings.Join(methodNames, ", "))
}

func (tm *TypeMap) interfaceRuntimeType(i *types.Interface) (global, ptr llvm.Value) {
	rtype := tm.makeRtype(i, reflect.Interface)
	interfaceType := llvm.ConstNull(tm.runtimeInterfaceType)
	interfaceType = llvm.ConstInsertValue(interfaceType, rtype, []uint32{0})

	imethods := make([]llvm.Value, i.NumMethods())
	for index, method := range sortedMethods(i) {
		//name, pkgPath, type
		imethod := llvm.ConstNull(tm.runtimeImethod)
		name := tm.globalStringPtr(method.Name())
		name = llvm.ConstBitCast(name, tm.runtimeImethod.StructElementTypes()[0])

		imethod = llvm.ConstInsertValue(imethod, name, []uint32{0})
		//imethod = llvm.ConstInsertValue(imethod, , []uint32{1})
		//imethod = llvm.ConstInsertValue(imethod, , []uint32{2})
		imethods[index] = imethod
	}

	var imethodsGlobalPtr llvm.Value
	imethodPtrType := llvm.PointerType(tm.runtimeImethod, 0)
	if len(imethods) > 0 {
		imethodsArray := llvm.ConstArray(tm.runtimeImethod, imethods)
		imethodsGlobalPtr = llvm.AddGlobal(tm.module, imethodsArray.Type(), "")
		imethodsGlobalPtr.SetInitializer(imethodsArray)
		imethodsGlobalPtr = llvm.ConstBitCast(imethodsGlobalPtr, imethodPtrType)
	} else {
		imethodsGlobalPtr = llvm.ConstNull(imethodPtrType)
	}

	len_ := llvm.ConstInt(tm.inttype, uint64(i.NumMethods()), false)
	imethodsSliceType := tm.runtimeInterfaceType.StructElementTypes()[1]
	imethodsSlice := llvm.ConstNull(imethodsSliceType)
	imethodsSlice = llvm.ConstInsertValue(imethodsSlice, imethodsGlobalPtr, []uint32{0})
	imethodsSlice = llvm.ConstInsertValue(imethodsSlice, len_, []uint32{1})
	imethodsSlice = llvm.ConstInsertValue(imethodsSlice, len_, []uint32{2})
	interfaceType = llvm.ConstInsertValue(interfaceType, imethodsSlice, []uint32{1})
	return tm.makeRuntimeTypeGlobal(interfaceType)
}

func (tm *LLVMTypeMap) interfaceLLVMType(tstr string, i *types.Interface) llvm.Type {
	typ, ok := tm.types[tstr]
	if !ok {
		typ = llvm.GlobalContext().StructCreateNamed("")
		tm.types[tstr] = typ
		valptr_type := llvm.PointerType(llvm.Int8Type(), 0)
		typptr_type := valptr_type // runtimeType may not be defined yet
		elements := make([]llvm.Type, 2+i.NumMethods())
		elements[0] = typptr_type // type
		elements[1] = valptr_type // value
		for n := 0; n < i.NumMethods(); n++ {
			// Add an opaque pointer parameter to the function for the
			// struct pointer. Take a copy of the Type here, so we don't
			// change how the Interface's TypeString is determined.
			m := i.Method(n)
			fntype := m.Type()
			elements[n+2] = tm.ToLLVM(fntype).StructElementTypes()[0]
		}
		typ.StructSetBody(elements, false)
	}
	return typ
}

// convertI2I converts an interface to another interface.
func (v *LLVMValue) convertI2I(iface *types.Interface) (result *LLVMValue, success *LLVMValue) {
	c := v.compiler
	builder := v.compiler.builder
	src_typ := v.Type().Underlying()
	val := v.LLVMValue()

	zero_iface_struct := llvm.ConstNull(c.types.ToLLVM(iface))
	iface_struct := zero_iface_struct
	dynamicType := builder.CreateExtractValue(val, 0, "")
	receiver := builder.CreateExtractValue(val, 1, "")

	// TODO check whether the functions in the struct take
	// value or pointer receivers.

	// TODO handle dynamic interface conversion (non-subset).
	srciface := src_typ.(*types.Interface)
	for i := 0; i < iface.NumMethods(); i++ {
		m := iface.Method(i)

		// FIXME sort methods somewhere, make loop linear.
		var mi int
		for ; mi < srciface.NumMethods(); mi++ {
			if srciface.Method(i).Name() == m.Name() {
				break
			}
		}

		if mi >= srciface.NumMethods() {
			goto check_dynamic
		} else {
			fptr := builder.CreateExtractValue(val, mi+2, "")
			iface_struct = builder.CreateInsertValue(iface_struct, fptr, i+2, "")
		}
	}
	iface_struct = builder.CreateInsertValue(iface_struct, dynamicType, 0, "")
	iface_struct = builder.CreateInsertValue(iface_struct, receiver, 1, "")
	result = c.NewValue(iface_struct, iface)
	success = c.NewValue(llvm.ConstAllOnes(llvm.Int1Type()), types.Typ[types.Bool])
	return result, success

check_dynamic:
	runtimeConvertI2I := c.NamedFunction("runtime.convertI2I", "func f(typ, from, to uintptr) bool")
	llvmUintptr := runtimeConvertI2I.Type().ElementType().ParamTypes()[0]

	var vptr llvm.Value
	if v.pointer != nil {
		vptr = v.pointer.LLVMValue()
	} else {
		vptr = c.builder.CreateAlloca(val.Type(), "")
		c.builder.CreateStore(val, vptr)
	}

	runtimeType := c.builder.CreatePtrToInt(c.types.ToRuntime(iface), llvmUintptr, "")
	from := c.builder.CreatePtrToInt(vptr, llvmUintptr, "")
	to := c.builder.CreateAlloca(iface_struct.Type(), "")
	c.builder.CreateStore(iface_struct, to)
	toUintptr := c.builder.CreatePtrToInt(to, llvmUintptr, "")
	args := []llvm.Value{runtimeType, from, toUintptr}
	ok := c.builder.CreateCall(runtimeConvertI2I, args, "")

	value := c.builder.CreateLoad(to, "")
	value = c.builder.CreateSelect(ok, value, zero_iface_struct, "")
	result = c.NewValue(value, iface)
	success = c.NewValue(ok, types.Typ[types.Bool])
	return result, success
}

// convertV2I converts a value to an interface.
func (v *LLVMValue) convertV2I(iface *types.Interface) *LLVMValue {
	var srcname *types.Named
	srctyp := v.Type()
	if name, isname := srctyp.(*types.Named); isname {
		srcname = name
		srctyp = name.Underlying()
	}

	var isptr bool
	if p, fromptr := srctyp.(*types.Pointer); fromptr {
		isptr = true
		srctyp = p.Elem()
		if name, isname := srctyp.(*types.Named); isname {
			srcname = name
			srctyp = name.Underlying()
		}
	}

	iface_struct_type := v.compiler.types.ToLLVM(iface)
	element_types := iface_struct_type.StructElementTypes()
	zero_iface_struct := llvm.ConstNull(iface_struct_type)
	iface_struct := zero_iface_struct

	builder := v.compiler.builder
	var ptr llvm.Value
	lv := v.LLVMValue()
	if lv.Type().TypeKind() == llvm.PointerTypeKind {
		ptr = builder.CreateBitCast(lv, element_types[1], "")
	} else {
		// If the value fits exactly in a pointer, then we can just
		// bitcast it. Otherwise we need to malloc, and create a shim
		// function to load the receiver.
		c := v.compiler
		ptrsize := c.target.PointerSize()
		if c.target.TypeStoreSize(lv.Type()) <= uint64(ptrsize) {
			bits := c.target.TypeSizeInBits(lv.Type())
			if bits > 0 {
				lv = c.coerce(lv, llvm.IntType(int(bits)))
				ptr = builder.CreateIntToPtr(lv, element_types[1], "")
			} else {
				ptr = llvm.ConstNull(element_types[1])
			}
		} else {
			if lv.IsConstant() {
				ptr = llvm.AddGlobal(c.module.Module, lv.Type(), "")
				ptr.SetInitializer(lv)
			} else {
				ptr = c.createTypeMalloc(lv.Type())
				builder.CreateStore(lv, ptr)
			}
			ptr = builder.CreateBitCast(ptr, element_types[1], "")
			isptr = true
		}
	}
	runtimeType := v.compiler.types.ToRuntime(v.Type())
	runtimeType = builder.CreateBitCast(runtimeType, element_types[0], "")
	iface_struct = builder.CreateInsertValue(iface_struct, runtimeType, 0, "")
	iface_struct = builder.CreateInsertValue(iface_struct, ptr, 1, "")

	if srcname != nil {
		// Look up the method by name.
		for i := 0; i < iface.NumMethods(); i++ {
			m := iface.Method(i)
			method := v.compiler.methods(srcname).lookup(m.Name(), isptr)
			methodident := v.compiler.objectdata[method].Ident
			llvm_value := v.compiler.Resolve(methodident).LLVMValue()
			llvm_value = builder.CreateExtractValue(llvm_value, 0, "")
			llvm_value = builder.CreateBitCast(llvm_value, element_types[i+2], "")
			iface_struct = builder.CreateInsertValue(iface_struct, llvm_value, i+2, "")
		}
	}

	return v.compiler.NewValue(iface_struct, iface)
}

// promoteInterfaceMethod promotes an interface method to a type
// which has embedded the interface.
//
// TODO consolidate this and promoteMethod.
func (c *compiler) promoteInterfaceMethod(iface *types.Interface, methodIndex int, recv types.Type, indices []int) types.Object {
	m := iface.Method(methodIndex)
	var pkg *types.Package
	if recv, ok := recv.(*types.Named); ok {
		pkg = c.objectdata[recv.Obj()].Package
	}
	recvvar := types.NewVar(pkg, "", recv)
	sig := m.Type().(*types.Signature)
	sig = types.NewSignature(recvvar, sig.Params(), sig.Results(), sig.IsVariadic())
	f := &synthFunc{pkg: pkg, name: m.Name(), typ: sig}
	ident := ast.NewIdent(f.Name())

	var isptr bool
	if ptr, ok := recv.(*types.Pointer); ok {
		isptr = true
		recv = ptr.Elem()
	}

	c.objects[ident] = f
	c.objectdata[f] = &ObjectData{Ident: ident, Package: pkg}

	if pkg == nil || pkg == c.pkg {
		if currblock := c.builder.GetInsertBlock(); !currblock.IsNil() {
			defer c.builder.SetInsertPointAtEnd(currblock)
		}
		llvmfn := c.Resolve(ident).LLVMValue()
		llvmfn = c.builder.CreateExtractValue(llvmfn, 0, "")
		llvmfn.SetLinkage(llvm.LinkOnceODRLinkage)
		entry := llvm.AddBasicBlock(llvmfn, "entry")
		c.builder.SetInsertPointAtEnd(entry)

		args := llvmfn.Params()
		ifaceval := args[0]
		if !isptr {
			ptr := c.builder.CreateAlloca(ifaceval.Type(), "")
			c.builder.CreateStore(ifaceval, ptr)
			ifaceval = ptr
		}
		for _, i := range indices {
			if i == -1 {
				ifaceval = c.builder.CreateLoad(ifaceval, "")
			} else {
				ifaceval = c.builder.CreateStructGEP(ifaceval, i, "")
			}
		}

		recvarg := c.builder.CreateExtractValue(ifaceval, 0, "")
		ifn := c.builder.CreateExtractValue(ifaceval, methodIndex+2, "")

		// Add the receiver argument type.
		fntyp := ifn.Type().ElementType()
		returnType := fntyp.ReturnType()
		paramTypes := fntyp.ParamTypes()
		paramTypes = append([]llvm.Type{recvarg.Type()}, paramTypes...)
		vararg := fntyp.IsFunctionVarArg()
		fntyp = llvm.FunctionType(returnType, paramTypes, vararg)
		fnptrtyp := llvm.PointerType(fntyp, 0)
		ifn = c.builder.CreateBitCast(ifn, fnptrtyp, "")

		args[0] = recvarg
		result := c.builder.CreateCall(ifn, args, "")
		if sig.Results().Len() == 0 {
			c.builder.CreateRetVoid()
		} else {
			c.builder.CreateRet(result)
		}
	}

	return f
}

// isSuperinterface returns true if x is a superinterface of y,
// i.e.  x's methods are a subset of y's.
//
func isSuperinterface(x, y *types.Interface) bool {
	if y.NumMethods() < x.NumMethods() {
		return false
	}
	// TODO(adonovan): opt: this is quadratic.
outer:
	for i, n := 0, x.NumMethods(); i < n; i++ {
		xm := x.Method(i)
		for j, m := 0, y.NumMethods(); j < m; j++ {
			ym := y.Method(j)
			if MakeId(xm.Name(), xm.Pkg()) == MakeId(ym.Name(), ym.Pkg()) {
				if !types.IsIdentical(xm.Type(), ym.Type()) {
					return false // common name but conflicting types
				}
				continue outer
			}
		}
		return false // y doesn't have this method
	}
	return true
}