1 // Package interp is a partial evaluator of code run at package init time. See
2 // the README in this package for details.
3 package interp
4 5 import (
6 "encoding/binary"
7 "fmt"
8 "os"
9 "strings"
10 "time"
11 12 "moxie/compiler/llvmutil"
13 "tinygo.org/x/go-llvm"
14 )
15 16 // Enable extra checks, which should be disabled by default.
17 // This may help track down bugs by adding a few more sanity checks.
18 const checks = true
19 20 // runner contains all state related to one interp run.
21 type runner struct {
22 mod llvm.Module
23 targetData llvm.TargetData
24 builder llvm.Builder
25 pointerSize uint32 // cached pointer size from the TargetData
26 dataPtrType llvm.Type // often used type so created in advance
27 uintptrType llvm.Type // equivalent to uintptr in Go
28 maxAlign int // maximum alignment of an object, alignment of runtime.alloc() result
29 byteOrder binary.ByteOrder // big-endian or little-endian
30 debug bool // log debug messages
31 pkgName string // package name of the currently executing package
32 functionCache map[llvm.Value]*function // cache of compiled functions
33 objects []object // slice of objects in memory
34 globals map[llvm.Value]int // map from global to index in objects slice
35 start time.Time
36 timeout time.Duration
37 callsExecuted uint64
38 }
39 40 func newRunner(mod llvm.Module, timeout time.Duration, debug bool) *runner {
41 r := runner{
42 mod: mod,
43 targetData: llvm.NewTargetData(mod.DataLayout()),
44 byteOrder: llvmutil.ByteOrder(mod.Target()),
45 debug: debug,
46 functionCache: make(map[llvm.Value]*function),
47 objects: []object{{}},
48 globals: make(map[llvm.Value]int),
49 start: time.Now(),
50 timeout: timeout,
51 }
52 r.pointerSize = uint32(r.targetData.PointerSize())
53 r.dataPtrType = llvm.PointerType(mod.Context().Int8Type(), 0)
54 r.uintptrType = mod.Context().IntType(r.targetData.PointerSize() * 8)
55 r.maxAlign = r.targetData.PrefTypeAlignment(r.dataPtrType) // assume pointers are maximally aligned (this is not always the case)
56 return &r
57 }
58 59 // Dispose deallocates all allocated LLVM resources.
60 func (r *runner) dispose() {
61 r.targetData.Dispose()
62 r.targetData = llvm.TargetData{}
63 }
64 65 // Run evaluates runtime.initAll function as much as possible at compile time.
66 // Set debug to true if it should print output while running.
67 func Run(mod llvm.Module, timeout time.Duration, debug bool) error {
68 r := newRunner(mod, timeout, debug)
69 defer r.dispose()
70 71 initAll := mod.NamedFunction("runtime.initAll")
72 bb := initAll.EntryBasicBlock()
73 74 // Create a builder, to insert instructions that could not be evaluated at
75 // compile time.
76 r.builder = mod.Context().NewBuilder()
77 defer r.builder.Dispose()
78 79 // Create a dummy alloca in the entry block that we can set the insert point
80 // to. This is necessary because otherwise we might be removing the
81 // instruction (init call) that we are removing after successful
82 // interpretation.
83 r.builder.SetInsertPointBefore(bb.FirstInstruction())
84 dummy := r.builder.CreateAlloca(r.mod.Context().Int8Type(), "dummy")
85 r.builder.SetInsertPointBefore(dummy)
86 defer dummy.EraseFromParentAsInstruction()
87 88 // Get a list if init calls. A runtime.initAll might look something like this:
89 // func initAll() {
90 // unsafe.init()
91 // machine.init()
92 // runtime.init()
93 // }
94 // This function gets a list of these call instructions.
95 var initCalls []llvm.Value
96 for inst := bb.FirstInstruction(); !inst.IsNil(); inst = llvm.NextInstruction(inst) {
97 if inst == dummy {
98 continue
99 }
100 if !inst.IsAReturnInst().IsNil() {
101 break // ret void
102 }
103 if inst.IsACallInst().IsNil() || inst.CalledValue().IsAFunction().IsNil() {
104 return errorAt(inst, "interp: expected all instructions in "+initAll.Name()+" to be direct calls")
105 }
106 initCalls = append(initCalls, inst)
107 }
108 109 // Run initializers for each package. Once the package initializer is
110 // finished, the call to the package initializer can be removed.
111 for _, call := range initCalls {
112 initName := call.CalledValue().Name()
113 if !strings.HasSuffix(initName, ".init") {
114 return errorAt(call, "interp: expected all instructions in "+initAll.Name()+" to be *.init() calls")
115 }
116 r.pkgName = initName[:len(initName)-len(".init")]
117 fn := call.CalledValue()
118 if r.debug {
119 fmt.Fprintln(os.Stderr, "call:", fn.Name())
120 }
121 _, mem, callErr := r.run(r.getFunction(fn), nil, nil, " ")
122 call.EraseFromParentAsInstruction()
123 if callErr != nil {
124 if isRecoverableError(callErr.Err) {
125 if r.debug {
126 fmt.Fprintln(os.Stderr, "not interpreting", r.pkgName, "because of error:", callErr.Error())
127 }
128 // Remove instructions that were created as part of interpreting
129 // the package.
130 mem.revert()
131 // Create a call to the package initializer (which was
132 // previously deleted).
133 i8undef := llvm.Undef(r.dataPtrType)
134 r.builder.CreateCall(fn.GlobalValueType(), fn, []llvm.Value{i8undef}, "")
135 // Make sure that any globals touched by the package
136 // initializer, won't be accessed by later package initializers.
137 err := r.markExternalLoad(fn)
138 if err != nil {
139 return fmt.Errorf("failed to interpret package %s: %w", r.pkgName, err)
140 }
141 continue
142 }
143 return callErr
144 }
145 for index, obj := range mem.objects {
146 r.objects[index] = obj
147 }
148 }
149 r.pkgName = ""
150 151 // Update all global variables in the LLVM module.
152 mem := memoryView{r: r}
153 for i, obj := range r.objects {
154 if obj.llvmGlobal.IsNil() {
155 continue
156 }
157 if obj.buffer == nil {
158 continue
159 }
160 if obj.constant {
161 continue // constant buffers can't have been modified
162 }
163 initializer, err := obj.buffer.toLLVMValue(obj.llvmGlobal.GlobalValueType(), &mem)
164 if err == errInvalidPtrToIntSize {
165 // This can happen when a previous interp run did not have the
166 // correct LLVM type for a global and made something up. In that
167 // case, some fields could be written out as a series of (null)
168 // bytes even though they actually contain a pointer value.
169 // As a fallback, use asRawValue to get something of the correct
170 // memory layout.
171 initializer, err := obj.buffer.asRawValue(r).rawLLVMValue(&mem)
172 if err != nil {
173 return err
174 }
175 initializerType := initializer.Type()
176 newGlobal := llvm.AddGlobal(mod, initializerType, obj.llvmGlobal.Name()+".tmp")
177 newGlobal.SetInitializer(initializer)
178 newGlobal.SetLinkage(obj.llvmGlobal.Linkage())
179 newGlobal.SetAlignment(obj.llvmGlobal.Alignment())
180 // TODO: copy debug info, unnamed_addr, ...
181 obj.llvmGlobal.ReplaceAllUsesWith(newGlobal)
182 name := obj.llvmGlobal.Name()
183 obj.llvmGlobal.EraseFromParentAsGlobal()
184 newGlobal.SetName(name)
185 186 // Update interp-internal references.
187 delete(r.globals, obj.llvmGlobal)
188 obj.llvmGlobal = newGlobal
189 r.globals[newGlobal] = i
190 r.objects[i] = obj
191 continue
192 }
193 if err != nil {
194 return err
195 }
196 if checks && initializer.Type() != obj.llvmGlobal.GlobalValueType() {
197 panic("initializer type mismatch")
198 }
199 obj.llvmGlobal.SetInitializer(initializer)
200 }
201 202 return nil
203 }
204 205 // RunFunc evaluates a single package initializer at compile time.
206 // Set debug to true if it should print output while running.
207 func RunFunc(fn llvm.Value, timeout time.Duration, debug bool) error {
208 // Create and initialize *runner object.
209 mod := fn.GlobalParent()
210 r := newRunner(mod, timeout, debug)
211 defer r.dispose()
212 initName := fn.Name()
213 if !strings.HasSuffix(initName, ".init") {
214 return errorAt(fn, "interp: unexpected function name (expected *.init)")
215 }
216 r.pkgName = initName[:len(initName)-len(".init")]
217 218 // Create new function with the interp result.
219 newFn := llvm.AddFunction(mod, fn.Name()+".tmp", fn.GlobalValueType())
220 newFn.SetLinkage(fn.Linkage())
221 newFn.SetVisibility(fn.Visibility())
222 entry := mod.Context().AddBasicBlock(newFn, "entry")
223 224 // Create a builder, to insert instructions that could not be evaluated at
225 // compile time.
226 r.builder = mod.Context().NewBuilder()
227 defer r.builder.Dispose()
228 r.builder.SetInsertPointAtEnd(entry)
229 230 // Copy debug information.
231 subprogram := fn.Subprogram()
232 if !subprogram.IsNil() {
233 newFn.SetSubprogram(subprogram)
234 r.builder.SetCurrentDebugLocation(subprogram.SubprogramLine(), 0, subprogram, llvm.Metadata{})
235 }
236 237 // Run the initializer, filling the .init.tmp function.
238 if r.debug {
239 fmt.Fprintln(os.Stderr, "interp:", fn.Name())
240 }
241 _, pkgMem, callErr := r.run(r.getFunction(fn), nil, nil, " ")
242 if callErr != nil {
243 if isRecoverableError(callErr.Err) {
244 // Could not finish, but could recover from it.
245 if r.debug {
246 fmt.Fprintln(os.Stderr, "not interpreting", r.pkgName, "because of error:", callErr.Error())
247 }
248 newFn.EraseFromParentAsFunction()
249 return nil
250 }
251 return callErr
252 }
253 for index, obj := range pkgMem.objects {
254 r.objects[index] = obj
255 }
256 257 // Update globals with values determined while running the initializer above.
258 mem := memoryView{r: r}
259 for _, obj := range r.objects {
260 if obj.llvmGlobal.IsNil() {
261 continue
262 }
263 if obj.buffer == nil {
264 continue
265 }
266 if obj.constant {
267 continue // constant, so can't have been modified
268 }
269 initializer, err := obj.buffer.toLLVMValue(obj.llvmGlobal.GlobalValueType(), &mem)
270 if err != nil {
271 return err
272 }
273 if checks && initializer.Type() != obj.llvmGlobal.GlobalValueType() {
274 panic("initializer type mismatch")
275 }
276 obj.llvmGlobal.SetInitializer(initializer)
277 }
278 279 // Finalize: remove the old init function and replace it with the new
280 // (.init.tmp) function.
281 r.builder.CreateRetVoid()
282 fnName := fn.Name()
283 fn.ReplaceAllUsesWith(newFn)
284 fn.EraseFromParentAsFunction()
285 newFn.SetName(fnName)
286 287 return nil
288 }
289 290 // getFunction returns the compiled version of the given LLVM function. It
291 // compiles the function if necessary and caches the result.
292 func (r *runner) getFunction(llvmFn llvm.Value) *function {
293 if fn, ok := r.functionCache[llvmFn]; ok {
294 return fn
295 }
296 fn := r.compileFunction(llvmFn)
297 r.functionCache[llvmFn] = fn
298 return fn
299 }
300 301 // markExternalLoad marks the given llvmValue as being loaded externally. This
302 // is primarily used to mark package initializers that could not be run at
303 // compile time. As an example, a package initialize might store to a global
304 // variable. Another package initializer might read from the same global
305 // variable. By marking this function as being run at runtime, that load
306 // instruction will need to be run at runtime instead of at compile time.
307 func (r *runner) markExternalLoad(llvmValue llvm.Value) error {
308 mem := memoryView{r: r}
309 err := mem.markExternalLoad(llvmValue)
310 if err != nil {
311 return err
312 }
313 for index, obj := range mem.objects {
314 if obj.marked > r.objects[index].marked {
315 r.objects[index].marked = obj.marked
316 }
317 }
318 return nil
319 }
320