func (tm *TypeMap) makeAlgorithmTable(t types.Type) llvm.Value {
	// TODO set these to actual functions.
	hashAlg := llvm.ConstNull(llvm.PointerType(tm.hashAlgFunctionType, 0))
	printAlg := llvm.ConstNull(llvm.PointerType(tm.printAlgFunctionType, 0))
	copyAlg := llvm.ConstNull(llvm.PointerType(tm.copyAlgFunctionType, 0))

	const eqalgsig = "func(uintptr, unsafe.Pointer, unsafe.Pointer) bool"
	var equalAlg llvm.Value
	switch t := t.(type) {
	case *types.Basic:
		switch t.Kind() {
		case types.String:
			equalAlg = tm.functions.NamedFunction("runtime.streqalg", eqalgsig)
		case types.Float32:
			equalAlg = tm.functions.NamedFunction("runtime.f32eqalg", eqalgsig)
		case types.Float64:
			equalAlg = tm.functions.NamedFunction("runtime.f64eqalg", eqalgsig)
		case types.Complex64:
			equalAlg = tm.functions.NamedFunction("runtime.c64eqalg", eqalgsig)
		case types.Complex128:
			equalAlg = tm.functions.NamedFunction("runtime.c128eqalg", eqalgsig)
		}
	}
	if equalAlg.IsNil() {
		equalAlg = tm.functions.NamedFunction("runtime.memequal", eqalgsig)
	}
	elems := []llvm.Value{hashAlg, equalAlg, printAlg, copyAlg}
	return llvm.ConstStruct(elems, false)
}

func (c *compiler) tollvmDebugDescriptor(t types.Type) llvm.DebugDescriptor {
	switch t := t.(type) {
	case *types.Pointer:
		return llvm.NewPointerDerivedType(c.tollvmDebugDescriptor(t.Elem()))
	case nil:
		return void_debug_type
	}
	bt := &llvm.BasicTypeDescriptor{
		Name:      c.types.TypeString(t),
		Size:      uint64(c.types.Sizeof(t) * 8),
		Alignment: uint64(c.types.Alignof(t) * 8),
	}
	if basic, ok := t.(*types.Basic); ok {
		switch bi := basic.Info(); {
		case bi&types.IsBoolean != 0:
			bt.TypeEncoding = llvm.DW_ATE_boolean
		case bi&types.IsUnsigned != 0:
			bt.TypeEncoding = llvm.DW_ATE_unsigned
		case bi&types.IsInteger != 0:
			bt.TypeEncoding = llvm.DW_ATE_signed
		case bi&types.IsFloat != 0:
			bt.TypeEncoding = llvm.DW_ATE_float
		}
	}
	return bt
}

func typeTypeToJson(t types.Type) interface{} {
	if t != nil {
		return t.String()
	} else {
		return nil
	}
}

func (tm *llvmTypeMap) makeLLVMType(t types.Type, name string) llvm.Type {
	switch t := t.(type) {
	case *types.Basic:
		return tm.basicLLVMType(t)
	case *types.Array:
		return tm.arrayLLVMType(t)
	case *types.Slice:
		return tm.sliceLLVMType(t, name)
	case *types.Struct:
		return tm.structLLVMType(t, name)
	case *types.Pointer:
		return tm.pointerLLVMType(t)
	case *types.Interface:
		return tm.interfaceLLVMType(t, name)
	case *types.Map:
		return tm.mapLLVMType(t)
	case *types.Chan:
		return tm.chanLLVMType(t)
	case *types.Named:
		// First we set ptrstandin, in case we've got a recursive pointer.
		if _, ok := t.Underlying().(*types.Pointer); ok {
			tm.types.Set(t, tm.ptrstandin)
		}
		return tm.nameLLVMType(t)
	}
	panic(fmt.Errorf("unhandled: %T", t))
}

