func (m *TypeMap) descriptorInterface(t *types.Interface, name string) TypeDebugDescriptor {
	ifaceStruct := types.NewStruct([]*types.Var{
		types.NewVar(0, nil, "type", types.NewPointer(types.Typ[types.Uint8])),
		types.NewVar(0, nil, "data", types.NewPointer(types.Typ[types.Uint8])),
	}, nil)
	return m.typeDebugDescriptor(ifaceStruct, name)
}

func WriteInterfaces(dependencies []*types.Package, w io.Writer, merge bool) {
	allTypeNames := []*types.TypeName{types.New("error").(*types.Named).Obj()}
	for _, dep := range dependencies {
		scope := dep.Scope()
		for _, name := range scope.Names() {
			if typeName, isTypeName := scope.Lookup(name).(*types.TypeName); isTypeName {
				allTypeNames = append(allTypeNames, typeName)
			}
		}
	}
	for _, t := range allTypeNames {
		if in, isInterface := t.Type().Underlying().(*types.Interface); isInterface {
			if in.MethodSet().Len() == 0 {
				continue
			}
			implementedBy := make(map[string]bool, 0)
			for _, other := range allTypeNames {
				otherType := other.Type()
				switch otherType.Underlying().(type) {
				case *types.Interface:
					// skip
				case *types.Struct:
					if types.IsAssignableTo(otherType, in) {
						implementedBy[fmt.Sprintf("Go$packages[\"%s\"].%s.Go$NonPointer", other.Pkg().Path(), other.Name())] = true
					}
					if types.IsAssignableTo(types.NewPointer(otherType), in) {
						implementedBy[fmt.Sprintf("Go$packages[\"%s\"].%s", other.Pkg().Path(), other.Name())] = true
					}
				default:
					if types.IsAssignableTo(otherType, in) {
						implementedBy[fmt.Sprintf("Go$packages[\"%s\"].%s", other.Pkg().Path(), other.Name())] = true
					}
					if types.IsAssignableTo(types.NewPointer(otherType), in) {
						implementedBy[fmt.Sprintf("Go$packages[\"%s\"].%s.Go$Pointer", other.Pkg().Path(), other.Name())] = true
					}
				}
			}
			list := make([]string, 0, len(implementedBy))
			for ref := range implementedBy {
				list = append(list, ref)
			}
			sort.Strings(list)
			var target string
			switch t.Name() {
			case "error":
				target = "Go$error"
			default:
				target = fmt.Sprintf("Go$packages[\"%s\"].%s", t.Pkg().Path(), t.Name())
			}
			if merge {
				for _, entry := range list {
					fmt.Fprintf(w, "if (%s.Go$implementedBy.indexOf(%s) === -1) { %s.Go$implementedBy.push(%s); }\n", target, entry, target, entry)
				}
				continue
			}
			fmt.Fprintf(w, "%s.Go$implementedBy = [%s];\n", target, strings.Join(list, ", "))
		}
	}
}

// testMainSlice emits to fn code to construct a slice of type slice
// (one of []testing.Internal{Test,Benchmark,Example}) for all
// functions in this package whose name starts with prefix (one of
// "Test", "Benchmark" or "Example") and whose type is appropriate.
// It returns the slice value.
//
func testMainSlice(fn *Function, prefix string, slice types.Type) Value {
	tElem := slice.(*types.Slice).Elem()
	tFunc := tElem.Underlying().(*types.Struct).Field(1).Type()

	var testfuncs []*Function
	for name, mem := range fn.Pkg.Members {
		if fn, ok := mem.(*Function); ok && isTest(name, prefix) && types.IsIdentical(fn.Signature, tFunc) {
			testfuncs = append(testfuncs, fn)
		}
	}
	if testfuncs == nil {
		return nilConst(slice)
	}

	tString := types.Typ[types.String]
	tPtrString := types.NewPointer(tString)
	tPtrElem := types.NewPointer(tElem)
	tPtrFunc := types.NewPointer(tFunc)

	// Emit: array = new [n]testing.InternalTest
	tArray := types.NewArray(tElem, int64(len(testfuncs)))
	array := emitNew(fn, tArray, token.NoPos)
	array.Comment = "test main"
	for i, testfunc := range testfuncs {
		// Emit: pitem = &array[i]
		ia := &IndexAddr{X: array, Index: intConst(int64(i))}
		ia.setType(tPtrElem)
		pitem := fn.emit(ia)

		// Emit: pname = &pitem.Name
		fa := &FieldAddr{X: pitem, Field: 0} // .Name
		fa.setType(tPtrString)
		pname := fn.emit(fa)

		// Emit: *pname = "testfunc"
		emitStore(fn, pname, NewConst(exact.MakeString(testfunc.Name()), tString))

		// Emit: pfunc = &pitem.F
		fa = &FieldAddr{X: pitem, Field: 1} // .F
		fa.setType(tPtrFunc)
		pfunc := fn.emit(fa)

		// Emit: *pfunc = testfunc
		emitStore(fn, pfunc, testfunc)
	}

	// Emit: slice array[:]
	sl := &Slice{X: array}
	sl.setType(slice)
	return fn.emit(sl)
}

