1 package compiler
2 3 import (
4 "fmt"
5 "go/token"
6 "go/types"
7 "math/big"
8 "strings"
9 10 "moxie/compileopts"
11 "moxie/compiler/llvmutil"
12 "tinygo.org/x/go-llvm"
13 )
14 15 // This file contains helper functions for LLVM that are not exposed in the Go
16 // bindings.
17 18 // createTemporaryAlloca creates a new alloca in the entry block and adds
19 // lifetime start information in the IR signalling that the alloca won't be used
20 // before this point.
21 //
22 // This is useful for creating temporary allocas for intrinsics. Don't forget to
23 // end the lifetime using emitLifetimeEnd after you're done with it.
24 func (b *builder) createTemporaryAlloca(t llvm.Type, name string) (alloca, size llvm.Value) {
25 return llvmutil.CreateTemporaryAlloca(b.Builder, b.mod, t, name)
26 }
27 28 // insertBasicBlock inserts a new basic block after the current basic block.
29 // This is useful when inserting new basic blocks while converting a
30 // *ssa.BasicBlock to a llvm.BasicBlock and the LLVM basic block needs some
31 // extra blocks.
32 // It does not update b.blockExits, this must be done by the caller.
33 func (b *builder) insertBasicBlock(name string) llvm.BasicBlock {
34 currentBB := b.Builder.GetInsertBlock()
35 nextBB := llvm.NextBasicBlock(currentBB)
36 if nextBB.IsNil() {
37 // Last basic block in the function, so add one to the end.
38 return b.ctx.AddBasicBlock(b.llvmFn, name)
39 }
40 // Insert a basic block before the next basic block - that is, at the
41 // current insert location.
42 return b.ctx.InsertBasicBlock(nextBB, name)
43 }
44 45 // emitLifetimeEnd signals the end of an (alloca) lifetime by calling the
46 // llvm.lifetime.end intrinsic. It is commonly used together with
47 // createTemporaryAlloca.
48 func (b *builder) emitLifetimeEnd(ptr, size llvm.Value) {
49 llvmutil.EmitLifetimeEnd(b.Builder, b.mod, ptr, size)
50 }
51 52 // emitPointerPack packs the list of values into a single pointer value using
53 // bitcasts, or else allocates a value on the heap if it cannot be packed in the
54 // pointer value directly. It returns the pointer with the packed data.
55 // If the values are all constants, they are be stored in a constant global and
56 // deduplicated.
57 func (b *builder) emitPointerPack(values []llvm.Value) llvm.Value {
58 valueTypes := make([]llvm.Type, len(values))
59 for i, value := range values {
60 valueTypes[i] = value.Type()
61 }
62 packedType := b.ctx.StructType(valueTypes, false)
63 64 // Allocate memory for the packed data.
65 size := b.targetData.TypeAllocSize(packedType)
66 if size == 0 {
67 return llvm.ConstPointerNull(b.dataPtrType)
68 } else if len(values) == 1 && values[0].Type().TypeKind() == llvm.PointerTypeKind {
69 return values[0]
70 } else if size <= b.targetData.TypeAllocSize(b.dataPtrType) {
71 // Packed data fits in a pointer, so store it directly inside the
72 // pointer.
73 if len(values) == 1 && values[0].Type().TypeKind() == llvm.IntegerTypeKind {
74 // Try to keep this cast in SSA form.
75 return b.CreateIntToPtr(values[0], b.dataPtrType, "pack.int")
76 }
77 78 // Because packedType is a struct and we have to cast it to a *i8, store
79 // it in a *i8 alloca first and load the *i8 value from there. This is
80 // effectively a bitcast.
81 packedAlloc, _ := b.createTemporaryAlloca(b.dataPtrType, "")
82 83 if size < b.targetData.TypeAllocSize(b.dataPtrType) {
84 // The alloca is bigger than the value that will be stored in it.
85 // To avoid having some bits undefined, zero the alloca first.
86 // Hopefully this will get optimized away.
87 b.CreateStore(llvm.ConstNull(b.dataPtrType), packedAlloc)
88 }
89 90 // Store all values in the alloca.
91 for i, value := range values {
92 indices := []llvm.Value{
93 llvm.ConstInt(b.ctx.Int32Type(), 0, false),
94 llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false),
95 }
96 gep := b.CreateInBoundsGEP(packedType, packedAlloc, indices, "")
97 b.CreateStore(value, gep)
98 }
99 100 // Load value (the *i8) from the alloca.
101 result := b.CreateLoad(b.dataPtrType, packedAlloc, "")
102 103 // End the lifetime of the alloca, to help the optimizer.
104 packedSize := llvm.ConstInt(b.ctx.Int64Type(), b.targetData.TypeAllocSize(packedAlloc.Type()), false)
105 b.emitLifetimeEnd(packedAlloc, packedSize)
106 107 return result
108 } else {
109 // Check if the values are all constants.
110 constant := true
111 for _, v := range values {
112 if !v.IsConstant() {
113 constant = false
114 break
115 }
116 }
117 118 if constant {
119 // The data is known at compile time, so store it in a constant global.
120 // The global address is marked as unnamed, which allows LLVM to merge duplicates.
121 global := llvm.AddGlobal(b.mod, packedType, b.pkg.Path()+"$pack")
122 global.SetInitializer(b.ctx.ConstStruct(values, false))
123 global.SetGlobalConstant(true)
124 global.SetUnnamedAddr(true)
125 global.SetLinkage(llvm.InternalLinkage)
126 return global
127 }
128 129 // Packed data is bigger than a pointer, so allocate it on the heap.
130 sizeValue := llvm.ConstInt(b.uintptrType, size, false)
131 align := b.targetData.ABITypeAlignment(packedType)
132 alloc := b.mod.NamedFunction("runtime.alloc")
133 packedAlloc := b.CreateCall(alloc.GlobalValueType(), alloc, []llvm.Value{
134 sizeValue,
135 llvm.ConstNull(b.dataPtrType),
136 llvm.Undef(b.dataPtrType), // unused context parameter
137 }, "")
138 packedAlloc.AddCallSiteAttribute(0, b.ctx.CreateEnumAttribute(llvm.AttributeKindID("align"), uint64(align)))
139 // Store all values in the heap pointer.
140 for i, value := range values {
141 indices := []llvm.Value{
142 llvm.ConstInt(b.ctx.Int32Type(), 0, false),
143 llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false),
144 }
145 gep := b.CreateInBoundsGEP(packedType, packedAlloc, indices, "")
146 b.CreateStore(value, gep)
147 }
148 149 // Return the original heap allocation pointer, which already is an *i8.
150 return packedAlloc
151 }
152 }
153 154 // emitPointerUnpack extracts a list of values packed using emitPointerPack.
155 func (b *builder) emitPointerUnpack(ptr llvm.Value, valueTypes []llvm.Type) []llvm.Value {
156 packedType := b.ctx.StructType(valueTypes, false)
157 158 // Get a correctly-typed pointer to the packed data.
159 var packedAlloc llvm.Value
160 needsLifetimeEnd := false
161 size := b.targetData.TypeAllocSize(packedType)
162 if size == 0 {
163 // No data to unpack.
164 } else if len(valueTypes) == 1 && valueTypes[0].TypeKind() == llvm.PointerTypeKind {
165 // A single pointer is always stored directly.
166 return []llvm.Value{ptr}
167 } else if size <= b.targetData.TypeAllocSize(b.dataPtrType) {
168 // Packed data stored directly in pointer.
169 if len(valueTypes) == 1 && valueTypes[0].TypeKind() == llvm.IntegerTypeKind {
170 // Keep this cast in SSA form.
171 return []llvm.Value{b.CreatePtrToInt(ptr, valueTypes[0], "unpack.int")}
172 }
173 // Fallback: load it using an alloca.
174 packedAlloc, _ = b.createTemporaryAlloca(b.dataPtrType, "unpack.raw.alloc")
175 b.CreateStore(ptr, packedAlloc)
176 needsLifetimeEnd = true
177 } else {
178 // Packed data stored on the heap.
179 packedAlloc = ptr
180 }
181 // Load each value from the packed data.
182 values := make([]llvm.Value, len(valueTypes))
183 for i, valueType := range valueTypes {
184 if b.targetData.TypeAllocSize(valueType) == 0 {
185 // This value has length zero, so there's nothing to load.
186 values[i] = llvm.ConstNull(valueType)
187 continue
188 }
189 indices := []llvm.Value{
190 llvm.ConstInt(b.ctx.Int32Type(), 0, false),
191 llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false),
192 }
193 gep := b.CreateInBoundsGEP(packedType, packedAlloc, indices, "")
194 values[i] = b.CreateLoad(valueType, gep, "")
195 }
196 if needsLifetimeEnd {
197 allocSize := llvm.ConstInt(b.ctx.Int64Type(), b.targetData.TypeAllocSize(b.uintptrType), false)
198 b.emitLifetimeEnd(packedAlloc, allocSize)
199 }
200 return values
201 }
202 203 // makeGlobalArray creates a new LLVM global with the given name and integers as
204 // contents, and returns the global and initializer type.
205 // Note that it is left with the default linkage etc., you should set
206 // linkage/constant/etc properties yourself.
207 func (c *compilerContext) makeGlobalArray(buf []byte, name string, elementType llvm.Type) (llvm.Type, llvm.Value) {
208 globalType := llvm.ArrayType(elementType, len(buf))
209 global := llvm.AddGlobal(c.mod, globalType, name)
210 value := llvm.Undef(globalType)
211 for i := 0; i < len(buf); i++ {
212 ch := uint64(buf[i])
213 value = c.builder.CreateInsertValue(value, llvm.ConstInt(elementType, ch, false), i, "")
214 }
215 global.SetInitializer(value)
216 return globalType, global
217 }
218 219 // createObjectLayout returns a LLVM value (of type i8*) that describes where
220 // there are pointers in the type t. If all the data fits in a word, it is
221 // returned as a word. Otherwise it will store the data in a global.
222 //
223 // The value contains two pieces of information: the length of the object and
224 // which words contain a pointer (indicated by setting the given bit to 1). For
225 // arrays, only the element is stored. This works because the GC knows the
226 // object size and can therefore know how this value is repeated in the object.
227 //
228 // For details on what's in this value, see src/runtime/gc_precise.go.
229 func (c *compilerContext) createObjectLayout(t llvm.Type, pos token.Pos) llvm.Value {
230 // Use the element type for arrays. This works even for nested arrays.
231 for {
232 kind := t.TypeKind()
233 if kind == llvm.ArrayTypeKind {
234 t = t.ElementType()
235 continue
236 }
237 if kind == llvm.StructTypeKind {
238 fields := t.StructElementTypes()
239 if len(fields) == 1 {
240 t = fields[0]
241 continue
242 }
243 }
244 break
245 }
246 247 // Do a few checks to see whether we need to generate any object layout
248 // information at all.
249 objectSizeBytes := c.targetData.TypeAllocSize(t)
250 pointerSize := c.targetData.TypeAllocSize(c.dataPtrType)
251 pointerAlignment := c.targetData.PrefTypeAlignment(c.dataPtrType)
252 if objectSizeBytes < pointerSize {
253 // Too small to contain a pointer.
254 layout := (uint64(1) << 1) | 1
255 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
256 }
257 bitmap := c.getPointerBitmap(t, pos)
258 if bitmap.BitLen() == 0 {
259 // There are no pointers in this type, so we can simplify the layout.
260 // TODO: this can be done in many other cases, e.g. when allocating an
261 // array (like [4][]byte, which repeats a slice 4 times).
262 layout := (uint64(1) << 1) | 1
263 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
264 }
265 if objectSizeBytes%uint64(pointerAlignment) != 0 {
266 // This shouldn't happen except for packed structs, which aren't
267 // currently used.
268 c.addError(pos, "internal error: unexpected object size for object with pointer field")
269 return llvm.ConstNull(c.dataPtrType)
270 }
271 objectSizeWords := objectSizeBytes / uint64(pointerAlignment)
272 273 pointerBits := pointerSize * 8
274 var sizeFieldBits uint64
275 switch pointerBits {
276 case 16:
277 sizeFieldBits = 4
278 case 32:
279 sizeFieldBits = 5
280 case 64:
281 sizeFieldBits = 6
282 default:
283 panic("unknown pointer size")
284 }
285 layoutFieldBits := pointerBits - 1 - sizeFieldBits
286 287 // Try to emit the value as an inline integer. This is possible in most
288 // cases.
289 if objectSizeWords < layoutFieldBits {
290 // If it can be stored directly in the pointer value, do so.
291 // The runtime knows that if the least significant bit of the pointer is
292 // set, the pointer contains the value itself.
293 layout := bitmap.Uint64()<<(sizeFieldBits+1) | (objectSizeWords << 1) | 1
294 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
295 }
296 297 // Unfortunately, the object layout is too big to fit in a pointer-sized
298 // integer. Store it in a global instead.
299 300 // Try first whether the global already exists. All objects with a
301 // particular name have the same type, so this is possible.
302 globalName := "runtime/gc.layout:" + fmt.Sprintf("%d-%0*x", objectSizeWords, (objectSizeWords+15)/16, bitmap)
303 global := c.mod.NamedGlobal(globalName)
304 if !global.IsNil() {
305 return global
306 }
307 308 // Create the global initializer.
309 bitmapBytes := make([]byte, int(objectSizeWords+7)/8)
310 bitmap.FillBytes(bitmapBytes)
311 reverseBytes(bitmapBytes) // big-endian to little-endian
312 var bitmapByteValues []llvm.Value
313 for _, b := range bitmapBytes {
314 bitmapByteValues = append(bitmapByteValues, llvm.ConstInt(c.ctx.Int8Type(), uint64(b), false))
315 }
316 initializer := c.ctx.ConstStruct([]llvm.Value{
317 llvm.ConstInt(c.uintptrType, objectSizeWords, false),
318 llvm.ConstArray(c.ctx.Int8Type(), bitmapByteValues),
319 }, false)
320 321 global = llvm.AddGlobal(c.mod, initializer.Type(), globalName)
322 global.SetInitializer(initializer)
323 global.SetUnnamedAddr(true)
324 global.SetGlobalConstant(true)
325 global.SetLinkage(llvm.LinkOnceODRLinkage)
326 if c.targetData.PrefTypeAlignment(c.uintptrType) < 2 {
327 // AVR doesn't have alignment by default.
328 global.SetAlignment(2)
329 }
330 if c.Debug && pos != token.NoPos {
331 // Creating a fake global so that the value can be inspected in GDB.
332 // For example, the layout for strings.stringFinder (as of Go version
333 // 1.15) has the following type according to GDB:
334 // type = struct {
335 // uintptr numBits;
336 // uint8 data[33];
337 // }
338 // ...that's sort of a mixed C/Go type, but it is readable. More
339 // importantly, these object layout globals can be read and printed by
340 // GDB which may be useful for debugging.
341 position := c.program.Fset.Position(pos)
342 diglobal := c.dibuilder.CreateGlobalVariableExpression(c.difiles[position.Filename], llvm.DIGlobalVariableExpression{
343 Name: globalName,
344 File: c.getDIFile(position.Filename),
345 Line: position.Line,
346 Type: c.getDIType(types.NewStruct([]*types.Var{
347 types.NewVar(pos, nil, "numBits", types.Typ[types.Uintptr]),
348 types.NewVar(pos, nil, "data", types.NewArray(types.Typ[types.Byte], int64(len(bitmapByteValues)))),
349 }, nil)),
350 LocalToUnit: false,
351 Expr: c.dibuilder.CreateExpression(nil),
352 })
353 global.AddMetadata(0, diglobal)
354 }
355 356 return global
357 }
358 359 // getPointerBitmap scans the given LLVM type for pointers and sets bits in a
360 // bigint at the word offset that contains a pointer. This scan is recursive.
361 func (c *compilerContext) getPointerBitmap(typ llvm.Type, pos token.Pos) *big.Int {
362 alignment := c.targetData.PrefTypeAlignment(c.dataPtrType)
363 switch typ.TypeKind() {
364 case llvm.IntegerTypeKind, llvm.FloatTypeKind, llvm.DoubleTypeKind:
365 return big.NewInt(0)
366 case llvm.PointerTypeKind:
367 return big.NewInt(1)
368 case llvm.StructTypeKind:
369 ptrs := big.NewInt(0)
370 for i, subtyp := range typ.StructElementTypes() {
371 subptrs := c.getPointerBitmap(subtyp, pos)
372 if subptrs.BitLen() == 0 {
373 continue
374 }
375 offset := c.targetData.ElementOffset(typ, i)
376 if offset%uint64(alignment) != 0 {
377 // This error will let the compilation fail, but by continuing
378 // the error can still easily be shown.
379 c.addError(pos, "internal error: allocated struct contains unaligned pointer")
380 continue
381 }
382 subptrs.Lsh(subptrs, uint(offset)/uint(alignment))
383 ptrs.Or(ptrs, subptrs)
384 }
385 return ptrs
386 case llvm.ArrayTypeKind:
387 subtyp := typ.ElementType()
388 subptrs := c.getPointerBitmap(subtyp, pos)
389 ptrs := big.NewInt(0)
390 if subptrs.BitLen() == 0 {
391 return ptrs
392 }
393 elementSize := c.targetData.TypeAllocSize(subtyp)
394 if elementSize%uint64(alignment) != 0 {
395 // This error will let the compilation fail (but continues so that
396 // other errors can be shown).
397 c.addError(pos, "internal error: allocated array contains unaligned pointer")
398 return ptrs
399 }
400 for i := 0; i < typ.ArrayLength(); i++ {
401 ptrs.Lsh(ptrs, uint(elementSize)/uint(alignment))
402 ptrs.Or(ptrs, subptrs)
403 }
404 return ptrs
405 default:
406 // Should not happen.
407 panic("unknown LLVM type")
408 }
409 }
410 411 // archFamily returns the architecture from the LLVM triple but with some
412 // architecture names ("armv6", "thumbv7m", etc) merged into a single
413 // architecture name ("arm").
414 func (c *compilerContext) archFamily() string {
415 return compileopts.CanonicalArchName(c.Triple)
416 }
417 418 // isThumb returns whether we're in ARM or in Thumb mode. It panics if the
419 // features string is not one for an ARM architecture.
420 func (c *compilerContext) isThumb() bool {
421 var isThumb, isNotThumb bool
422 for _, feature := range strings.Split(c.Features, ",") {
423 if feature == "+thumb-mode" {
424 isThumb = true
425 }
426 if feature == "-thumb-mode" {
427 isNotThumb = true
428 }
429 }
430 if isThumb == isNotThumb {
431 panic("unexpected feature flags")
432 }
433 return isThumb
434 }
435 436 // readStackPointer emits a LLVM intrinsic call that returns the current stack
437 // pointer as an *i8.
438 func (b *builder) readStackPointer() llvm.Value {
439 name := "llvm.stacksave.p0"
440 if llvmutil.Version() < 18 {
441 name = "llvm.stacksave" // backwards compatibility with LLVM 17 and below
442 }
443 stacksave := b.mod.NamedFunction(name)
444 if stacksave.IsNil() {
445 fnType := llvm.FunctionType(b.dataPtrType, nil, false)
446 stacksave = llvm.AddFunction(b.mod, name, fnType)
447 }
448 return b.CreateCall(stacksave.GlobalValueType(), stacksave, nil, "")
449 }
450 451 // writeStackPointer emits a LLVM intrinsic call that updates the current stack
452 // pointer.
453 func (b *builder) writeStackPointer(sp llvm.Value) {
454 name := "llvm.stackrestore.p0"
455 if llvmutil.Version() < 18 {
456 name = "llvm.stackrestore" // backwards compatibility with LLVM 17 and below
457 }
458 stackrestore := b.mod.NamedFunction(name)
459 if stackrestore.IsNil() {
460 fnType := llvm.FunctionType(b.ctx.VoidType(), []llvm.Type{b.dataPtrType}, false)
461 stackrestore = llvm.AddFunction(b.mod, name, fnType)
462 }
463 b.CreateCall(stackrestore.GlobalValueType(), stackrestore, []llvm.Value{sp}, "")
464 }
465 466 // createZExtOrTrunc lets the input value fit in the output type bits, by zero
467 // extending or truncating the integer.
468 func (b *builder) createZExtOrTrunc(value llvm.Value, t llvm.Type) llvm.Value {
469 valueBits := value.Type().IntTypeWidth()
470 resultBits := t.IntTypeWidth()
471 if valueBits > resultBits {
472 value = b.CreateTrunc(value, t, "")
473 } else if valueBits < resultBits {
474 value = b.CreateZExt(value, t, "")
475 }
476 return value
477 }
478 479 // Reverse a slice of bytes. From the wiki:
480 // https://github.com/golang/go/wiki/SliceTricks#reversing
481 func reverseBytes(buf []byte) {
482 for i := len(buf)/2 - 1; i >= 0; i-- {
483 opp := len(buf) - 1 - i
484 buf[i], buf[opp] = buf[opp], buf[i]
485 }
486 }
487