// lockPath returns a typePath describing the location of a lock value
// contained in typ. If there is no contained lock, it returns nil.
func lockPath(tpkg *types.Package, typ types.Type) typePath {
	if typ == nil {
		return nil
	}

	// We're only interested in the case in which the underlying
	// type is a struct. (Interfaces and pointers are safe to copy.)
	styp, ok := typ.Underlying().(*types.Struct)
	if !ok {
		return nil
	}

	// We're looking for cases in which a reference to this type
	// can be locked, but a value cannot. This differentiates
	// embedded interfaces from embedded values.
	if plock := types.NewMethodSet(types.NewPointer(typ)).Lookup(tpkg, "Lock"); plock != nil {
		if lock := types.NewMethodSet(typ).Lookup(tpkg, "Lock"); lock == nil {
			return []types.Type{typ}
		}
	}

	nfields := styp.NumFields()
	for i := 0; i < nfields; i++ {
		ftyp := styp.Field(i).Type()
		subpath := lockPath(tpkg, ftyp)
		if subpath != nil {
			return append(subpath, typ)
		}
	}

	return nil
}

// makeImethodThunk returns a synthetic thunk function permitting a
// method id of interface typ to be called like a standalone function,
// e.g.:
//
//   type I interface { f(x int) R }
//   m := I.f  // thunk
//   var i I
//   m(i, 0)
//
// The thunk is defined as if by:
//
//   func I.f(i I, x int, ...) R {
//     return i.f(x, ...)
//   }
//
// TODO(adonovan): opt: currently the stub is created even when used
// in call position: I.f(i, 0).  Clearly this is suboptimal.
//
// TODO(adonovan): memoize creation of these functions in the Program.
//
func makeImethodThunk(prog *Program, typ types.Type, id Id) *Function {
	if prog.mode&LogSource != 0 {
		defer logStack("makeImethodThunk %s.%s", typ, id)()
	}
	itf := typ.Underlying().(*types.Interface)
	index, meth := methodIndex(itf, id)
	sig := *meth.Type().(*types.Signature) // copy; shared Values
	fn := &Function{
		Name_:     meth.Name(),
		Signature: &sig,
		Prog:      prog,
	}
	fn.startBody()
	fn.addParam("recv", typ)
	createParams(fn)
	var c Call
	c.Call.Method = index
	c.Call.Recv = fn.Params[0]
	for _, arg := range fn.Params[1:] {
		c.Call.Args = append(c.Call.Args, arg)
	}
	emitTailCall(fn, &c)
	fn.finishBody()
	return fn
}

func (c *compiler) makeInterface(v *LLVMValue, iface types.Type) *LLVMValue {
	llv := v.LLVMValue()
	lltyp := llv.Type()
	i8ptr := llvm.PointerType(llvm.Int8Type(), 0)
	if lltyp.TypeKind() == llvm.PointerTypeKind {
		llv = c.builder.CreateBitCast(llv, i8ptr, "")
	} else {
		// If the value fits exactly in a pointer, then we can just
		// bitcast it. Otherwise we need to malloc.
		if c.target.TypeStoreSize(lltyp) <= uint64(c.target.PointerSize()) {
			bits := c.target.TypeSizeInBits(lltyp)
			if bits > 0 {
				llv = coerce(c.builder, llv, llvm.IntType(int(bits)))
				llv = c.builder.CreateIntToPtr(llv, i8ptr, "")
			} else {
				llv = llvm.ConstNull(i8ptr)
			}
		} else {
			ptr := c.createTypeMalloc(lltyp)
			c.builder.CreateStore(llv, ptr)
			llv = c.builder.CreateBitCast(ptr, i8ptr, "")
		}
	}
	value := llvm.Undef(c.types.ToLLVM(iface))
	rtype := c.types.ToRuntime(v.Type())
	rtype = c.builder.CreateBitCast(rtype, llvm.PointerType(llvm.Int8Type(), 0), "")
	value = c.builder.CreateInsertValue(value, rtype, 0, "")
	value = c.builder.CreateInsertValue(value, llv, 1, "")
	if iface.Underlying().(*types.Interface).NumMethods() > 0 {
		result := c.NewValue(value, types.NewInterface(nil, nil))
		result, _ = result.convertE2I(iface)
		return result
	}
	return c.NewValue(value, iface)
}

