1 package compiler
2 3 // This file emits the correct map intrinsics for map operations.
4 5 import (
6 "go/token"
7 "go/types"
8 9 "moxie/src/moxie"
10 "golang.org/x/tools/go/ssa"
11 "tinygo.org/x/go-llvm"
12 )
13 14 // createMakeMap creates a new map object (runtime.hashmap) by allocating and
15 // initializing an appropriately sized object.
16 func (b *builder) createMakeMap(expr *ssa.MakeMap) (llvm.Value, error) {
17 mapType := expr.Type().Underlying().(*types.Map)
18 keyType := mapType.Key().Underlying()
19 llvmValueType := b.getLLVMType(mapType.Elem().Underlying())
20 var llvmKeyType llvm.Type
21 var alg uint64
22 if isStringLike(keyType) {
23 // String/[]byte keys (Moxie: string=[]byte).
24 llvmKeyType = b.getLLVMType(keyType)
25 alg = uint64(moxie.HashmapAlgorithmContent)
26 } else if hashmapIsBinaryKey(keyType) {
27 // Trivially comparable keys.
28 llvmKeyType = b.getLLVMType(keyType)
29 alg = uint64(moxie.HashmapAlgorithmBinary)
30 } else {
31 // All other keys. Implemented as map[interface{}]valueType for ease of
32 // implementation.
33 llvmKeyType = b.getLLVMRuntimeType("_interface")
34 alg = uint64(moxie.HashmapAlgorithmInterface)
35 }
36 keySize := b.targetData.TypeAllocSize(llvmKeyType)
37 valueSize := b.targetData.TypeAllocSize(llvmValueType)
38 llvmKeySize := llvm.ConstInt(b.uintptrType, keySize, false)
39 llvmValueSize := llvm.ConstInt(b.uintptrType, valueSize, false)
40 sizeHint := llvm.ConstInt(b.uintptrType, 8, false)
41 algEnum := llvm.ConstInt(b.ctx.Int8Type(), alg, false)
42 if expr.Reserve != nil {
43 sizeHint = b.getValue(expr.Reserve, getPos(expr))
44 var err error
45 sizeHint, err = b.createConvert(expr.Reserve.Type(), types.Typ[types.Uintptr], sizeHint, expr.Pos())
46 if err != nil {
47 return llvm.Value{}, err
48 }
49 }
50 hashmap := b.createRuntimeCall("hashmapMake", []llvm.Value{llvmKeySize, llvmValueSize, sizeHint, algEnum}, "")
51 return hashmap, nil
52 }
53 54 // createMapLookup returns the value in a map. It calls a runtime function
55 // depending on the map key type to load the map value and its comma-ok value.
56 func (b *builder) createMapLookup(keyType, valueType types.Type, m, key llvm.Value, commaOk bool, pos token.Pos) (llvm.Value, error) {
57 llvmValueType := b.getLLVMType(valueType)
58 59 // Allocate the memory for the resulting type. Do not zero this memory: it
60 // will be zeroed by the hashmap get implementation if the key is not
61 // present in the map.
62 mapValueAlloca, mapValueAllocaSize := b.createTemporaryAlloca(llvmValueType, "hashmap.value")
63 64 // We need the map size (with type uintptr) to pass to the hashmap*Get
65 // functions. This is necessary because those *Get functions are valid on
66 // nil maps, and they'll need to zero the value pointer by that number of
67 // bytes.
68 mapValueSize := mapValueAllocaSize
69 if mapValueSize.Type().IntTypeWidth() > b.uintptrType.IntTypeWidth() {
70 mapValueSize = llvm.ConstTrunc(mapValueSize, b.uintptrType)
71 }
72 73 // Do the lookup. How it is done depends on the key type.
74 var commaOkValue llvm.Value
75 origKeyType := keyType
76 keyType = keyType.Underlying()
77 if isStringLike(keyType) {
78 // key is string/[]byte (Moxie: string=[]byte)
79 params := []llvm.Value{m, key, mapValueAlloca, mapValueSize}
80 commaOkValue = b.createRuntimeCall("hashmapContentGet", params, "")
81 } else if hashmapIsBinaryKey(keyType) {
82 // key can be compared with runtime.memequal
83 // Store the key in an alloca, in the entry block to avoid dynamic stack
84 // growth.
85 mapKeyAlloca, mapKeySize := b.createTemporaryAlloca(key.Type(), "hashmap.key")
86 b.CreateStore(key, mapKeyAlloca)
87 b.zeroUndefBytes(b.getLLVMType(keyType), mapKeyAlloca)
88 // Fetch the value from the hashmap.
89 params := []llvm.Value{m, mapKeyAlloca, mapValueAlloca, mapValueSize}
90 commaOkValue = b.createRuntimeCall("hashmapBinaryGet", params, "")
91 b.emitLifetimeEnd(mapKeyAlloca, mapKeySize)
92 } else {
93 // Not trivially comparable using memcmp. Make it an interface instead.
94 itfKey := key
95 if _, ok := keyType.(*types.Interface); !ok {
96 // Not already an interface, so convert it to an interface now.
97 itfKey = b.createMakeInterface(key, origKeyType, pos)
98 }
99 params := []llvm.Value{m, itfKey, mapValueAlloca, mapValueSize}
100 commaOkValue = b.createRuntimeCall("hashmapInterfaceGet", params, "")
101 }
102 103 // Load the resulting value from the hashmap. The value is set to the zero
104 // value if the key doesn't exist in the hashmap.
105 mapValue := b.CreateLoad(llvmValueType, mapValueAlloca, "")
106 b.emitLifetimeEnd(mapValueAlloca, mapValueAllocaSize)
107 108 if commaOk {
109 tuple := llvm.Undef(b.ctx.StructType([]llvm.Type{llvmValueType, b.ctx.Int1Type()}, false))
110 tuple = b.CreateInsertValue(tuple, mapValue, 0, "")
111 tuple = b.CreateInsertValue(tuple, commaOkValue, 1, "")
112 return tuple, nil
113 } else {
114 return mapValue, nil
115 }
116 }
117 118 // createMapUpdate updates a map key to a given value, by creating an
119 // appropriate runtime call.
120 func (b *builder) createMapUpdate(keyType types.Type, m, key, value llvm.Value, pos token.Pos) {
121 valueAlloca, valueSize := b.createTemporaryAlloca(value.Type(), "hashmap.value")
122 b.CreateStore(value, valueAlloca)
123 origKeyType := keyType
124 keyType = keyType.Underlying()
125 if isStringLike(keyType) {
126 // key is string/[]byte (Moxie: string=[]byte)
127 params := []llvm.Value{m, key, valueAlloca}
128 b.createRuntimeCall("hashmapContentSet", params, "")
129 } else if hashmapIsBinaryKey(keyType) {
130 // key can be compared with runtime.memequal
131 keyAlloca, keySize := b.createTemporaryAlloca(key.Type(), "hashmap.key")
132 b.CreateStore(key, keyAlloca)
133 b.zeroUndefBytes(b.getLLVMType(keyType), keyAlloca)
134 params := []llvm.Value{m, keyAlloca, valueAlloca}
135 b.createRuntimeCall("hashmapBinarySet", params, "")
136 b.emitLifetimeEnd(keyAlloca, keySize)
137 } else {
138 // Key is not trivially comparable, so compare it as an interface instead.
139 itfKey := key
140 if _, ok := keyType.(*types.Interface); !ok {
141 // Not already an interface, so convert it to an interface first.
142 itfKey = b.createMakeInterface(key, origKeyType, pos)
143 }
144 params := []llvm.Value{m, itfKey, valueAlloca}
145 b.createRuntimeCall("hashmapInterfaceSet", params, "")
146 }
147 b.emitLifetimeEnd(valueAlloca, valueSize)
148 }
149 150 // createMapDelete deletes a key from a map by calling the appropriate runtime
151 // function. It is the implementation of the Go delete() builtin.
152 func (b *builder) createMapDelete(keyType types.Type, m, key llvm.Value, pos token.Pos) error {
153 origKeyType := keyType
154 keyType = keyType.Underlying()
155 if isStringLike(keyType) {
156 // key is string/[]byte (Moxie: string=[]byte)
157 params := []llvm.Value{m, key}
158 b.createRuntimeCall("hashmapContentDelete", params, "")
159 return nil
160 } else if hashmapIsBinaryKey(keyType) {
161 keyAlloca, keySize := b.createTemporaryAlloca(key.Type(), "hashmap.key")
162 b.CreateStore(key, keyAlloca)
163 b.zeroUndefBytes(b.getLLVMType(keyType), keyAlloca)
164 params := []llvm.Value{m, keyAlloca}
165 b.createRuntimeCall("hashmapBinaryDelete", params, "")
166 b.emitLifetimeEnd(keyAlloca, keySize)
167 return nil
168 } else {
169 // Key is not trivially comparable, so compare it as an interface
170 // instead.
171 itfKey := key
172 if _, ok := keyType.(*types.Interface); !ok {
173 // Not already an interface, so convert it to an interface first.
174 itfKey = b.createMakeInterface(key, origKeyType, pos)
175 }
176 params := []llvm.Value{m, itfKey}
177 b.createRuntimeCall("hashmapInterfaceDelete", params, "")
178 return nil
179 }
180 }
181 182 // Clear the given map.
183 func (b *builder) createMapClear(m llvm.Value) {
184 b.createRuntimeCall("hashmapClear", []llvm.Value{m}, "")
185 }
186 187 // createMapIteratorNext lowers the *ssa.Next instruction for iterating over a
188 // map. It returns a tuple of {bool, key, value} with the result of the
189 // iteration.
190 func (b *builder) createMapIteratorNext(rangeVal ssa.Value, llvmRangeVal, it llvm.Value) llvm.Value {
191 // Determine the type of the values to return from the *ssa.Next
192 // instruction. It is returned as {bool, keyType, valueType}.
193 keyType := rangeVal.Type().Underlying().(*types.Map).Key()
194 valueType := rangeVal.Type().Underlying().(*types.Map).Elem()
195 llvmKeyType := b.getLLVMType(keyType)
196 llvmValueType := b.getLLVMType(valueType)
197 198 // There is a special case in which keys are stored as an interface value
199 // instead of the value they normally are. This happens for non-trivially
200 // comparable types such as float32 or some structs.
201 isKeyStoredAsInterface := false
202 if isStringLike(keyType.Underlying()) {
203 // key is string/[]byte (Moxie: string=[]byte)
204 } else if hashmapIsBinaryKey(keyType) {
205 // key can be compared with runtime.memequal
206 } else {
207 // The key is stored as an interface value, and may or may not be an
208 // interface type (for example, float32 keys are stored as an interface
209 // value).
210 if _, ok := keyType.Underlying().(*types.Interface); !ok {
211 isKeyStoredAsInterface = true
212 }
213 }
214 215 // Determine the type of the key as stored in the map.
216 llvmStoredKeyType := llvmKeyType
217 if isKeyStoredAsInterface {
218 llvmStoredKeyType = b.getLLVMRuntimeType("_interface")
219 }
220 221 // Extract the key and value from the map.
222 mapKeyAlloca, mapKeySize := b.createTemporaryAlloca(llvmStoredKeyType, "range.key")
223 mapValueAlloca, mapValueSize := b.createTemporaryAlloca(llvmValueType, "range.value")
224 ok := b.createRuntimeCall("hashmapNext", []llvm.Value{llvmRangeVal, it, mapKeyAlloca, mapValueAlloca}, "range.next")
225 mapKey := b.CreateLoad(llvmStoredKeyType, mapKeyAlloca, "")
226 mapValue := b.CreateLoad(llvmValueType, mapValueAlloca, "")
227 228 if isKeyStoredAsInterface {
229 // The key is stored as an interface but it isn't of interface type.
230 // Extract the underlying value.
231 mapKey = b.extractValueFromInterface(mapKey, llvmKeyType)
232 }
233 234 // End the lifetimes of the allocas, because we're done with them.
235 b.emitLifetimeEnd(mapKeyAlloca, mapKeySize)
236 b.emitLifetimeEnd(mapValueAlloca, mapValueSize)
237 238 // Construct the *ssa.Next return value: {ok, mapKey, mapValue}
239 tuple := llvm.Undef(b.ctx.StructType([]llvm.Type{b.ctx.Int1Type(), llvmKeyType, llvmValueType}, false))
240 tuple = b.CreateInsertValue(tuple, ok, 0, "")
241 tuple = b.CreateInsertValue(tuple, mapKey, 1, "")
242 tuple = b.CreateInsertValue(tuple, mapValue, 2, "")
243 244 return tuple
245 }
246 247 // Returns true if this key type does not contain strings, interfaces etc., so
248 // can be compared with runtime.memequal. Note that padding bytes are undef
249 // and can alter two "equal" structs being equal when compared with memequal.
250 // isStringLike reports whether t is string or []byte (Moxie: string=[]byte).
251 func isStringLike(t types.Type) bool {
252 switch t := t.(type) {
253 case *types.Basic:
254 return t.Info()&types.IsString != 0
255 case *types.Slice:
256 if b, ok := t.Elem().(*types.Basic); ok && b.Kind() == types.Byte {
257 return true
258 }
259 }
260 return false
261 }
262 263 func hashmapIsBinaryKey(keyType types.Type) bool {
264 switch keyType := keyType.Underlying().(type) {
265 case *types.Basic:
266 // TODO: unsafe.Pointer is also a binary key, but to support that we
267 // need to fix an issue with interp first (see
268 // https://moxie/pull/4898).
269 return keyType.Info()&(types.IsBoolean|types.IsInteger) != 0
270 case *types.Pointer:
271 return true
272 case *types.Struct:
273 for i := 0; i < keyType.NumFields(); i++ {
274 fieldType := keyType.Field(i).Type().Underlying()
275 if !hashmapIsBinaryKey(fieldType) {
276 return false
277 }
278 }
279 return true
280 case *types.Array:
281 return hashmapIsBinaryKey(keyType.Elem())
282 default:
283 return false
284 }
285 }
286 287 func (b *builder) zeroUndefBytes(llvmType llvm.Type, ptr llvm.Value) error {
288 // We know that hashmapIsBinaryKey is true, so we only have to handle those types that can show up there.
289 // To zero all undefined bytes, we iterate over all the fields in the type. For each element, compute the
290 // offset of that element. If it's Basic type, there are no internal padding bytes. For compound types, we recurse to ensure
291 // we handle nested types. Next, we determine if there are any padding bytes before the next
292 // element and zero those as well.
293 294 zero := llvm.ConstInt(b.ctx.Int32Type(), 0, false)
295 296 switch llvmType.TypeKind() {
297 case llvm.IntegerTypeKind:
298 // no padding bytes
299 return nil
300 case llvm.PointerTypeKind:
301 // mo padding bytes
302 return nil
303 case llvm.ArrayTypeKind:
304 llvmArrayType := llvmType
305 llvmElemType := llvmType.ElementType()
306 307 for i := 0; i < llvmArrayType.ArrayLength(); i++ {
308 idx := llvm.ConstInt(b.uintptrType, uint64(i), false)
309 elemPtr := b.CreateInBoundsGEP(llvmArrayType, ptr, []llvm.Value{zero, idx}, "")
310 311 // zero any padding bytes in this element
312 b.zeroUndefBytes(llvmElemType, elemPtr)
313 }
314 315 case llvm.StructTypeKind:
316 llvmStructType := llvmType
317 numFields := llvmStructType.StructElementTypesCount()
318 llvmElementTypes := llvmStructType.StructElementTypes()
319 320 for i := 0; i < numFields; i++ {
321 idx := llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false)
322 elemPtr := b.CreateInBoundsGEP(llvmStructType, ptr, []llvm.Value{zero, idx}, "")
323 324 // zero any padding bytes in this field
325 llvmElemType := llvmElementTypes[i]
326 b.zeroUndefBytes(llvmElemType, elemPtr)
327 328 // zero any padding bytes before the next field, if any
329 offset := b.targetData.ElementOffset(llvmStructType, i)
330 storeSize := b.targetData.TypeStoreSize(llvmElemType)
331 fieldEndOffset := offset + storeSize
332 333 var nextOffset uint64
334 if i < numFields-1 {
335 nextOffset = b.targetData.ElementOffset(llvmStructType, i+1)
336 } else {
337 // Last field? Next offset is the total size of the allocate struct.
338 nextOffset = b.targetData.TypeAllocSize(llvmStructType)
339 }
340 341 if fieldEndOffset != nextOffset {
342 n := llvm.ConstInt(b.uintptrType, nextOffset-fieldEndOffset, false)
343 llvmStoreSize := llvm.ConstInt(b.uintptrType, storeSize, false)
344 paddingStart := b.CreateInBoundsGEP(b.ctx.Int8Type(), elemPtr, []llvm.Value{llvmStoreSize}, "")
345 b.createRuntimeCall("memzero", []llvm.Value{paddingStart, n}, "")
346 }
347 }
348 }
349 350 return nil
351 }
352