func (c *compiler) VisitIndexExpr(expr *ast.IndexExpr) Value {
	value := c.VisitExpr(expr.X)
	index := c.VisitExpr(expr.Index)

	typ := value.Type().Underlying()
	if isString(typ) {
		ptr := c.builder.CreateExtractValue(value.LLVMValue(), 0, "")
		gepindices := []llvm.Value{index.LLVMValue()}
		ptr = c.builder.CreateGEP(ptr, gepindices, "")
		byteType := types.Typ[types.Byte]
		result := c.NewValue(ptr, types.NewPointer(byteType))
		return result.makePointee()
	}

	// We can index a pointer to an array.
	if _, ok := typ.(*types.Pointer); ok {
		value = value.(*LLVMValue).makePointee()
		typ = value.Type().Underlying()
	}

	switch typ := typ.(type) {
	case *types.Array:
		index := index.Convert(types.Typ[types.Int]).LLVMValue()
		var ptr llvm.Value
		value := value.(*LLVMValue)
		if value.pointer != nil {
			ptr = value.pointer.LLVMValue()
		} else {
			init := value.LLVMValue()
			ptr = c.builder.CreateAlloca(init.Type(), "")
			c.builder.CreateStore(init, ptr)
		}
		zero := llvm.ConstNull(llvm.Int32Type())
		element := c.builder.CreateGEP(ptr, []llvm.Value{zero, index}, "")
		result := c.NewValue(element, types.NewPointer(typ.Elem()))
		return result.makePointee()

	case *types.Slice:
		index := index.Convert(types.Typ[types.Int]).LLVMValue()
		ptr := c.builder.CreateExtractValue(value.LLVMValue(), 0, "")
		element := c.builder.CreateGEP(ptr, []llvm.Value{index}, "")
		result := c.NewValue(element, types.NewPointer(typ.Elem()))
		return result.makePointee()

	case *types.Map:
		value, _ = c.mapLookup(value.(*LLVMValue), index, false)
		return value
	}
	panic(fmt.Sprintf("unreachable (%s)", typ))
}

func (c *funcContext) initType(o types.Object) {
	if _, isInterface := o.Type().Underlying().(*types.Interface); !isInterface {
		writeMethodSet := func(t types.Type) {
			methodSet := types.NewMethodSet(t)
			if methodSet.Len() == 0 {
				return
			}
			methods := make([]string, methodSet.Len())
			for i := range methods {
				method := methodSet.At(i)
				pkgPath := ""
				if !method.Obj().Exported() {
					pkgPath = method.Obj().Pkg().Path()
				}
				t := method.Type().(*types.Signature)
				embeddedIndex := -1
				if len(method.Index()) > 1 {
					embeddedIndex = method.Index()[0]
				}
				methods[i] = fmt.Sprintf(`["%s", "%s", %s, %s, %t, %d]`, method.Obj().Name(), pkgPath, c.typeArray(t.Params()), c.typeArray(t.Results()), t.Variadic(), embeddedIndex)
			}
			c.Printf("%s.methods = [%s];", c.typeName(t), strings.Join(methods, ", "))
		}
		writeMethodSet(o.Type())
		writeMethodSet(types.NewPointer(o.Type()))
	}
	switch t := o.Type().Underlying().(type) {
	case *types.Array, *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Slice, *types.Signature, *types.Struct:
		c.Printf("%s.init(%s);", c.objectName(o), c.initArgs(t))
	}
}

// emitNew emits to f a new (heap Alloc) instruction allocating an
// object of type typ.  pos is the optional source location.
//
func emitNew(f *Function, typ types.Type, pos token.Pos) *Alloc {
	v := &Alloc{Heap: true}
	v.setType(types.NewPointer(typ))
	v.setPos(pos)
	f.emit(v)
	return v
}