func (am *algorithmMap) eqalg(t types.Type) llvm.Value {
	t = t.Underlying()
	if st, ok := t.(*types.Struct); ok && st.NumFields() == 1 {
		t = st.Field(0).Type().Underlying()
	}
	switch t := t.(type) {
	case *types.Basic:
		switch t.Kind() {
		case types.String:
			return am.runtime.streqalg.LLVMValue()
		case types.Float32:
			return am.runtime.f32eqalg.LLVMValue()
		case types.Float64:
			return am.runtime.f64eqalg.LLVMValue()
		case types.Complex64:
			return am.runtime.c64eqalg.LLVMValue()
		case types.Complex128:
			return am.runtime.c128eqalg.LLVMValue()
		}
	case *types.Struct:
		// TODO
	}
	// TODO(axw) size-specific memequal cases
	return am.runtime.memequal.LLVMValue()
}

// makeMapLiteral makes a map with the specified keys and values.
func (c *compiler) makeMapLiteral(typ types.Type, keys, values []Value) *LLVMValue {
	var count, keysptr, valuesptr llvm.Value
	dyntyp := c.types.ToRuntime(typ)
	dyntyp = c.builder.CreatePtrToInt(dyntyp, c.target.IntPtrType(), "")
	if len(keys) == 0 {
		count = llvm.ConstNull(c.types.inttype)
		keysptr = llvm.ConstNull(c.target.IntPtrType())
		valuesptr = keysptr
	} else {
		maptyp := typ.Underlying().(*types.Map)
		keytyp := maptyp.Key()
		valtyp := maptyp.Elem()
		count = llvm.ConstInt(c.types.inttype, uint64(len(keys)), false)
		keysptr = c.builder.CreateArrayAlloca(c.types.ToLLVM(keytyp), count, "")
		valuesptr = c.builder.CreateArrayAlloca(c.types.ToLLVM(valtyp), count, "")
		for i := range keys {
			gepindices := []llvm.Value{llvm.ConstInt(c.types.inttype, uint64(i), false)}
			key := keys[i].Convert(keytyp).LLVMValue()
			ptr := c.builder.CreateGEP(keysptr, gepindices, "")
			c.builder.CreateStore(key, ptr)
			value := values[i].Convert(valtyp).LLVMValue()
			ptr = c.builder.CreateGEP(valuesptr, gepindices, "")
			c.builder.CreateStore(value, ptr)
		}
		keysptr = c.builder.CreatePtrToInt(keysptr, c.target.IntPtrType(), "")
		valuesptr = c.builder.CreatePtrToInt(valuesptr, c.target.IntPtrType(), "")
	}
	f := c.NamedFunction("runtime.makemap", "func(t uintptr, n int, keys, values uintptr) uintptr")
	mapval := c.builder.CreateCall(f, []llvm.Value{dyntyp, count, keysptr, valuesptr}, "")
	return c.NewValue(mapval, typ)
}

func (visit *visitor) methodSet(typ types.Type) {
	mset := typ.MethodSet()
	for i, n := 0, mset.Len(); i < n; i++ {
		// Side-effect: creates all wrapper methods.
		visit.function(visit.prog.Method(mset.At(i)))
	}
}

// emitConv emits to f code to convert Value val to exactly type typ,
// and returns the converted value.  Implicit conversions are required
// by language assignability rules in assignments, parameter passing,
// etc.
//
func emitConv(f *Function, val Value, typ types.Type) Value {
	t_src := val.Type()

	// Identical types?  Conversion is a no-op.
	if types.IsIdentical(t_src, typ) {
		return val
	}

	ut_dst := typ.Underlying()
	ut_src := t_src.Underlying()

	// Just a change of type, but not value or representation?
	if isValuePreserving(ut_src, ut_dst) {
		c := &ChangeType{X: val}
		c.setType(typ)
		return f.emit(c)
	}

	// Conversion to, or construction of a value of, an interface type?
	if _, ok := ut_dst.(*types.Interface); ok {

		// Assignment from one interface type to another?
		if _, ok := ut_src.(*types.Interface); ok {
			return emitTypeAssert(f, val, typ)
		}

		// Untyped nil literal?  Return interface-typed nil literal.
		if ut_src == tUntypedNil {
			return nilLiteral(typ)
		}

		// Convert (non-nil) "untyped" literals to their default type.
		// TODO(gri): expose types.isUntyped().
		if t, ok := ut_src.(*types.Basic); ok && t.Info()&types.IsUntyped != 0 {
			val = emitConv(f, val, DefaultType(ut_src))
		}

		mi := &MakeInterface{
			X:       val,
			Methods: f.Prog.MethodSet(t_src),
		}
		mi.setType(typ)
		return f.emit(mi)
	}

	// Conversion of a literal to a non-interface type results in
	// a new literal of the destination type and (initially) the
	// same abstract value.  We don't compute the representation
	// change yet; this defers the point at which the number of
	// possible representations explodes.
	if l, ok := val.(*Literal); ok {
		return newLiteral(l.Value, typ)
	}

	// A representation-changing conversion.
	c := &Convert{X: val}
	c.setType(typ)
	return f.emit(c)
}

