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