// emitImplicitSelections emits to f code to apply the sequence of
// implicit field selections specified by indices to base value v, and
// returns the selected value.
//
// If v is the address of a struct, the result will be the address of
// a field; if it is the value of a struct, the result will be the
// value of a field.
//
func emitImplicitSelections(f *Function, v Value, indices []int) Value {
	for _, index := range indices {
		fld := deref(v.Type()).Underlying().(*types.Struct).Field(index)

		if isPointer(v.Type()) {
			instr := &FieldAddr{
				X:     v,
				Field: index,
			}
			instr.setType(types.NewPointer(fld.Type()))
			v = f.emit(instr)
			// Load the field's value iff indirectly embedded.
			if isPointer(fld.Type()) {
				v = emitLoad(f, v)
			}
		} else {
			instr := &Field{
				X:     v,
				Field: index,
			}
			instr.setType(fld.Type())
			v = f.emit(instr)
		}
	}
	return v
}

func checkVarValue(t *testing.T, prog *ssa.Program, pkg *ssa.Package, ref []ast.Node, obj *types.Var, expKind string, wantAddr bool) {
	// The prefix of all assertions messages.
	prefix := fmt.Sprintf("VarValue(%s @ L%d)",
		obj, prog.Fset.Position(ref[0].Pos()).Line)

	v := prog.VarValue(obj, pkg, ref)

	// Kind is the concrete type of the ssa Value.
	gotKind := "nil"
	if v != nil {
		gotKind = fmt.Sprintf("%T", v)[len("*ssa."):]
	}

	// fmt.Printf("%s = %v (kind %q; expect %q) addr=%t\n", prefix, v, gotKind, expKind, wantAddr) // debugging

	// Check the kinds match.
	// "nil" indicates expected failure (e.g. optimized away).
	if expKind != gotKind {
		t.Errorf("%s concrete type == %s, want %s", prefix, gotKind, expKind)
	}

	// Check the types match.
	// If wantAddr, the expected type is the object's address.
	if v != nil {
		expType := obj.Type()
		if wantAddr {
			expType = types.NewPointer(expType)
		}
		if !types.IsIdentical(v.Type(), expType) {
			t.Errorf("%s.Type() == %s, want %s", prefix, v.Type(), expType)
		}
	}
}

// emitFieldSelection emits to f code to select the index'th field of v.
//
// If wantAddr, the input must be a pointer-to-struct and the result
// will be the field's address; otherwise the result will be the
// field's value.
//
func emitFieldSelection(f *Function, v Value, index int, wantAddr bool, pos token.Pos) Value {
	fld := deref(v.Type()).Underlying().(*types.Struct).Field(index)
	if isPointer(v.Type()) {
		instr := &FieldAddr{
			X:     v,
			Field: index,
		}
		instr.setPos(pos)
		instr.setType(types.NewPointer(fld.Type()))
		v = f.emit(instr)
		// Load the field's value iff we don't want its address.
		if !wantAddr {
			v = emitLoad(f, v)
		}
	} else {
		instr := &Field{
			X:     v,
			Field: index,
		}
		instr.setPos(pos)
		instr.setType(fld.Type())
		v = f.emit(instr)
	}
	return v
}

// 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
}

func (c *compiler) exportRuntimeTypes(exportedTypes []types.Type, builtin bool) {
	if builtin {
		kinds := [...]types.BasicKind{
			types.Uint,
			types.Uint8,
			types.Uint16,
			types.Uint32,
			types.Uint64,
			types.Int,
			types.Int8,
			types.Int16,
			types.Int32,
			types.Int64,
			types.Float32,
			types.Float64,
			types.Complex64,
			types.Complex128,
			types.Bool,
			types.Uintptr,
			types.UnsafePointer,
			types.String,
		}
		for _, kind := range kinds {
			exportedTypes = append(exportedTypes, types.Typ[kind])
		}
		error_ := types.Universe.Lookup("error").Type()
		exportedTypes = append(exportedTypes, error_)
	}
	for _, typ := range exportedTypes {
		c.types.ToRuntime(types.NewPointer(typ))
	}
}

