diff options
| -rw-r--r-- | interp/interp_test.go | 1 | ||||
| -rw-r--r-- | interp/interpreter.go | 68 | ||||
| -rw-r--r-- | interp/memory.go | 282 | ||||
| -rw-r--r-- | interp/testdata/map.ll | 74 | ||||
| -rw-r--r-- | interp/testdata/map.out.ll | 20 | ||||
| -rw-r--r-- | testdata/map.go | 10 | ||||
| -rw-r--r-- | testdata/map.txt | 46 |
7 files changed, 32 insertions, 469 deletions
diff --git a/interp/interp_test.go b/interp/interp_test.go index 6fabdd519..50af8af60 100644 --- a/interp/interp_test.go +++ b/interp/interp_test.go @@ -16,7 +16,6 @@ func TestInterp(t *testing.T) { "phi", "slice-copy", "consteval", - "map", "interface", } { name := name // make tc local to this closure diff --git a/interp/interpreter.go b/interp/interpreter.go index 73707811c..71be6957c 100644 --- a/interp/interpreter.go +++ b/interp/interpreter.go @@ -456,74 +456,6 @@ func (r *runner) run(fn *function, params []value, parentMem *memoryView, indent return nil, mem, r.errorAt(inst, errors.New("could not find method: "+signature.Name())) } locals[inst.localIndex] = r.getValue(method) - case callFn.name == "runtime.hashmapMake": - // Create a new map. - hashmapPointerType := inst.llvmInst.Type() - keySize := uint32(operands[1].Uint()) - valueSize := uint32(operands[2].Uint()) - m := newMapValue(r, hashmapPointerType, keySize, valueSize) - alloc := object{ - llvmType: hashmapPointerType, - globalName: r.pkgName + "$map", - buffer: m, - size: m.len(r), - } - index := len(r.objects) - r.objects = append(r.objects, alloc) - - // Create a pointer to this map. Maps are reference types, so - // are implemented as pointers. - ptr := newPointerValue(r, index, 0) - if r.debug { - fmt.Fprintln(os.Stderr, indent+"runtime.hashmapMake:", keySize, valueSize, "->", ptr) - } - locals[inst.localIndex] = ptr - case callFn.name == "runtime.hashmapBinarySet": - // Do a mapassign operation with a binary key (that is, without - // a string key). - if r.debug { - fmt.Fprintln(os.Stderr, indent+"runtime.hashmapBinarySet:", operands[1:]) - } - mapPtr, err := operands[1].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - m := mem.getWritable(mapPtr.index()).buffer.(*mapValue) - keyPtr, err := operands[2].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - valuePtr, err := operands[3].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - err = m.putBinary(&mem, keyPtr, valuePtr) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - case callFn.name == "runtime.hashmapStringSet": - // Do a mapassign operation with a string key. - if r.debug { - fmt.Fprintln(os.Stderr, indent+"runtime.hashmapBinarySet:", operands[1:]) - } - mapPtr, err := operands[1].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - m := mem.getWritable(mapPtr.index()).buffer.(*mapValue) - stringPtr, err := operands[2].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - stringLen := operands[3].Uint() - valuePtr, err := operands[4].asPointer(r) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } - err = m.putString(&mem, stringPtr, stringLen, valuePtr) - if err != nil { - return nil, mem, r.errorAt(inst, err) - } default: if len(callFn.blocks) == 0 { // Call to a function declaration without a definition diff --git a/interp/memory.go b/interp/memory.go index f55ac7e28..54bfcb623 100644 --- a/interp/memory.go +++ b/interp/memory.go @@ -640,288 +640,6 @@ func (v pointerValue) toLLVMValue(llvmType llvm.Type, mem *memoryView) (llvm.Val return gep, nil } -// mapValue implements a Go map which is created at compile time and stored as a -// global variable. -// The value itself is only used as part of an object (object.buffer). Maps are -// reference types aka pointers, so it can only be used as a pointerValue, not -// directly. -type mapValue struct { - r *runner - pkgName string - size uint32 // byte size of runtime.hashmap - hashmap llvm.Value - keyIsString bool - keys []interface{} // either rawValue (for binary key) or mapStringKey (for string key) - values []rawValue - keySize uint32 - valueSize uint32 -} - -type mapStringKey struct { - buf pointerValue - size uint64 - data []uint64 -} - -func newMapValue(r *runner, hashmapPointerType llvm.Type, keySize, valueSize uint32) *mapValue { - size := uint32(r.targetData.TypeAllocSize(hashmapPointerType.ElementType())) - return &mapValue{ - r: r, - pkgName: r.pkgName, - size: size, - keySize: keySize, - valueSize: valueSize, - } -} - -func (v *mapValue) len(r *runner) uint32 { - return v.size -} - -func (v *mapValue) clone() value { - // Return a copy of mapValue. - clone := *v - clone.keys = append([]interface{}{}, clone.keys...) - clone.values = append([]rawValue{}, clone.values...) - return &clone -} - -func (v *mapValue) asPointer(r *runner) (pointerValue, error) { - panic("interp: mapValue.asPointer") -} - -func (v *mapValue) asRawValue(r *runner) rawValue { - panic("interp: mapValue.asRawValue") -} - -func (v *mapValue) Uint() uint64 { - panic("interp: mapValue.Uint") -} - -func (v *mapValue) Int() int64 { - panic("interp: mapValue.Int") -} - -// Temporary struct to collect data before turning this into a hashmap bucket -// LLVM value. -type mapBucket struct { - m *mapValue - tophash [8]uint8 - keys []rawValue // can have up to 8 keys - values []rawValue // can have up to 8 values, len(keys) == len(values) -} - -// create returns a (pointer to a) buffer structurally equivalent to -// runtime.hashmapBucket. -func (b *mapBucket) create(ctx llvm.Context, nextBucket llvm.Value, mem *memoryView) llvm.Value { - // Create tophash array. - int8Type := ctx.Int8Type() - tophashValues := make([]llvm.Value, 8) - for i := range tophashValues { - tophashValues[i] = llvm.ConstInt(int8Type, uint64(b.tophash[i]), false) - } - tophash := llvm.ConstArray(int8Type, tophashValues) - - // Create next pointer (if not set). - if nextBucket.IsNil() { - nextBucket = llvm.ConstNull(llvm.PointerType(int8Type, 0)) - } - - // Create data for keys. - var keyValues []llvm.Value - for _, key := range b.keys { - keyValue, err := key.rawLLVMValue(mem) - if err != nil { - panic(err) - } - keyValues = append(keyValues, keyValue) - } - if len(b.keys) < 8 { - keyValues = append(keyValues, llvm.ConstNull(llvm.ArrayType(int8Type, int(b.m.keySize)*(8-len(b.keys))))) - } - keyValue := ctx.ConstStruct(keyValues, false) - if checks && uint32(b.m.r.targetData.TypeAllocSize(keyValue.Type())) != b.m.keySize*8 { - panic("key size invalid") - } - - // Create data for values. - var valueValues []llvm.Value - for _, value := range b.values { - v, err := value.rawLLVMValue(mem) - if err != nil { - panic(err) - } - valueValues = append(valueValues, v) - } - if len(b.values) < 8 { - valueValues = append(valueValues, llvm.ConstNull(llvm.ArrayType(int8Type, int(b.m.valueSize)*(8-len(b.values))))) - } - valueValue := ctx.ConstStruct(valueValues, false) - if checks && uint32(b.m.r.targetData.TypeAllocSize(valueValue.Type())) != b.m.valueSize*8 { - panic("value size invalid") - } - - // Create the bucket. - bucketInitializer := ctx.ConstStruct([]llvm.Value{ - tophash, - nextBucket, - keyValue, - valueValue, - }, false) - bucket := llvm.AddGlobal(b.m.r.mod, bucketInitializer.Type(), b.m.pkgName+"$mapbucket") - bucket.SetInitializer(bucketInitializer) - bucket.SetLinkage(llvm.InternalLinkage) - bucket.SetUnnamedAddr(true) - return bucket -} - -func (v *mapValue) toLLVMValue(hashmapType llvm.Type, mem *memoryView) (llvm.Value, error) { - if !v.hashmap.IsNil() { - return v.hashmap, nil - } - - // Create a slice of buckets with all the keys and values in the hashmap. - var buckets []*mapBucket - var bucket *mapBucket - for i, key := range v.keys { - var data []uint64 - var keyValue rawValue - switch key := key.(type) { - case mapStringKey: - data = key.data - keyValue = newRawValue(v.keySize) - // runtime._string is {ptr, length} - for i := uint32(0); i < v.keySize/2; i++ { - keyValue.buf[i] = key.buf.pointer - } - copy(keyValue.buf[v.keySize/2:], literalValue{key.size}.asRawValue(v.r).buf) - case rawValue: - if key.hasPointer() { - return llvm.Value{}, errors.New("interp: todo: map key with pointer") - } - data = key.buf - keyValue = key - default: - return llvm.Value{}, errors.New("interp: unknown map key type") - } - buf := make([]byte, len(data)) - for i, p := range data { - buf[i] = byte(p) - } - hash := v.hash(buf) - - if i%8 == 0 { - bucket = &mapBucket{m: v} - buckets = append(buckets, bucket) - } - bucket.tophash[i%8] = v.topHash(hash) - bucket.keys = append(bucket.keys, keyValue) - bucket.values = append(bucket.values, v.values[i]) - } - - // Convert these buckets into LLVM global variables. - ctx := v.r.mod.Context() - var nextBucket llvm.Value - for i := len(buckets) - 1; i >= 0; i-- { - bucket = buckets[i] - bucketValue := bucket.create(ctx, nextBucket, mem) - nextBucket = bucketValue - } - firstBucket := nextBucket - if firstBucket.IsNil() { - firstBucket = llvm.ConstNull(mem.r.i8ptrType) - } else { - firstBucket = llvm.ConstBitCast(firstBucket, mem.r.i8ptrType) - } - - // Create the hashmap itself, pointing to these buckets. - hashmapPointerType := llvm.PointerType(hashmapType, 0) - hashmap := llvm.ConstNamedStruct(hashmapType, []llvm.Value{ - llvm.ConstPointerNull(hashmapPointerType), // next - firstBucket, // buckets - llvm.ConstInt(hashmapType.StructElementTypes()[2], uint64(len(v.keys)), false), // count - llvm.ConstInt(ctx.Int8Type(), uint64(v.keySize), false), // keySize - llvm.ConstInt(ctx.Int8Type(), uint64(v.valueSize), false), // valueSize - llvm.ConstInt(ctx.Int8Type(), 0, false), // bucketBits - }) - - v.hashmap = hashmap - return v.hashmap, nil -} - -// putString does a map assign operation, assuming that the map is of type -// map[string]T. -func (v *mapValue) putString(mem *memoryView, stringBuf pointerValue, stringLen uint64, valuePtr pointerValue) error { - if !v.hashmap.IsNil() { - return errMapAlreadyCreated - } - - value := mem.load(valuePtr, v.valueSize) - stringValue := mem.load(stringBuf, uint32(stringLen)).asRawValue(v.r) - if stringValue.hasPointer() { - panic("interp: string contains pointer") - } - - // TODO: avoid duplicate keys - v.keys = append(v.keys, mapStringKey{stringBuf, stringLen, stringValue.buf}) - v.values = append(v.values, value.asRawValue(v.r)) - v.keyIsString = true - - return nil -} - -// putBinary does a map assign operation for binary data (e.g. [3]int etc). The -// key must not contain pointer values. -func (v *mapValue) putBinary(mem *memoryView, keyPtr, valuePtr pointerValue) error { - if !v.hashmap.IsNil() { - return errMapAlreadyCreated - } - - key := mem.load(keyPtr, v.keySize) - value := mem.load(valuePtr, v.valueSize) - - // Sanity checks. - if v.keySize != key.len(mem.r) || v.valueSize != value.len(mem.r) { - // This is a bug (not unhandled input), so panic. - panic("interp: key or value size mismatch") - } - if v.keyIsString { - panic("cannot put binary keys in string map") - } - - // TODO: avoid duplicate keys - v.keys = append(v.keys, key.asRawValue(v.r)) - v.values = append(v.values, value.asRawValue(v.r)) - - return nil -} - -// Get FNV-1a hash of this string. -// -// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash -func (v *mapValue) hash(data []byte) uint32 { - var result uint32 = 2166136261 // FNV offset basis - for _, c := range data { - result ^= uint32(c) - result *= 16777619 // FNV prime - } - return result -} - -// Get the topmost 8 bits of the hash, without using a special value (like 0). -func (v *mapValue) topHash(hash uint32) uint8 { - tophash := uint8(hash >> 24) - if tophash < 1 { - // 0 means empty slot, so make it bigger. - tophash++ - } - return tophash -} - -func (v *mapValue) String() string { - return "<map keySize=" + strconv.Itoa(int(v.keySize)) + " valueSize=" + strconv.Itoa(int(v.valueSize)) + ">" -} - // rawValue is a raw memory buffer that can store either pointers or regular // data. This is the fallback data for everything that isn't clearly a // literalValue or pointerValue. diff --git a/interp/testdata/map.ll b/interp/testdata/map.ll deleted file mode 100644 index 9afb53322..000000000 --- a/interp/testdata/map.ll +++ /dev/null @@ -1,74 +0,0 @@ -target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64" -target triple = "armv6m-none-eabi" - -%runtime._string = type { i8*, i32 } -%runtime.hashmap = type { %runtime.hashmap*, i8*, i32, i8, i8, i8 } - [email protected] = global %runtime.hashmap* null [email protected] = global %runtime.hashmap* null [email protected] = global %runtime.hashmap* null [email protected] = internal unnamed_addr constant [7 x i8] c"CONNECT" - -declare %runtime.hashmap* @runtime.hashmapMake(i8, i8, i32, i8* %context, i8* %parentHandle) -declare void @runtime.hashmapBinarySet(%runtime.hashmap*, i8*, i8*, i8* %context, i8* %parentHandle) -declare void @runtime.hashmapStringSet(%runtime.hashmap*, i8*, i32, i8*, i8* %context, i8* %parentHandle) -declare void @llvm.lifetime.end.p0i8(i64, i8*) -declare void @llvm.lifetime.start.p0i8(i64, i8*) - -define void @runtime.initAll() unnamed_addr { -entry: - call void @main.init(i8* undef, i8* null) - ret void -} - -define internal void @main.init(i8* %context, i8* %parentHandle) unnamed_addr { -entry: -; Test that hashmap optimizations generally work (even with lifetimes). - %hashmap.key = alloca i8 - %hashmap.value = alloca %runtime._string - %0 = call %runtime.hashmap* @runtime.hashmapMake(i8 1, i8 8, i32 1, i8* undef, i8* null) - %hashmap.value.bitcast = bitcast %runtime._string* %hashmap.value to i8* - call void @llvm.lifetime.start.p0i8(i64 8, i8* %hashmap.value.bitcast) - store %runtime._string { i8* getelementptr inbounds ([7 x i8], [7 x i8]* @main.init.string, i32 0, i32 0), i32 7 }, %runtime._string* %hashmap.value - call void @llvm.lifetime.start.p0i8(i64 1, i8* %hashmap.key) - store i8 1, i8* %hashmap.key - call void @runtime.hashmapBinarySet(%runtime.hashmap* %0, i8* %hashmap.key, i8* %hashmap.value.bitcast, i8* undef, i8* null) - call void @llvm.lifetime.end.p0i8(i64 1, i8* %hashmap.key) - call void @llvm.lifetime.end.p0i8(i64 8, i8* %hashmap.value.bitcast) - store %runtime.hashmap* %0, %runtime.hashmap** @main.m - - ; Other tests, that can be done in a separate function. - call void @main.testNonConstantBinarySet() - call void @main.testNonConstantStringSet() - ret void -} - -; Test that a map loaded from a global can still be used for mapassign -; operations (with binary keys). -define internal void @main.testNonConstantBinarySet() { - %hashmap.key = alloca i8 - %hashmap.value = alloca i8 - ; Create hashmap from global. - %map.new = call %runtime.hashmap* @runtime.hashmapMake(i8 1, i8 1, i32 1, i8* undef, i8* null) - store %runtime.hashmap* %map.new, %runtime.hashmap** @main.binaryMap - %map = load %runtime.hashmap*, %runtime.hashmap** @main.binaryMap - ; Do the binary set to the newly loaded map. - store i8 1, i8* %hashmap.key - store i8 2, i8* %hashmap.value - call void @runtime.hashmapBinarySet(%runtime.hashmap* %map, i8* %hashmap.key, i8* %hashmap.value, i8* undef, i8* null) - ret void -} - -; Test that a map loaded from a global can still be used for mapassign -; operations (with string keys). -define internal void @main.testNonConstantStringSet() { - %hashmap.value = alloca i8 - ; Create hashmap from global. - %map.new = call %runtime.hashmap* @runtime.hashmapMake(i8 8, i8 1, i32 1, i8* undef, i8* null) - store %runtime.hashmap* %map.new, %runtime.hashmap** @main.stringMap - %map = load %runtime.hashmap*, %runtime.hashmap** @main.stringMap - ; Do the string set to the newly loaded map. - store i8 2, i8* %hashmap.value - call void @runtime.hashmapStringSet(%runtime.hashmap* %map, i8* getelementptr inbounds ([7 x i8], [7 x i8]* @main.init.string, i32 0, i32 0), i32 7, i8* %hashmap.value, i8* undef, i8* null) - ret void -} diff --git a/interp/testdata/map.out.ll b/interp/testdata/map.out.ll deleted file mode 100644 index a8acc49f3..000000000 --- a/interp/testdata/map.out.ll +++ /dev/null @@ -1,20 +0,0 @@ -target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64" -target triple = "armv6m-none-eabi" - -%runtime.hashmap = type { %runtime.hashmap*, i8*, i32, i8, i8, i8 } - [email protected] = local_unnamed_addr global %runtime.hashmap* @"main$map" [email protected] = local_unnamed_addr global %runtime.hashmap* @"main$map.1" [email protected] = local_unnamed_addr global %runtime.hashmap* @"main$map.3" [email protected] = internal unnamed_addr constant [7 x i8] c"CONNECT" -@"main$map" = internal global %runtime.hashmap { %runtime.hashmap* null, i8* getelementptr inbounds ({ [8 x i8], i8*, { i8, [7 x i8] }, { { [7 x i8]*, [4 x i8] }, [56 x i8] } }, { [8 x i8], i8*, { i8, [7 x i8] }, { { [7 x i8]*, [4 x i8] }, [56 x i8] } }* @"main$mapbucket", i32 0, i32 0, i32 0), i32 1, i8 1, i8 8, i8 0 } -@"main$mapbucket" = internal unnamed_addr global { [8 x i8], i8*, { i8, [7 x i8] }, { { [7 x i8]*, [4 x i8] }, [56 x i8] } } { [8 x i8] c"\04\00\00\00\00\00\00\00", i8* null, { i8, [7 x i8] } { i8 1, [7 x i8] zeroinitializer }, { { [7 x i8]*, [4 x i8] }, [56 x i8] } { { [7 x i8]*, [4 x i8] } { [7 x i8]* @main.init.string, [4 x i8] c"\07\00\00\00" }, [56 x i8] zeroinitializer } } -@"main$map.1" = internal global %runtime.hashmap { %runtime.hashmap* null, i8* getelementptr inbounds ({ [8 x i8], i8*, { i8, [7 x i8] }, { i8, [7 x i8] } }, { [8 x i8], i8*, { i8, [7 x i8] }, { i8, [7 x i8] } }* @"main$mapbucket.2", i32 0, i32 0, i32 0), i32 1, i8 1, i8 1, i8 0 } -@"main$mapbucket.2" = internal unnamed_addr global { [8 x i8], i8*, { i8, [7 x i8] }, { i8, [7 x i8] } } { [8 x i8] c"\04\00\00\00\00\00\00\00", i8* null, { i8, [7 x i8] } { i8 1, [7 x i8] zeroinitializer }, { i8, [7 x i8] } { i8 2, [7 x i8] zeroinitializer } } -@"main$map.3" = internal global %runtime.hashmap { %runtime.hashmap* null, i8* getelementptr inbounds ({ [8 x i8], i8*, { { [7 x i8]*, [4 x i8] }, [56 x i8] }, { i8, [7 x i8] } }, { [8 x i8], i8*, { { [7 x i8]*, [4 x i8] }, [56 x i8] }, { i8, [7 x i8] } }* @"main$mapbucket.4", i32 0, i32 0, i32 0), i32 1, i8 8, i8 1, i8 0 } -@"main$mapbucket.4" = internal unnamed_addr global { [8 x i8], i8*, { { [7 x i8]*, [4 x i8] }, [56 x i8] }, { i8, [7 x i8] } } { [8 x i8] c"x\00\00\00\00\00\00\00", i8* null, { { [7 x i8]*, [4 x i8] }, [56 x i8] } { { [7 x i8]*, [4 x i8] } { [7 x i8]* @main.init.string, [4 x i8] c"\07\00\00\00" }, [56 x i8] zeroinitializer }, { i8, [7 x i8] } { i8 2, [7 x i8] zeroinitializer } } - -define void @runtime.initAll() unnamed_addr { -entry: - ret void -} diff --git a/testdata/map.go b/testdata/map.go index b93eacac2..558688dc5 100644 --- a/testdata/map.go +++ b/testdata/map.go @@ -1,5 +1,7 @@ package main +import "sort" + var testmap1 = map[string]int{"data": 3} var testmap2 = map[string]int{ "one": 1, @@ -112,7 +114,13 @@ func main() { func readMap(m map[string]int, key string) { println("map length:", len(m)) println("map read:", key, "=", m[key]) - for k, v := range m { + keys := make([]string, 0, len(m)) + for k := range m { + keys = append(keys, k) + } + sort.Strings(keys) + for _, k := range keys { + v := m[k] println(" ", k, "=", v) } } diff --git a/testdata/map.txt b/testdata/map.txt index e6141addc..309881081 100644 --- a/testdata/map.txt +++ b/testdata/map.txt @@ -7,45 +7,45 @@ map read: data = 3 data = 3 map length: 12 map read: three = 3 - one = 1 - two = 2 - three = 3 - four = 4 - five = 5 - six = 6 - seven = 7 eight = 8 + eleven = 11 + five = 5 + four = 4 nine = 9 + one = 1 + seven = 7 + six = 6 ten = 10 - eleven = 11 + three = 3 twelve = 12 + two = 2 map length: 12 map read: ten = 10 - one = 1 - two = 2 - three = 3 - four = 4 - five = 5 - six = 6 - seven = 7 eight = 8 + eleven = 11 + five = 5 + four = 4 nine = 9 + one = 1 + seven = 7 + six = 6 ten = 10 - eleven = 11 + three = 3 twelve = 12 + two = 2 map length: 11 map read: seven = 7 - one = 1 - two = 2 - three = 3 - four = 4 - five = 5 - seven = 7 eight = 8 + eleven = 11 + five = 5 + four = 4 nine = 9 + one = 1 + seven = 7 ten = 10 - eleven = 11 + three = 3 twelve = 12 + two = 2 lookup with comma-ok: eight 8 true lookup with comma-ok: nokey 0 false false true 2 |