1 // Package llvmutil contains utility functions used across multiple compiler
2 // packages. For example, they may be used by both the compiler package and
3 // transformation packages.
4 //
5 // Normally, utility packages are avoided. However, in this case, the utility
6 // functions are non-trivial and hard to get right. Copying them to multiple
7 // places would be a big risk if only one of them is updated.
8 package llvmutil
9 10 import (
11 "encoding/binary"
12 "strconv"
13 "strings"
14 15 "tinygo.org/x/go-llvm"
16 )
17 18 // CreateEntryBlockAlloca creates a new alloca in the entry block, even though
19 // the IR builder is located elsewhere. It assumes that the insert point is
20 // at the end of the current block.
21 func CreateEntryBlockAlloca(builder llvm.Builder, t llvm.Type, name string) llvm.Value {
22 currentBlock := builder.GetInsertBlock()
23 entryBlock := currentBlock.Parent().EntryBasicBlock()
24 if entryBlock.FirstInstruction().IsNil() {
25 builder.SetInsertPointAtEnd(entryBlock)
26 } else {
27 builder.SetInsertPointBefore(entryBlock.FirstInstruction())
28 }
29 alloca := builder.CreateAlloca(t, name)
30 builder.SetInsertPointAtEnd(currentBlock)
31 return alloca
32 }
33 34 // CreateTemporaryAlloca creates a new alloca in the entry block and adds
35 // lifetime start information in the IR signalling that the alloca won't be used
36 // before this point.
37 //
38 // This is useful for creating temporary allocas for intrinsics. Don't forget to
39 // end the lifetime using emitLifetimeEnd after you're done with it.
40 func CreateTemporaryAlloca(builder llvm.Builder, mod llvm.Module, t llvm.Type, name string) (alloca, size llvm.Value) {
41 ctx := t.Context()
42 targetData := llvm.NewTargetData(mod.DataLayout())
43 defer targetData.Dispose()
44 alloca = CreateEntryBlockAlloca(builder, t, name)
45 size = llvm.ConstInt(ctx.Int64Type(), targetData.TypeAllocSize(t), false)
46 fnType, fn := getLifetimeStartFunc(mod)
47 builder.CreateCall(fnType, fn, []llvm.Value{size, alloca}, "")
48 return
49 }
50 51 // CreateInstructionAlloca creates an alloca in the entry block, and places lifetime control intrinsics around the instruction
52 func CreateInstructionAlloca(builder llvm.Builder, mod llvm.Module, t llvm.Type, inst llvm.Value, name string) llvm.Value {
53 ctx := mod.Context()
54 targetData := llvm.NewTargetData(mod.DataLayout())
55 defer targetData.Dispose()
56 57 alloca := CreateEntryBlockAlloca(builder, t, name)
58 builder.SetInsertPointBefore(inst)
59 size := llvm.ConstInt(ctx.Int64Type(), targetData.TypeAllocSize(t), false)
60 fnType, fn := getLifetimeStartFunc(mod)
61 builder.CreateCall(fnType, fn, []llvm.Value{size, alloca}, "")
62 if next := llvm.NextInstruction(inst); !next.IsNil() {
63 builder.SetInsertPointBefore(next)
64 } else {
65 builder.SetInsertPointAtEnd(inst.InstructionParent())
66 }
67 fnType, fn = getLifetimeEndFunc(mod)
68 builder.CreateCall(fnType, fn, []llvm.Value{size, alloca}, "")
69 return alloca
70 }
71 72 // EmitLifetimeEnd signals the end of an (alloca) lifetime by calling the
73 // llvm.lifetime.end intrinsic. It is commonly used together with
74 // createTemporaryAlloca.
75 func EmitLifetimeEnd(builder llvm.Builder, mod llvm.Module, ptr, size llvm.Value) {
76 fnType, fn := getLifetimeEndFunc(mod)
77 builder.CreateCall(fnType, fn, []llvm.Value{size, ptr}, "")
78 }
79 80 // getLifetimeStartFunc returns the llvm.lifetime.start intrinsic and creates it
81 // first if it doesn't exist yet.
82 func getLifetimeStartFunc(mod llvm.Module) (llvm.Type, llvm.Value) {
83 fnName := "llvm.lifetime.start.p0"
84 fn := mod.NamedFunction(fnName)
85 ctx := mod.Context()
86 ptrType := llvm.PointerType(ctx.Int8Type(), 0)
87 fnType := llvm.FunctionType(ctx.VoidType(), []llvm.Type{ctx.Int64Type(), ptrType}, false)
88 if fn.IsNil() {
89 fn = llvm.AddFunction(mod, fnName, fnType)
90 }
91 return fnType, fn
92 }
93 94 // getLifetimeEndFunc returns the llvm.lifetime.end intrinsic and creates it
95 // first if it doesn't exist yet.
96 func getLifetimeEndFunc(mod llvm.Module) (llvm.Type, llvm.Value) {
97 fnName := "llvm.lifetime.end.p0"
98 fn := mod.NamedFunction(fnName)
99 ctx := mod.Context()
100 ptrType := llvm.PointerType(ctx.Int8Type(), 0)
101 fnType := llvm.FunctionType(ctx.VoidType(), []llvm.Type{ctx.Int64Type(), ptrType}, false)
102 if fn.IsNil() {
103 fn = llvm.AddFunction(mod, fnName, fnType)
104 }
105 return fnType, fn
106 }
107 108 // SplitBasicBlock splits a LLVM basic block into two parts. All instructions
109 // after afterInst are moved into a new basic block (created right after the
110 // current one) with the given name.
111 func SplitBasicBlock(builder llvm.Builder, afterInst llvm.Value, insertAfter llvm.BasicBlock, name string) llvm.BasicBlock {
112 oldBlock := afterInst.InstructionParent()
113 newBlock := afterInst.Type().Context().InsertBasicBlock(insertAfter, name)
114 var nextInstructions []llvm.Value // values to move
115 116 // Collect to-be-moved instructions.
117 inst := afterInst
118 for {
119 inst = llvm.NextInstruction(inst)
120 if inst.IsNil() {
121 break
122 }
123 nextInstructions = append(nextInstructions, inst)
124 }
125 126 // Move instructions.
127 builder.SetInsertPointAtEnd(newBlock)
128 for _, inst := range nextInstructions {
129 inst.RemoveFromParentAsInstruction()
130 builder.Insert(inst)
131 }
132 133 // Find PHI nodes to update.
134 var phiNodes []llvm.Value // PHI nodes to update
135 for bb := insertAfter.Parent().FirstBasicBlock(); !bb.IsNil(); bb = llvm.NextBasicBlock(bb) {
136 for inst := bb.FirstInstruction(); !inst.IsNil(); inst = llvm.NextInstruction(inst) {
137 if inst.IsAPHINode().IsNil() {
138 continue
139 }
140 needsUpdate := false
141 incomingCount := inst.IncomingCount()
142 for i := 0; i < incomingCount; i++ {
143 if inst.IncomingBlock(i) == oldBlock {
144 needsUpdate = true
145 break
146 }
147 }
148 if !needsUpdate {
149 // PHI node has no incoming edge from the old block.
150 continue
151 }
152 phiNodes = append(phiNodes, inst)
153 }
154 }
155 156 // Update PHI nodes.
157 for _, phi := range phiNodes {
158 builder.SetInsertPointBefore(phi)
159 newPhi := builder.CreatePHI(phi.Type(), "")
160 incomingCount := phi.IncomingCount()
161 incomingVals := make([]llvm.Value, incomingCount)
162 incomingBlocks := make([]llvm.BasicBlock, incomingCount)
163 for i := 0; i < incomingCount; i++ {
164 value := phi.IncomingValue(i)
165 block := phi.IncomingBlock(i)
166 if block == oldBlock {
167 block = newBlock
168 }
169 incomingVals[i] = value
170 incomingBlocks[i] = block
171 }
172 newPhi.AddIncoming(incomingVals, incomingBlocks)
173 phi.ReplaceAllUsesWith(newPhi)
174 phi.EraseFromParentAsInstruction()
175 }
176 177 return newBlock
178 }
179 180 // AppendToGlobal appends the given values to a global array like llvm.used. The global might
181 // not exist yet. The values can be any pointer type, they will be cast to i8*.
182 func AppendToGlobal(mod llvm.Module, globalName string, values ...llvm.Value) {
183 // Read the existing values in the llvm.used array (if it exists).
184 var usedValues []llvm.Value
185 if used := mod.NamedGlobal(globalName); !used.IsNil() {
186 builder := mod.Context().NewBuilder()
187 defer builder.Dispose()
188 usedInitializer := used.Initializer()
189 num := usedInitializer.Type().ArrayLength()
190 for i := 0; i < num; i++ {
191 usedValues = append(usedValues, builder.CreateExtractValue(usedInitializer, i, ""))
192 }
193 used.EraseFromParentAsGlobal()
194 }
195 196 // Add the new values.
197 ptrType := llvm.PointerType(mod.Context().Int8Type(), 0)
198 for _, value := range values {
199 // Note: the bitcast is necessary to cast AVR function pointers to
200 // address space 0 pointer types.
201 usedValues = append(usedValues, llvm.ConstPointerCast(value, ptrType))
202 }
203 204 // Create a new array (with the old and new values).
205 usedInitializer := llvm.ConstArray(ptrType, usedValues)
206 used := llvm.AddGlobal(mod, usedInitializer.Type(), globalName)
207 used.SetInitializer(usedInitializer)
208 used.SetLinkage(llvm.AppendingLinkage)
209 }
210 211 // Version returns the LLVM major version.
212 func Version() int {
213 majorStr := strings.Split(llvm.Version, ".")[0]
214 major, err := strconv.Atoi(majorStr)
215 if err != nil {
216 panic("unexpected error while parsing LLVM version: " + err.Error()) // should not happen
217 }
218 return major
219 }
220 221 // ByteOrder returns the byte order for the given target triple. Most targets are little
222 // endian, but for example MIPS can be big-endian.
223 func ByteOrder(target string) binary.ByteOrder {
224 if strings.HasPrefix(target, "mips-") {
225 return binary.BigEndian
226 } else {
227 return binary.LittleEndian
228 }
229 }
230