// mapLookup searches a map for a specified key, returning a pointer to the
// memory location for the value. If insert is given as true, and the key
// does not exist in the map, it will be added with an uninitialised value.
func (c *compiler) mapLookup(m *LLVMValue, key Value, insert bool) (elem *LLVMValue, notnull *LLVMValue) {
	mapType := m.Type().Underlying().(*types.Map)
	maplookup := c.NamedFunction("runtime.maplookup", "func f(t, m, k uintptr, insert bool) uintptr")
	ptrType := c.target.IntPtrType()
	args := make([]llvm.Value, 4)
	args[0] = llvm.ConstPtrToInt(c.types.ToRuntime(mapType), ptrType)
	args[1] = c.builder.CreatePtrToInt(m.LLVMValue(), ptrType, "")
	if insert {
		args[3] = llvm.ConstAllOnes(llvm.Int1Type())
	} else {
		args[3] = llvm.ConstNull(llvm.Int1Type())
	}

	if lv, islv := key.(*LLVMValue); islv && lv.pointer != nil {
		args[2] = c.builder.CreatePtrToInt(lv.pointer.LLVMValue(), ptrType, "")
	}
	if args[2].IsNil() {
		stackval := c.builder.CreateAlloca(c.types.ToLLVM(key.Type()), "")
		c.builder.CreateStore(key.LLVMValue(), stackval)
		args[2] = c.builder.CreatePtrToInt(stackval, ptrType, "")
	}

	eltPtrType := types.NewPointer(mapType.Elem())
	llvmtyp := c.types.ToLLVM(eltPtrType)
	zeroglobal := llvm.AddGlobal(c.module.Module, llvmtyp.ElementType(), "")
	zeroglobal.SetInitializer(llvm.ConstNull(llvmtyp.ElementType()))
	result := c.builder.CreateCall(maplookup, args, "")
	result = c.builder.CreateIntToPtr(result, llvmtyp, "")
	notnull_ := c.builder.CreateIsNotNull(result, "")
	result = c.builder.CreateSelect(notnull_, result, zeroglobal, "")
	value := c.NewValue(result, eltPtrType)
	return value.makePointee(), c.NewValue(notnull_, types.Typ[types.Bool])
}

func (c *compiler) exportRuntimeTypes() {
	if c.pkg.Path() == "runtime" {
		kinds := [...]types.BasicKind{
			types.Uint,
			types.Uint8,
			types.Uint16,
			types.Uint32,
			types.Uint64,
			types.Int,
			types.Int8,
			types.Int16,
			types.Int32,
			types.Int64,
			types.Float32,
			types.Float64,
			types.Complex64,
			types.Complex128,
			types.Bool,
			types.Uintptr,
			types.UnsafePointer,
			types.String,
		}
		for _, kind := range kinds {
			c.exportedtypes = append(c.exportedtypes, types.Typ[kind])
		}
		error_ := types.Universe.Lookup("error").Type()
		c.exportedtypes = append(c.exportedtypes, error_)
	}
	for _, typ := range c.exportedtypes {
		c.types.ToRuntime(typ)
		c.types.ToRuntime(types.NewPointer(typ))
	}
}

// addLocal creates an anonymous local variable of type typ, adds it
// to function f and returns it.  pos is the optional source location.
//
func (f *Function) addLocal(typ types.Type, pos token.Pos) *Alloc {
	v := &Alloc{}
	v.setType(types.NewPointer(typ))
	v.setPos(pos)
	f.Locals = append(f.Locals, v)
	f.emit(v)
	return v
}

// PointerType = "*" ("any" | Type) .
func (p *parser) parsePointerType(pkg *types.Package) types.Type {
	p.expect('*')
	if p.tok == scanner.Ident {
		p.expectKeyword("any")
		return types.Typ[types.UnsafePointer]
	}
	return types.NewPointer(p.parseType(pkg))
}

func (m *TypeMap) descriptorSlice(t *types.Slice, name string) TypeDebugDescriptor {
	sliceStruct := types.NewStruct([]*types.Var{
		types.NewVar(0, nil, "ptr", types.NewPointer(t.Elem())),
		types.NewVar(0, nil, "len", types.Typ[types.Int]),
		types.NewVar(0, nil, "cap", types.Typ[types.Int]),
	}, nil)
	return m.typeDebugDescriptor(sliceStruct, name)
}

// memberFromObject populates package pkg with a member for the
// typechecker object obj.
//
// For objects from Go source code, syntax is the associated syntax
// tree (for funcs and vars only); it will be used during the build
// phase.
//
func memberFromObject(pkg *Package, obj types.Object, syntax ast.Node) {
	name := obj.Name()
	switch obj := obj.(type) {
	case *types.TypeName:
		pkg.Members[name] = &Type{object: obj}

	case *types.Const:
		c := &NamedConst{
			object: obj,
			Value:  NewConst(obj.Val(), obj.Type()),
		}
		pkg.values[obj] = c.Value
		pkg.Members[name] = c

	case *types.Var:
		spec, _ := syntax.(*ast.ValueSpec)
		g := &Global{
			Pkg:    pkg,
			name:   name,
			object: obj,
			typ:    types.NewPointer(obj.Type()), // address
			pos:    obj.Pos(),
			spec:   spec,
		}
		pkg.values[obj] = g
		pkg.Members[name] = g

	case *types.Func:
		var fs *funcSyntax
		synthetic := "loaded from gc object file"
		if decl, ok := syntax.(*ast.FuncDecl); ok {
			synthetic = ""
			fs = &funcSyntax{
				functype:  decl.Type,
				recvField: decl.Recv,
				body:      decl.Body,
			}
		}
		fn := &Function{
			name:      name,
			object:    obj,
			Signature: obj.Type().(*types.Signature),
			Synthetic: synthetic,
			pos:       obj.Pos(), // (iff syntax)
			Pkg:       pkg,
			Prog:      pkg.Prog,
			syntax:    fs,
		}
		pkg.values[obj] = fn
		if fn.Signature.Recv() == nil {
			pkg.Members[name] = fn // package-level function
		}

	default: // (incl. *types.Package)
		panic("unexpected Object type: " + obj.String())
	}
}