func (x array) hash(t types.Type) int {
	h := 0
	tElt := t.Underlying().(*types.Array).Elem()
	for _, xi := range x {
		h += hash(tElt, xi)
	}
	return h
}

// promoteMethod promotes a named type's method to another type
// which has embedded the named type.
func (c *compiler) promoteMethod(m *types.Func, recv types.Type, indices []int) types.Object {
	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)

		realfn := c.Resolve(c.objectdata[m].Ident).LLVMValue()
		realfn = c.builder.CreateExtractValue(realfn, 0, "")

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

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

func (c *PkgContext) typeCheck(of string, to types.Type) string {
	if in, isInterface := to.Underlying().(*types.Interface); isInterface {
		if in.MethodSet().Len() == 0 {
			return "true"
		}
		return fmt.Sprintf("%s.Go$implementedBy.indexOf(%s) !== -1", c.typeName(to), of)
	}
	return of + " === " + c.typeName(to)
}

func (c *funcContext) typeCheck(of string, to types.Type) string {
	if in, isInterface := to.Underlying().(*types.Interface); isInterface {
		if in.Empty() {
			return "true"
		}
		return fmt.Sprintf("%s.implementedBy.indexOf(%s) !== -1", c.typeName(to), of)
	}
	return of + " === " + c.typeName(to)
}

// hasMethod reports whether the type contains a method with the given name.
// It is part of the workaround for Formatters and should be deleted when
// that workaround is no longer necessary. TODO: delete when fixed.
func hasMethod(typ types.Type, name string) bool {
	set := typ.MethodSet()
	for i := 0; i < set.Len(); i++ {
		if set.At(i).Obj().Name() == name {
			return true
		}
	}
	return false
}

// underlying returns the underlying type of typ.  Copied from go/types.
func underlyingType(typ types.Type) types.Type {
	if typ, ok := typ.(*types.Named); ok {
		return typ.Underlying() // underlying types are never NamedTypes
	}
	if typ == nil {
		panic("underlying(nil)")
	}
	return typ
}

// lookupMethod returns the method set for type typ, which may be one
// of the interpreter's fake types.
func lookupMethod(i *interpreter, typ types.Type, meth *types.Func) *ssa.Function {
	switch typ {
	case rtypeType:
		return i.rtypeMethods[meth.Id()]
	case errorType:
		return i.errorMethods[meth.Id()]
	}
	return i.prog.Method(typ.MethodSet().Lookup(meth.Pkg(), meth.Name()))
}

func (x array) eq(t types.Type, _y interface{}) bool {
	y := _y.(array)
	tElt := t.Underlying().(*types.Array).Elem()
	for i, xi := range x {
		if !equals(tElt, xi, y[i]) {
			return false
		}
	}
	return true
}

func (tm *llvmTypeMap) Alignof(typ types.Type) int64 {
	switch typ := typ.Underlying().(type) {
	case *types.Array:
		return tm.Alignof(typ.Elem())
	case *types.Basic:
		switch typ.Kind() {
		case types.Int, types.Uint, types.Int64, types.Uint64,
			types.Float64, types.Complex64, types.Complex128:
			return int64(tm.target.TypeAllocSize(tm.inttype))
		case types.Uintptr, types.UnsafePointer, types.String:
			return int64(tm.target.PointerSize())
		}
		return tm.StdSizes.Alignof(typ)
	case *types.Struct:
		max := int64(1)
		for i := 0; i < typ.NumFields(); i++ {
			f := typ.Field(i)
			a := tm.Alignof(f.Type())
			if a > max {
				max = a
			}
		}
		return max
	}
	return int64(tm.target.PointerSize())
}