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 if b.NeedsStackObjects {
140 b.trackPointer(packedAlloc)
141 }
142 143 // Store all values in the heap pointer.
144 for i, value := range values {
145 indices := []llvm.Value{
146 llvm.ConstInt(b.ctx.Int32Type(), 0, false),
147 llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false),
148 }
149 gep := b.CreateInBoundsGEP(packedType, packedAlloc, indices, "")
150 b.CreateStore(value, gep)
151 }
152 153 // Return the original heap allocation pointer, which already is an *i8.
154 return packedAlloc
155 }
156 }
157 158 // emitPointerUnpack extracts a list of values packed using emitPointerPack.
159 func (b *builder) emitPointerUnpack(ptr llvm.Value, valueTypes []llvm.Type) []llvm.Value {
160 packedType := b.ctx.StructType(valueTypes, false)
161 162 // Get a correctly-typed pointer to the packed data.
163 var packedAlloc llvm.Value
164 needsLifetimeEnd := false
165 size := b.targetData.TypeAllocSize(packedType)
166 if size == 0 {
167 // No data to unpack.
168 } else if len(valueTypes) == 1 && valueTypes[0].TypeKind() == llvm.PointerTypeKind {
169 // A single pointer is always stored directly.
170 return []llvm.Value{ptr}
171 } else if size <= b.targetData.TypeAllocSize(b.dataPtrType) {
172 // Packed data stored directly in pointer.
173 if len(valueTypes) == 1 && valueTypes[0].TypeKind() == llvm.IntegerTypeKind {
174 // Keep this cast in SSA form.
175 return []llvm.Value{b.CreatePtrToInt(ptr, valueTypes[0], "unpack.int")}
176 }
177 // Fallback: load it using an alloca.
178 packedAlloc, _ = b.createTemporaryAlloca(b.dataPtrType, "unpack.raw.alloc")
179 b.CreateStore(ptr, packedAlloc)
180 needsLifetimeEnd = true
181 } else {
182 // Packed data stored on the heap.
183 packedAlloc = ptr
184 }
185 // Load each value from the packed data.
186 values := make([]llvm.Value, len(valueTypes))
187 for i, valueType := range valueTypes {
188 if b.targetData.TypeAllocSize(valueType) == 0 {
189 // This value has length zero, so there's nothing to load.
190 values[i] = llvm.ConstNull(valueType)
191 continue
192 }
193 indices := []llvm.Value{
194 llvm.ConstInt(b.ctx.Int32Type(), 0, false),
195 llvm.ConstInt(b.ctx.Int32Type(), uint64(i), false),
196 }
197 gep := b.CreateInBoundsGEP(packedType, packedAlloc, indices, "")
198 values[i] = b.CreateLoad(valueType, gep, "")
199 }
200 if needsLifetimeEnd {
201 allocSize := llvm.ConstInt(b.ctx.Int64Type(), b.targetData.TypeAllocSize(b.uintptrType), false)
202 b.emitLifetimeEnd(packedAlloc, allocSize)
203 }
204 return values
205 }
206 207 // makeGlobalArray creates a new LLVM global with the given name and integers as
208 // contents, and returns the global and initializer type.
209 // Note that it is left with the default linkage etc., you should set
210 // linkage/constant/etc properties yourself.
211 func (c *compilerContext) makeGlobalArray(buf []byte, name string, elementType llvm.Type) (llvm.Type, llvm.Value) {
212 globalType := llvm.ArrayType(elementType, len(buf))
213 global := llvm.AddGlobal(c.mod, globalType, name)
214 value := llvm.Undef(globalType)
215 for i := 0; i < len(buf); i++ {
216 ch := uint64(buf[i])
217 value = c.builder.CreateInsertValue(value, llvm.ConstInt(elementType, ch, false), i, "")
218 }
219 global.SetInitializer(value)
220 return globalType, global
221 }
222 223 // createObjectLayout returns a LLVM value (of type i8*) that describes where
224 // there are pointers in the type t. If all the data fits in a word, it is
225 // returned as a word. Otherwise it will store the data in a global.
226 //
227 // The value contains two pieces of information: the length of the object and
228 // which words contain a pointer (indicated by setting the given bit to 1). For
229 // arrays, only the element is stored. This works because the GC knows the
230 // object size and can therefore know how this value is repeated in the object.
231 //
232 // For details on what's in this value, see src/runtime/gc_precise.go.
233 func (c *compilerContext) createObjectLayout(t llvm.Type, pos token.Pos) llvm.Value {
234 // Use the element type for arrays. This works even for nested arrays.
235 for {
236 kind := t.TypeKind()
237 if kind == llvm.ArrayTypeKind {
238 t = t.ElementType()
239 continue
240 }
241 if kind == llvm.StructTypeKind {
242 fields := t.StructElementTypes()
243 if len(fields) == 1 {
244 t = fields[0]
245 continue
246 }
247 }
248 break
249 }
250 251 // Do a few checks to see whether we need to generate any object layout
252 // information at all.
253 objectSizeBytes := c.targetData.TypeAllocSize(t)
254 pointerSize := c.targetData.TypeAllocSize(c.dataPtrType)
255 pointerAlignment := c.targetData.PrefTypeAlignment(c.dataPtrType)
256 if objectSizeBytes < pointerSize {
257 // Too small to contain a pointer.
258 layout := (uint64(1) << 1) | 1
259 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
260 }
261 bitmap := c.getPointerBitmap(t, pos)
262 if bitmap.BitLen() == 0 {
263 // There are no pointers in this type, so we can simplify the layout.
264 // TODO: this can be done in many other cases, e.g. when allocating an
265 // array (like [4][]byte, which repeats a slice 4 times).
266 layout := (uint64(1) << 1) | 1
267 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
268 }
269 if objectSizeBytes%uint64(pointerAlignment) != 0 {
270 // This shouldn't happen except for packed structs, which aren't
271 // currently used.
272 c.addError(pos, "internal error: unexpected object size for object with pointer field")
273 return llvm.ConstNull(c.dataPtrType)
274 }
275 objectSizeWords := objectSizeBytes / uint64(pointerAlignment)
276 277 pointerBits := pointerSize * 8
278 var sizeFieldBits uint64
279 switch pointerBits {
280 case 16:
281 sizeFieldBits = 4
282 case 32:
283 sizeFieldBits = 5
284 case 64:
285 sizeFieldBits = 6
286 default:
287 panic("unknown pointer size")
288 }
289 layoutFieldBits := pointerBits - 1 - sizeFieldBits
290 291 // Try to emit the value as an inline integer. This is possible in most
292 // cases.
293 if objectSizeWords < layoutFieldBits {
294 // If it can be stored directly in the pointer value, do so.
295 // The runtime knows that if the least significant bit of the pointer is
296 // set, the pointer contains the value itself.
297 layout := bitmap.Uint64()<<(sizeFieldBits+1) | (objectSizeWords << 1) | 1
298 return llvm.ConstIntToPtr(llvm.ConstInt(c.uintptrType, layout, false), c.dataPtrType)
299 }
300 301 // Unfortunately, the object layout is too big to fit in a pointer-sized
302 // integer. Store it in a global instead.
303 304 // Try first whether the global already exists. All objects with a
305 // particular name have the same type, so this is possible.
306 globalName := "runtime/gc.layout:" + fmt.Sprintf("%d-%0*x", objectSizeWords, (objectSizeWords+15)/16, bitmap)
307 global := c.mod.NamedGlobal(globalName)
308 if !global.IsNil() {
309 return global
310 }
311 312 // Create the global initializer.
313 bitmapBytes := make([]byte, int(objectSizeWords+7)/8)
314 bitmap.FillBytes(bitmapBytes)
315 reverseBytes(bitmapBytes) // big-endian to little-endian
316 var bitmapByteValues []llvm.Value
317 for _, b := range bitmapBytes {
318 bitmapByteValues = append(bitmapByteValues, llvm.ConstInt(c.ctx.Int8Type(), uint64(b), false))
319 }
320 initializer := c.ctx.ConstStruct([]llvm.Value{
321 llvm.ConstInt(c.uintptrType, objectSizeWords, false),
322 llvm.ConstArray(c.ctx.Int8Type(), bitmapByteValues),
323 }, false)
324 325 global = llvm.AddGlobal(c.mod, initializer.Type(), globalName)
326 global.SetInitializer(initializer)
327 global.SetUnnamedAddr(true)
328 global.SetGlobalConstant(true)
329 global.SetLinkage(llvm.LinkOnceODRLinkage)
330 if c.targetData.PrefTypeAlignment(c.uintptrType) < 2 {
331 // AVR doesn't have alignment by default.
332 global.SetAlignment(2)
333 }
334 if c.Debug && pos != token.NoPos {
335 // Creating a fake global so that the value can be inspected in GDB.
336 // For example, the layout for strings.stringFinder (as of Go version
337 // 1.15) has the following type according to GDB:
338 // type = struct {
339 // uintptr numBits;
340 // uint8 data[33];
341 // }
342 // ...that's sort of a mixed C/Go type, but it is readable. More
343 // importantly, these object layout globals can be read and printed by
344 // GDB which may be useful for debugging.
345 position := c.program.Fset.Position(pos)
346 diglobal := c.dibuilder.CreateGlobalVariableExpression(c.difiles[position.Filename], llvm.DIGlobalVariableExpression{
347 Name: globalName,
348 File: c.getDIFile(position.Filename),
349 Line: position.Line,
350 Type: c.getDIType(types.NewStruct([]*types.Var{
351 types.NewVar(pos, nil, "numBits", types.Typ[types.Uintptr]),
352 types.NewVar(pos, nil, "data", types.NewArray(types.Typ[types.Byte], int64(len(bitmapByteValues)))),
353 }, nil)),
354 LocalToUnit: false,
355 Expr: c.dibuilder.CreateExpression(nil),
356 })
357 global.AddMetadata(0, diglobal)
358 }
359 360 return global
361 }
362 363 // getPointerBitmap scans the given LLVM type for pointers and sets bits in a
364 // bigint at the word offset that contains a pointer. This scan is recursive.
365 func (c *compilerContext) getPointerBitmap(typ llvm.Type, pos token.Pos) *big.Int {
366 alignment := c.targetData.PrefTypeAlignment(c.dataPtrType)
367 switch typ.TypeKind() {
368 case llvm.IntegerTypeKind, llvm.FloatTypeKind, llvm.DoubleTypeKind:
369 return big.NewInt(0)
370 case llvm.PointerTypeKind:
371 return big.NewInt(1)
372 case llvm.StructTypeKind:
373 ptrs := big.NewInt(0)
374 for i, subtyp := range typ.StructElementTypes() {
375 subptrs := c.getPointerBitmap(subtyp, pos)
376 if subptrs.BitLen() == 0 {
377 continue
378 }
379 offset := c.targetData.ElementOffset(typ, i)
380 if offset%uint64(alignment) != 0 {
381 // This error will let the compilation fail, but by continuing
382 // the error can still easily be shown.
383 c.addError(pos, "internal error: allocated struct contains unaligned pointer")
384 continue
385 }
386 subptrs.Lsh(subptrs, uint(offset)/uint(alignment))
387 ptrs.Or(ptrs, subptrs)
388 }
389 return ptrs
390 case llvm.ArrayTypeKind:
391 subtyp := typ.ElementType()
392 subptrs := c.getPointerBitmap(subtyp, pos)
393 ptrs := big.NewInt(0)
394 if subptrs.BitLen() == 0 {
395 return ptrs
396 }
397 elementSize := c.targetData.TypeAllocSize(subtyp)
398 if elementSize%uint64(alignment) != 0 {
399 // This error will let the compilation fail (but continues so that
400 // other errors can be shown).
401 c.addError(pos, "internal error: allocated array contains unaligned pointer")
402 return ptrs
403 }
404 for i := 0; i < typ.ArrayLength(); i++ {
405 ptrs.Lsh(ptrs, uint(elementSize)/uint(alignment))
406 ptrs.Or(ptrs, subptrs)
407 }
408 return ptrs
409 default:
410 // Should not happen.
411 panic("unknown LLVM type")
412 }
413 }
414 415 // archFamily returns the architecture from the LLVM triple but with some
416 // architecture names ("armv6", "thumbv7m", etc) merged into a single
417 // architecture name ("arm").
418 func (c *compilerContext) archFamily() string {
419 return compileopts.CanonicalArchName(c.Triple)
420 }
421 422 // isThumb returns whether we're in ARM or in Thumb mode. It panics if the
423 // features string is not one for an ARM architecture.
424 func (c *compilerContext) isThumb() bool {
425 var isThumb, isNotThumb bool
426 for _, feature := range strings.Split(c.Features, ",") {
427 if feature == "+thumb-mode" {
428 isThumb = true
429 }
430 if feature == "-thumb-mode" {
431 isNotThumb = true
432 }
433 }
434 if isThumb == isNotThumb {
435 panic("unexpected feature flags")
436 }
437 return isThumb
438 }
439 440 // readStackPointer emits a LLVM intrinsic call that returns the current stack
441 // pointer as an *i8.
442 func (b *builder) readStackPointer() llvm.Value {
443 name := "llvm.stacksave.p0"
444 if llvmutil.Version() < 18 {
445 name = "llvm.stacksave" // backwards compatibility with LLVM 17 and below
446 }
447 stacksave := b.mod.NamedFunction(name)
448 if stacksave.IsNil() {
449 fnType := llvm.FunctionType(b.dataPtrType, nil, false)
450 stacksave = llvm.AddFunction(b.mod, name, fnType)
451 }
452 return b.CreateCall(stacksave.GlobalValueType(), stacksave, nil, "")
453 }
454 455 // writeStackPointer emits a LLVM intrinsic call that updates the current stack
456 // pointer.
457 func (b *builder) writeStackPointer(sp llvm.Value) {
458 name := "llvm.stackrestore.p0"
459 if llvmutil.Version() < 18 {
460 name = "llvm.stackrestore" // backwards compatibility with LLVM 17 and below
461 }
462 stackrestore := b.mod.NamedFunction(name)
463 if stackrestore.IsNil() {
464 fnType := llvm.FunctionType(b.ctx.VoidType(), []llvm.Type{b.dataPtrType}, false)
465 stackrestore = llvm.AddFunction(b.mod, name, fnType)
466 }
467 b.CreateCall(stackrestore.GlobalValueType(), stackrestore, []llvm.Value{sp}, "")
468 }
469 470 // createZExtOrTrunc lets the input value fit in the output type bits, by zero
471 // extending or truncating the integer.
472 func (b *builder) createZExtOrTrunc(value llvm.Value, t llvm.Type) llvm.Value {
473 valueBits := value.Type().IntTypeWidth()
474 resultBits := t.IntTypeWidth()
475 if valueBits > resultBits {
476 value = b.CreateTrunc(value, t, "")
477 } else if valueBits < resultBits {
478 value = b.CreateZExt(value, t, "")
479 }
480 return value
481 }
482 483 // Reverse a slice of bytes. From the wiki:
484 // https://github.com/golang/go/wiki/SliceTricks#reversing
485 func reverseBytes(buf []byte) {
486 for i := len(buf)/2 - 1; i >= 0; i-- {
487 opp := len(buf) - 1 - i
488 buf[i], buf[opp] = buf[opp], buf[i]
489 }
490 }
491