// addSpilledParam declares a parameter that is pre-spilled to the
// stack; the function body will load/store the spilled location.
// Subsequent lifting will eliminate spills where possible.
//
func (f *Function) addSpilledParam(obj types.Object) {
	param := f.addParamObj(obj)
	spill := &Alloc{Comment: obj.Name()}
	spill.setType(types.NewPointer(obj.Type()))
	spill.setPos(obj.Pos())
	f.objects[obj] = spill
	f.Locals = append(f.Locals, spill)
	f.emit(spill)
	f.emit(&Store{Addr: spill, Val: param})
}

// testMainSlice emits to fn code to construct a slice of type slice
// (one of []testing.Internal{Test,Benchmark,Example}) for all
// functions in testfuncs.  It returns the slice value.
//
func testMainSlice(fn *Function, testfuncs []*Function, slice types.Type) Value {
	if testfuncs == nil {
		return nilConst(slice)
	}

	tElem := slice.(*types.Slice).Elem()
	tPtrString := types.NewPointer(tString)
	tPtrElem := types.NewPointer(tElem)
	tPtrFunc := types.NewPointer(funcField(slice))

	// Emit: array = new [n]testing.InternalTest
	tArray := types.NewArray(tElem, int64(len(testfuncs)))
	array := emitNew(fn, tArray, token.NoPos)
	array.Comment = "test main"
	for i, testfunc := range testfuncs {
		// Emit: pitem = &array[i]
		ia := &IndexAddr{X: array, Index: intConst(int64(i))}
		ia.setType(tPtrElem)
		pitem := fn.emit(ia)

		// Emit: pname = &pitem.Name
		fa := &FieldAddr{X: pitem, Field: 0} // .Name
		fa.setType(tPtrString)
		pname := fn.emit(fa)

		// Emit: *pname = "testfunc"
		emitStore(fn, pname, stringConst(testfunc.Name()))

		// Emit: pfunc = &pitem.F
		fa = &FieldAddr{X: pitem, Field: 1} // .F
		fa.setType(tPtrFunc)
		pfunc := fn.emit(fa)

		// Emit: *pfunc = testfunc
		emitStore(fn, pfunc, testfunc)
	}

	// Emit: slice array[:]
	sl := &Slice{X: array}
	sl.setType(slice)
	return fn.emit(sl)
}

func (c *compiler) Resolve(ident *ast.Ident) Value {
	obj := c.typeinfo.Objects[ident]
	data := c.objectdata[obj]
	if data.Value != nil {
		return data.Value
	}

	var value *LLVMValue
	switch obj := obj.(type) {
	case *types.Func:
		value = c.makeFunc(ident, obj.Type().(*types.Signature))
	case *synthFunc:
		value = c.makeFunc(ident, obj.Type().(*types.Signature))

	case *types.Var:
		if data.Ident.Obj != nil {
			switch decl := data.Ident.Obj.Decl.(type) {
			case *ast.ValueSpec:
				c.VisitValueSpec(decl)
			case *ast.Field:
				// No-op. Fields will be yielded for function
				// arg/recv/ret. We update the .Data field of the
				// object when we enter the function definition.
				if data.Value == nil {
					panic("expected object value")
				}
			}
		}

		// If it's an external variable, we'll need to create a global
		// value reference here. It may be possible for multiple objects
		// to refer to the same variable.
		value = data.Value
		if value == nil {
			module := c.module.Module
			t := obj.Type()
			name := obj.Pkg().Path() + "." + obj.Name()
			g := module.NamedGlobal(name)
			if g.IsNil() {
				g = llvm.AddGlobal(module, c.types.ToLLVM(t), name)
			}
			value = c.NewValue(g, types.NewPointer(t)).makePointee()
		}

	case *types.Const:
		value = c.NewConstValue(obj.Val(), obj.Type())

	default:
		panic(fmt.Sprintf("unreachable (%T)", obj))
	}

	data.Value = value
	return value
}