1 package interp
2 3 import (
4 "errors"
5 "fmt"
6 "math"
7 "os"
8 "strconv"
9 "strings"
10 "time"
11 12 "tinygo.org/x/go-llvm"
13 )
14 15 func (r *runner) run(fn *function, params []value, parentMem *memoryView, indent string) (value, memoryView, *Error) {
16 mem := memoryView{r: r, parent: parentMem}
17 locals := make([]value, len(fn.locals))
18 r.callsExecuted++
19 20 // Parameters are considered a kind of local values.
21 for i, param := range params {
22 locals[i] = param
23 }
24 25 // Track what blocks have run instructions at runtime.
26 // This is used to prevent unrolling.
27 var runtimeBlocks map[int]struct{}
28 29 // Start with the first basic block and the first instruction.
30 // Branch instructions may modify both bb and instIndex when branching.
31 bb := fn.blocks[0]
32 currentBB := 0
33 lastBB := -1 // last basic block is undefined, only defined after a branch
34 var operands []value
35 startRTInsts := len(mem.instructions)
36 for instIndex := 0; instIndex < len(bb.instructions); instIndex++ {
37 // Check timeout at every basic block entry to catch infinite loops.
38 if instIndex == 0 && time.Since(r.start) > r.timeout {
39 return nil, mem, r.errorAt(bb.instructions[0], errTimeout)
40 }
41 if instIndex == 0 {
42 // This is the start of a new basic block.
43 if len(mem.instructions) != startRTInsts {
44 if _, ok := runtimeBlocks[lastBB]; ok {
45 // This loop has been unrolled.
46 // Avoid doing this, as it can result in a large amount of extra machine code.
47 // This currently uses the branch from the last block, as there is no available information to give a better location.
48 lastBBInsts := fn.blocks[lastBB].instructions
49 return nil, mem, r.errorAt(lastBBInsts[len(lastBBInsts)-1], errLoopUnrolled)
50 }
51 52 // Flag the last block as having run stuff at runtime.
53 if runtimeBlocks == nil {
54 runtimeBlocks = make(map[int]struct{})
55 }
56 runtimeBlocks[lastBB] = struct{}{}
57 58 // Reset the block-start runtime instructions counter.
59 startRTInsts = len(mem.instructions)
60 }
61 62 // There may be PHI nodes that need to be resolved. Resolve all PHI
63 // nodes before continuing with regular instructions.
64 // PHI nodes need to be treated specially because they can have a
65 // mutual dependency:
66 // for.loop:
67 // %a = phi i8 [ 1, %entry ], [ %b, %for.loop ]
68 // %b = phi i8 [ 3, %entry ], [ %a, %for.loop ]
69 // If these PHI nodes are processed like a regular instruction, %a
70 // and %b are both 3 on the second iteration of the loop because %b
71 // loads the value of %a from the second iteration, while it should
72 // load the value from the previous iteration. The correct behavior
73 // is that these two values swap each others place on each
74 // iteration.
75 var phiValues []value
76 var phiIndices []int
77 for _, inst := range bb.phiNodes {
78 var result value
79 for i := 0; i < len(inst.operands); i += 2 {
80 if int(inst.operands[i].(literalValue).value.(uint32)) == lastBB {
81 incoming := inst.operands[i+1]
82 if local, ok := incoming.(localValue); ok {
83 result = locals[fn.locals[local.value]]
84 } else {
85 result = incoming
86 }
87 break
88 }
89 }
90 if r.debug {
91 fmt.Fprintln(os.Stderr, indent+"phi", inst.operands, "->", result)
92 }
93 if result == nil {
94 panic("could not find PHI input")
95 }
96 phiValues = append(phiValues, result)
97 phiIndices = append(phiIndices, inst.localIndex)
98 }
99 for i, value := range phiValues {
100 locals[phiIndices[i]] = value
101 }
102 }
103 104 inst := bb.instructions[instIndex]
105 operands = operands[:0]
106 isRuntimeInst := false
107 if inst.opcode != llvm.PHI {
108 for _, v := range inst.operands {
109 if v, ok := v.(localValue); ok {
110 index, ok := fn.locals[v.value]
111 if !ok {
112 // This is a localValue that is not local to the
113 // function. An example would be an inline assembly call
114 // operand.
115 isRuntimeInst = true
116 break
117 }
118 localVal := locals[index]
119 if localVal == nil {
120 // Trying to read a function-local value before it is
121 // set.
122 return nil, mem, r.errorAt(inst, errors.New("interp: local not defined"))
123 } else {
124 operands = append(operands, localVal)
125 if _, ok := localVal.(localValue); ok {
126 // The function-local value is still just a
127 // localValue (which can't be interpreted at compile
128 // time). Not sure whether this ever happens in
129 // practice.
130 isRuntimeInst = true
131 break
132 }
133 continue
134 }
135 }
136 operands = append(operands, v)
137 }
138 }
139 if isRuntimeInst {
140 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
141 if err != nil {
142 return nil, mem, err
143 }
144 continue
145 }
146 switch inst.opcode {
147 case llvm.Ret:
148 if time.Since(r.start) > r.timeout {
149 return nil, mem, r.errorAt(fn.blocks[0].instructions[0], errTimeout)
150 }
151 152 if len(operands) != 0 {
153 if r.debug {
154 fmt.Fprintln(os.Stderr, indent+"ret", operands[0])
155 }
156 // Return instruction has a value to return.
157 return operands[0], mem, nil
158 }
159 if r.debug {
160 fmt.Fprintln(os.Stderr, indent+"ret")
161 }
162 // Return instruction doesn't return anything, it's just 'ret void'.
163 return nil, mem, nil
164 case llvm.Br:
165 switch len(operands) {
166 case 1:
167 // Unconditional branch: [nextBB]
168 lastBB = currentBB
169 currentBB = int(operands[0].(literalValue).value.(uint32))
170 bb = fn.blocks[currentBB]
171 instIndex = -1 // start at 0 the next cycle
172 if r.debug {
173 fmt.Fprintln(os.Stderr, indent+"br", operands, "->", currentBB)
174 }
175 case 3:
176 // Conditional branch: [cond, thenBB, elseBB]
177 lastBB = currentBB
178 switch operands[0].Uint(r) {
179 case 1: // true -> thenBB
180 currentBB = int(operands[1].(literalValue).value.(uint32))
181 case 0: // false -> elseBB
182 currentBB = int(operands[2].(literalValue).value.(uint32))
183 default:
184 panic("bool should be 0 or 1")
185 }
186 if r.debug {
187 fmt.Fprintln(os.Stderr, indent+"br", operands, "->", currentBB)
188 }
189 bb = fn.blocks[currentBB]
190 instIndex = -1 // start at 0 the next cycle
191 default:
192 panic("unknown operands length")
193 }
194 case llvm.Switch:
195 // Switch statement: [value, defaultLabel, case0, label0, case1, label1, ...]
196 value := operands[0].Uint(r)
197 targetLabel := operands[1].Uint(r) // default label
198 // Do a lazy switch by iterating over all cases.
199 for i := 2; i < len(operands); i += 2 {
200 if value == operands[i].Uint(r) {
201 targetLabel = operands[i+1].Uint(r)
202 break
203 }
204 }
205 lastBB = currentBB
206 currentBB = int(targetLabel)
207 bb = fn.blocks[currentBB]
208 instIndex = -1 // start at 0 the next cycle
209 if r.debug {
210 fmt.Fprintln(os.Stderr, indent+"switch", operands, "->", currentBB)
211 }
212 case llvm.Select:
213 // Select is much like a ternary operator: it picks a result from
214 // the second and third operand based on the boolean first operand.
215 var result value
216 switch operands[0].Uint(r) {
217 case 1:
218 result = operands[1]
219 case 0:
220 result = operands[2]
221 default:
222 panic("boolean must be 0 or 1")
223 }
224 locals[inst.localIndex] = result
225 if r.debug {
226 fmt.Fprintln(os.Stderr, indent+"select", operands, "->", result)
227 }
228 case llvm.Call:
229 // A call instruction can either be a regular call or a runtime intrinsic.
230 fnPtr, err := operands[0].asPointer(r)
231 if err != nil {
232 return nil, mem, r.errorAt(inst, err)
233 }
234 callFn := r.getFunction(fnPtr.llvmValue(&mem))
235 switch {
236 case strings.HasPrefix(callFn.name, "runtime.print") || callFn.name == "runtime._panic" || callFn.name == "runtime.hashmapGet" || callFn.name == "runtime.hashmapInterfaceHash" ||
237 callFn.name == "os.runtime_args" || callFn.name == "internal/task.start" || callFn.name == "internal/task.Current" ||
238 callFn.name == "time.startTimer" || callFn.name == "time.stopTimer" || callFn.name == "time.resetTimer":
239 // These functions should be run at runtime. Specifically:
240 // * Print and panic functions are best emitted directly without
241 // interpreting them, otherwise we get a ton of putchar (etc.)
242 // calls.
243 // * runtime.hashmapGet tries to access the map value directly.
244 // This is not possible as the map value is treated as a special
245 // kind of object in this package.
246 // * os.runtime_args reads globals that are initialized outside
247 // the view of the interp package so it always needs to be run
248 // at runtime.
249 // * internal/task.start, internal/task.Current: start and read shcheduler state,
250 // which is modified elsewhere.
251 // * Timer functions access runtime internal state which may
252 // not be initialized.
253 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
254 if err != nil {
255 return nil, mem, err
256 }
257 case callFn.name == "internal/task.Pause":
258 // Task scheduling isn't possible at compile time.
259 return nil, mem, r.errorAt(inst, errUnsupportedRuntimeInst)
260 case callFn.name == "runtime.nanotime" && r.pkgName == "time":
261 // The time package contains a call to runtime.nanotime.
262 // This appears to be to work around a limitation in Windows
263 // Server 2008:
264 // > Monotonic times are reported as offsets from startNano.
265 // > We initialize startNano to runtimeNano() - 1 so that on systems where
266 // > monotonic time resolution is fairly low (e.g. Windows 2008
267 // > which appears to have a default resolution of 15ms),
268 // > we avoid ever reporting a monotonic time of 0.
269 // > (Callers may want to use 0 as "time not set".)
270 // Simply let runtime.nanotime return 0 in this case, which
271 // should be fine and avoids a call to runtime.nanotime. It
272 // means that monotonic time in the time package is counted from
273 // time.Time{}.Sub(1), which should be fine.
274 locals[inst.localIndex] = literalValue{uint64(0)}
275 case callFn.name == "runtime.alloc":
276 // Allocate heap memory. At compile time, this is instead done
277 // by creating a global variable.
278 279 // Get the requested memory size to be allocated.
280 size := operands[1].Uint(r)
281 282 // Get the object layout, if it is available.
283 llvmLayoutType := r.getLLVMTypeFromLayout(operands[2])
284 285 // Get the alignment of the memory to be allocated.
286 alignment := 0 // use default alignment if unset
287 alignAttr := inst.llvmInst.GetCallSiteEnumAttribute(0, llvm.AttributeKindID("align"))
288 if !alignAttr.IsNil() {
289 alignment = int(alignAttr.GetEnumValue())
290 }
291 292 // Create the object.
293 alloc := object{
294 globalName: r.pkgName + "$alloc",
295 align: alignment,
296 llvmLayoutType: llvmLayoutType,
297 buffer: newRawValue(uint32(size)),
298 size: uint32(size),
299 }
300 index := len(r.objects)
301 r.objects = append(r.objects, alloc)
302 303 // And create a pointer to this object, for working with it (so
304 // that stores to it copy it, etc).
305 ptr := newPointerValue(r, index, 0)
306 if r.debug {
307 fmt.Fprintln(os.Stderr, indent+"runtime.alloc:", size, "->", ptr)
308 }
309 locals[inst.localIndex] = ptr
310 case callFn.name == "runtime.sliceCopy":
311 // sliceCopy implements the built-in copy function for slices.
312 // It is implemented here so that it can be used even if the
313 // runtime implementation is not available. Doing it this way
314 // may also be faster.
315 // Code:
316 // func sliceCopy(dst, src unsafe.Pointer, dstLen, srcLen uintptr, elemSize uintptr) int {
317 // n := srcLen
318 // if n > dstLen {
319 // n = dstLen
320 // }
321 // memmove(dst, src, n*elemSize)
322 // return int(n)
323 // }
324 dstLen := operands[3].Uint(r)
325 srcLen := operands[4].Uint(r)
326 elemSize := operands[5].Uint(r)
327 n := srcLen
328 if n > dstLen {
329 n = dstLen
330 }
331 if r.debug {
332 fmt.Fprintln(os.Stderr, indent+"copy:", operands[1], operands[2], n)
333 }
334 if n != 0 {
335 // Only try to copy bytes when there are any bytes to copy.
336 // This is not just an optimization. If one of the slices
337 // (or both) are nil, the asPointer method call will fail
338 // even though copying a nil slice is allowed.
339 dst, err := operands[1].asPointer(r)
340 if err != nil {
341 return nil, mem, r.errorAt(inst, err)
342 }
343 src, err := operands[2].asPointer(r)
344 if err != nil {
345 return nil, mem, r.errorAt(inst, err)
346 }
347 if mem.hasExternalStore(src) || mem.hasExternalLoadOrStore(dst) {
348 // These are the same checks as there are on llvm.Load
349 // and llvm.Store in the interpreter. Copying is
350 // essentially loading from the source array and storing
351 // to the destination array, hence why we need to do the
352 // same checks here.
353 // This fixes the following bug:
354 // https://moxie/issues/3890
355 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
356 if err != nil {
357 return nil, mem, err
358 }
359 continue
360 }
361 nBytes := uint32(n * elemSize)
362 srcObj := mem.get(src.index())
363 dstObj := mem.getWritable(dst.index())
364 if srcObj.buffer == nil || dstObj.buffer == nil {
365 // If the buffer is nil, it means the slice is external.
366 // This can happen for example when copying data out of
367 // a //go:embed slice, which is not available at interp
368 // time.
369 // See: https://moxie/issues/4895
370 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
371 if err != nil {
372 return nil, mem, err
373 }
374 continue
375 }
376 dstBuf := dstObj.buffer.asRawValue(r)
377 srcBuf := srcObj.buffer.asRawValue(r)
378 copy(dstBuf.buf[dst.offset():dst.offset()+nBytes], srcBuf.buf[src.offset():])
379 dstObj.buffer = dstBuf
380 mem.put(dst.index(), dstObj)
381 }
382 locals[inst.localIndex] = makeLiteralInt(n, inst.llvmInst.Type().IntTypeWidth())
383 case strings.HasPrefix(callFn.name, "llvm.memcpy.p0") || strings.HasPrefix(callFn.name, "llvm.memmove.p0"):
384 // Copy a block of memory from one pointer to another.
385 dst, err := operands[1].asPointer(r)
386 if err != nil {
387 return nil, mem, r.errorAt(inst, err)
388 }
389 src, err := operands[2].asPointer(r)
390 if err != nil {
391 return nil, mem, r.errorAt(inst, err)
392 }
393 nBytes := uint32(operands[3].Uint(r))
394 dstObj := mem.getWritable(dst.index())
395 dstBuf := dstObj.buffer.asRawValue(r)
396 if mem.get(src.index()).buffer == nil {
397 // Looks like the source buffer is not defined.
398 // This can happen with //extern or //go:embed.
399 return nil, mem, r.errorAt(inst, errUnsupportedRuntimeInst)
400 }
401 srcBuf := mem.get(src.index()).buffer.asRawValue(r)
402 copy(dstBuf.buf[dst.offset():dst.offset()+nBytes], srcBuf.buf[src.offset():])
403 dstObj.buffer = dstBuf
404 mem.put(dst.index(), dstObj)
405 case callFn.name == "runtime.typeAssert":
406 // This function must be implemented manually as it is normally
407 // implemented by the interface lowering pass.
408 if r.debug {
409 fmt.Fprintln(os.Stderr, indent+"typeassert:", operands[1:])
410 }
411 assertedType, err := operands[2].toLLVMValue(inst.llvmInst.Operand(1).Type(), &mem)
412 if err != nil {
413 return nil, mem, r.errorAt(inst, err)
414 }
415 actualType, err := operands[1].toLLVMValue(inst.llvmInst.Operand(0).Type(), &mem)
416 if err != nil {
417 return nil, mem, r.errorAt(inst, err)
418 }
419 if !actualType.IsAConstantInt().IsNil() && actualType.ZExtValue() == 0 {
420 locals[inst.localIndex] = literalValue{uint8(0)}
421 break
422 }
423 // Strip pointer casts (bitcast, getelementptr).
424 for !actualType.IsAConstantExpr().IsNil() {
425 opcode := actualType.Opcode()
426 if opcode != llvm.GetElementPtr && opcode != llvm.BitCast {
427 break
428 }
429 actualType = actualType.Operand(0)
430 }
431 if strings.TrimPrefix(actualType.Name(), "reflect/types.type:") == strings.TrimPrefix(assertedType.Name(), "reflect/types.typeid:") {
432 locals[inst.localIndex] = literalValue{uint8(1)}
433 } else {
434 locals[inst.localIndex] = literalValue{uint8(0)}
435 }
436 case callFn.name == "__moxie_interp_raise_test_error":
437 // Special function that will trigger an error.
438 // This is used to test error reporting.
439 return nil, mem, r.errorAt(inst, errors.New("test error"))
440 case strings.HasSuffix(callFn.name, ".$typeassert"):
441 if r.debug {
442 fmt.Fprintln(os.Stderr, indent+"interface assert:", operands[1:])
443 }
444 445 // Load various values for the interface implements check below.
446 typecodePtr, err := operands[1].asPointer(r)
447 if err != nil {
448 return nil, mem, r.errorAt(inst, err)
449 }
450 // typecodePtr always point to the numMethod field in the type
451 // description struct. The methodSet, when present, comes right
452 // before the numMethod field (the compiler doesn't generate
453 // method sets for concrete types without methods).
454 // Considering that the compiler doesn't emit interface type
455 // asserts for interfaces with no methods (as the always succeed)
456 // then if the offset is zero, this assert must always fail.
457 if typecodePtr.offset() == 0 {
458 locals[inst.localIndex] = literalValue{uint8(0)}
459 break
460 }
461 typecodePtrOffset, err := typecodePtr.addOffset(-int64(r.pointerSize))
462 if err != nil {
463 return nil, mem, r.errorAt(inst, err)
464 }
465 methodSetPtr, err := mem.load(typecodePtrOffset, r.pointerSize).asPointer(r)
466 if err != nil {
467 return nil, mem, r.errorAt(inst, err)
468 }
469 methodSet := mem.get(methodSetPtr.index()).llvmGlobal.Initializer()
470 numMethods := int(r.builder.CreateExtractValue(methodSet, 0, "").ZExtValue())
471 llvmFn := inst.llvmInst.CalledValue()
472 methodSetAttr := llvmFn.GetStringAttributeAtIndex(-1, "moxie-methods")
473 methodSetString := methodSetAttr.GetStringValue()
474 475 // Make a set of all the methods on the concrete type, for
476 // easier checking in the next step.
477 concreteTypeMethods := map[string]struct{}{}
478 for i := 0; i < numMethods; i++ {
479 methodInfo := r.builder.CreateExtractValue(methodSet, 1, "")
480 name := r.builder.CreateExtractValue(methodInfo, i, "").Name()
481 concreteTypeMethods[name] = struct{}{}
482 }
483 484 // Check whether all interface methods are also in the list
485 // of defined methods calculated above. This is the interface
486 // assert itself.
487 assertOk := uint8(1) // i1 true
488 for _, name := range strings.Split(methodSetString, "; ") {
489 if _, ok := concreteTypeMethods[name]; !ok {
490 // There is a method on the interface that is not
491 // implemented by the type. The assertion will fail.
492 assertOk = 0 // i1 false
493 break
494 }
495 }
496 // If assertOk is still 1, the assertion succeeded.
497 locals[inst.localIndex] = literalValue{assertOk}
498 case strings.HasSuffix(callFn.name, "$invoke"):
499 // This thunk is the interface method dispatcher: it is called
500 // with all regular parameters and a type code. It will then
501 // call the concrete method for it.
502 if r.debug {
503 fmt.Fprintln(os.Stderr, indent+"invoke method:", operands[1:])
504 }
505 506 // Load the type code and method set of the interface value.
507 typecodePtr, err := operands[len(operands)-2].asPointer(r)
508 if err != nil {
509 return nil, mem, r.errorAt(inst, err)
510 }
511 typecodePtrOffset, err := typecodePtr.addOffset(-int64(r.pointerSize))
512 if err != nil {
513 return nil, mem, r.errorAt(inst, err)
514 }
515 methodSetPtr, err := mem.load(typecodePtrOffset, r.pointerSize).asPointer(r)
516 if err != nil {
517 return nil, mem, r.errorAt(inst, err)
518 }
519 methodSet := mem.get(methodSetPtr.index()).llvmGlobal.Initializer()
520 521 // We don't need to load the interface method set.
522 523 // Load the signature of the to-be-called function.
524 llvmFn := inst.llvmInst.CalledValue()
525 invokeAttr := llvmFn.GetStringAttributeAtIndex(-1, "moxie-invoke")
526 invokeName := invokeAttr.GetStringValue()
527 signature := r.mod.NamedGlobal(invokeName)
528 529 // Iterate through all methods, looking for the one method that
530 // should be returned.
531 numMethods := int(r.builder.CreateExtractValue(methodSet, 0, "").ZExtValue())
532 var method llvm.Value
533 for i := 0; i < numMethods; i++ {
534 methodSignatureAgg := r.builder.CreateExtractValue(methodSet, 1, "")
535 methodSignature := r.builder.CreateExtractValue(methodSignatureAgg, i, "")
536 if methodSignature == signature {
537 methodAgg := r.builder.CreateExtractValue(methodSet, 2, "")
538 method = r.builder.CreateExtractValue(methodAgg, i, "")
539 }
540 }
541 if method.IsNil() {
542 return nil, mem, r.errorAt(inst, errors.New("could not find method: "+invokeName))
543 }
544 545 // Change the to-be-called function to the underlying method to
546 // be called and fall through to the default case.
547 callFn = r.getFunction(method)
548 fallthrough
549 default:
550 if len(callFn.blocks) == 0 {
551 // Call to a function declaration without a definition
552 // available.
553 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
554 if err != nil {
555 return nil, mem, err
556 }
557 continue
558 }
559 // Call a function with a definition available. Run it as usual,
560 // possibly trying to recover from it if it failed to execute.
561 if r.debug {
562 argStrings := make([]string, len(operands)-1)
563 for i, v := range operands[1:] {
564 argStrings[i] = v.String()
565 }
566 fmt.Fprintln(os.Stderr, indent+"call:", callFn.name+"("+strings.Join(argStrings, ", ")+")")
567 }
568 retval, callMem, callErr := r.run(callFn, operands[1:], &mem, indent+" ")
569 if callErr != nil {
570 if isRecoverableError(callErr.Err) {
571 // This error can be recovered by doing the call at
572 // runtime instead of at compile time. But we need to
573 // revert any changes made by the call first.
574 if r.debug {
575 fmt.Fprintln(os.Stderr, indent+"!! revert because of error:", callErr.Error())
576 }
577 callMem.revert()
578 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
579 if err != nil {
580 return nil, mem, err
581 }
582 continue
583 }
584 // Add to the traceback, so that error handling code can see
585 // how this function got called.
586 callErr.Traceback = append(callErr.Traceback, ErrorLine{
587 Pos: getPosition(inst.llvmInst),
588 Inst: inst.llvmInst.String(),
589 })
590 return nil, mem, callErr
591 }
592 locals[inst.localIndex] = retval
593 mem.extend(callMem)
594 }
595 case llvm.Load:
596 // Load instruction, loading some data from the topmost memory view.
597 ptr, err := operands[0].asPointer(r)
598 if err != nil {
599 return nil, mem, r.errorAt(inst, err)
600 }
601 size := operands[1].(literalValue).value.(uint64)
602 if inst.llvmInst.IsVolatile() || inst.llvmInst.Ordering() != llvm.AtomicOrderingNotAtomic || mem.hasExternalStore(ptr) {
603 // If there could be an external store (for example, because a
604 // pointer to the object was passed to a function that could not
605 // be interpreted at compile time) then the load must be done at
606 // runtime.
607 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
608 if err != nil {
609 return nil, mem, err
610 }
611 continue
612 }
613 result := mem.load(ptr, uint32(size))
614 if result == nil {
615 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
616 if err != nil {
617 return nil, mem, err
618 }
619 continue
620 }
621 if r.debug {
622 fmt.Fprintln(os.Stderr, indent+"load:", ptr, "->", result)
623 }
624 locals[inst.localIndex] = result
625 case llvm.Store:
626 // Store instruction. Create a new object in the memory view and
627 // store to that, to make it possible to roll back this store.
628 ptr, err := operands[1].asPointer(r)
629 if err != nil {
630 return nil, mem, r.errorAt(inst, err)
631 }
632 if inst.llvmInst.IsVolatile() || inst.llvmInst.Ordering() != llvm.AtomicOrderingNotAtomic || mem.hasExternalLoadOrStore(ptr) {
633 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
634 if err != nil {
635 return nil, mem, err
636 }
637 continue
638 }
639 val := operands[0]
640 if r.debug {
641 fmt.Fprintln(os.Stderr, indent+"store:", val, ptr)
642 }
643 ok := mem.store(val, ptr)
644 if !ok {
645 // Could not store the value, do it at runtime.
646 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
647 if err != nil {
648 return nil, mem, err
649 }
650 }
651 case llvm.Alloca:
652 // Alloca normally allocates some stack memory. In the interpreter,
653 // it allocates a global instead.
654 // This can likely be optimized, as all it really needs is an alloca
655 // in the initAll function and creating a global is wasteful for
656 // this purpose.
657 658 // Create the new object.
659 size := operands[0].(literalValue).value.(uint64)
660 alloca := object{
661 llvmType: inst.llvmInst.AllocatedType(),
662 globalName: r.pkgName + "$alloca",
663 buffer: newRawValue(uint32(size)),
664 size: uint32(size),
665 align: inst.llvmInst.Alignment(),
666 }
667 index := len(r.objects)
668 r.objects = append(r.objects, alloca)
669 670 // Create a pointer to this object (an alloca produces a pointer).
671 ptr := newPointerValue(r, index, 0)
672 if r.debug {
673 fmt.Fprintln(os.Stderr, indent+"alloca:", operands, "->", ptr)
674 }
675 locals[inst.localIndex] = ptr
676 case llvm.GetElementPtr:
677 // GetElementPtr does pointer arithmetic, changing the offset of the
678 // pointer into the underlying object.
679 var offset int64
680 for i := 1; i < len(operands); i += 2 {
681 index := operands[i].Int(r)
682 elementSize := operands[i+1].Int(r)
683 if elementSize < 0 {
684 // This is a struct field.
685 offset += index
686 } else {
687 // This is a normal GEP, probably an array index.
688 offset += elementSize * index
689 }
690 }
691 ptr, err := operands[0].asPointer(r)
692 if err != nil {
693 if err != errIntegerAsPointer {
694 return nil, mem, r.errorAt(inst, err)
695 }
696 // GEP on fixed pointer value (for example, memory-mapped I/O).
697 ptrValue := operands[0].Uint(r) + uint64(offset)
698 locals[inst.localIndex] = makeLiteralInt(ptrValue, int(operands[0].len(r)*8))
699 continue
700 }
701 ptr, err = ptr.addOffset(int64(offset))
702 if err != nil {
703 return nil, mem, r.errorAt(inst, err)
704 }
705 locals[inst.localIndex] = ptr
706 if r.debug {
707 fmt.Fprintln(os.Stderr, indent+"gep:", operands, "->", ptr)
708 }
709 case llvm.BitCast, llvm.IntToPtr, llvm.PtrToInt:
710 // Various bitcast-like instructions that all keep the same bits
711 // while changing the LLVM type.
712 // Because interp doesn't preserve the type, these operations are
713 // identity operations.
714 if r.debug {
715 fmt.Fprintln(os.Stderr, indent+instructionNameMap[inst.opcode]+":", operands[0])
716 }
717 locals[inst.localIndex] = operands[0]
718 case llvm.ExtractValue:
719 agg := operands[0].asRawValue(r)
720 offset := operands[1].(literalValue).value.(uint64)
721 size := operands[2].(literalValue).value.(uint64)
722 elt := rawValue{
723 buf: agg.buf[offset : offset+size],
724 }
725 if r.debug {
726 fmt.Fprintln(os.Stderr, indent+"extractvalue:", operands, "->", elt)
727 }
728 locals[inst.localIndex] = elt
729 case llvm.InsertValue:
730 agg := operands[0].asRawValue(r)
731 elt := operands[1].asRawValue(r)
732 offset := int(operands[2].(literalValue).value.(uint64))
733 newagg := newRawValue(uint32(len(agg.buf)))
734 copy(newagg.buf, agg.buf)
735 copy(newagg.buf[offset:], elt.buf)
736 if r.debug {
737 fmt.Fprintln(os.Stderr, indent+"insertvalue:", operands, "->", newagg)
738 }
739 locals[inst.localIndex] = newagg
740 case llvm.ICmp:
741 predicate := llvm.IntPredicate(operands[2].(literalValue).value.(uint8))
742 lhs := operands[0]
743 rhs := operands[1]
744 result, icmpErr := r.interpretICmp(lhs, rhs, predicate)
745 if icmpErr != nil {
746 return nil, mem, r.errorAt(inst, icmpErr)
747 }
748 if result {
749 locals[inst.localIndex] = literalValue{uint8(1)}
750 } else {
751 locals[inst.localIndex] = literalValue{uint8(0)}
752 }
753 if r.debug {
754 fmt.Fprintln(os.Stderr, indent+"icmp:", operands[0], intPredicateString(predicate), operands[1], "->", result)
755 }
756 case llvm.FCmp:
757 predicate := llvm.FloatPredicate(operands[2].(literalValue).value.(uint8))
758 var result bool
759 var lhs, rhs float64
760 switch operands[0].len(r) {
761 case 8:
762 lhs = math.Float64frombits(operands[0].Uint(r))
763 rhs = math.Float64frombits(operands[1].Uint(r))
764 case 4:
765 lhs = float64(math.Float32frombits(uint32(operands[0].Uint(r))))
766 rhs = float64(math.Float32frombits(uint32(operands[1].Uint(r))))
767 default:
768 panic("unknown float type")
769 }
770 switch predicate {
771 case llvm.FloatOEQ:
772 result = lhs == rhs
773 case llvm.FloatUNE:
774 result = lhs != rhs
775 case llvm.FloatOGT:
776 result = lhs > rhs
777 case llvm.FloatOGE:
778 result = lhs >= rhs
779 case llvm.FloatOLT:
780 result = lhs < rhs
781 case llvm.FloatOLE:
782 result = lhs <= rhs
783 default:
784 return nil, mem, r.errorAt(inst, errors.New("interp: unsupported fcmp"))
785 }
786 if result {
787 locals[inst.localIndex] = literalValue{uint8(1)}
788 } else {
789 locals[inst.localIndex] = literalValue{uint8(0)}
790 }
791 if r.debug {
792 fmt.Fprintln(os.Stderr, indent+"fcmp:", operands[0], predicate, operands[1], "->", result)
793 }
794 case llvm.Add, llvm.Sub, llvm.Mul, llvm.UDiv, llvm.SDiv, llvm.URem, llvm.SRem, llvm.Shl, llvm.LShr, llvm.AShr, llvm.And, llvm.Or, llvm.Xor:
795 // Integer binary operations.
796 lhs := operands[0]
797 rhs := operands[1]
798 lhsPtr, err := lhs.asPointer(r)
799 if err == nil {
800 // The lhs is a pointer. This sometimes happens for particular
801 // pointer tricks.
802 if inst.opcode == llvm.Add {
803 // This likely means this is part of a
804 // unsafe.Pointer(uintptr(ptr) + offset) pattern.
805 lhsPtr, err = lhsPtr.addOffset(int64(rhs.Uint(r)))
806 if err != nil {
807 return nil, mem, r.errorAt(inst, err)
808 }
809 locals[inst.localIndex] = lhsPtr
810 } else if inst.opcode == llvm.Xor && rhs.Uint(r) == 0 {
811 // Special workaround for strings.noescape, see
812 // src/strings/builder.go in the Go source tree. This is
813 // the identity operator, so we can return the input.
814 locals[inst.localIndex] = lhs
815 } else if inst.opcode == llvm.And && rhs.Uint(r) < 8 {
816 // This is probably part of a pattern to get the lower bits
817 // of a pointer for pointer tagging, like this:
818 // uintptr(unsafe.Pointer(t)) & 0b11
819 // We can actually support this easily by ANDing with the
820 // pointer offset.
821 result := uint64(lhsPtr.offset()) & rhs.Uint(r)
822 locals[inst.localIndex] = makeLiteralInt(result, int(lhs.len(r)*8))
823 } else {
824 // Catch-all for weird operations that should just be done
825 // at runtime.
826 err := r.runAtRuntime(fn, inst, locals, &mem, indent)
827 if err != nil {
828 return nil, mem, err
829 }
830 }
831 continue
832 }
833 var result uint64
834 switch inst.opcode {
835 case llvm.Add:
836 result = lhs.Uint(r) + rhs.Uint(r)
837 case llvm.Sub:
838 result = lhs.Uint(r) - rhs.Uint(r)
839 case llvm.Mul:
840 result = lhs.Uint(r) * rhs.Uint(r)
841 case llvm.UDiv:
842 result = lhs.Uint(r) / rhs.Uint(r)
843 case llvm.SDiv:
844 result = uint64(lhs.Int(r) / rhs.Int(r))
845 case llvm.URem:
846 result = lhs.Uint(r) % rhs.Uint(r)
847 case llvm.SRem:
848 result = uint64(lhs.Int(r) % rhs.Int(r))
849 case llvm.Shl:
850 result = lhs.Uint(r) << rhs.Uint(r)
851 case llvm.LShr:
852 result = lhs.Uint(r) >> rhs.Uint(r)
853 case llvm.AShr:
854 result = uint64(lhs.Int(r) >> rhs.Uint(r))
855 case llvm.And:
856 result = lhs.Uint(r) & rhs.Uint(r)
857 case llvm.Or:
858 result = lhs.Uint(r) | rhs.Uint(r)
859 case llvm.Xor:
860 result = lhs.Uint(r) ^ rhs.Uint(r)
861 default:
862 panic("unreachable")
863 }
864 locals[inst.localIndex] = makeLiteralInt(result, int(lhs.len(r)*8))
865 if r.debug {
866 fmt.Fprintln(os.Stderr, indent+instructionNameMap[inst.opcode]+":", lhs, rhs, "->", result)
867 }
868 case llvm.SExt, llvm.ZExt, llvm.Trunc:
869 // Change the size of an integer to a larger or smaller bit width.
870 // We make use of the fact that the Uint() function already
871 // zero-extends the value and that Int() already sign-extends the
872 // value, so we only need to truncate it to the appropriate bit
873 // width. This means we can implement sext, zext and trunc in the
874 // same way, by first {zero,sign}extending all the way up to uint64
875 // and then truncating it as necessary.
876 var value uint64
877 if inst.opcode == llvm.SExt {
878 value = uint64(operands[0].Int(r))
879 } else {
880 value = operands[0].Uint(r)
881 }
882 bitwidth := operands[1].Uint(r)
883 if r.debug {
884 fmt.Fprintln(os.Stderr, indent+instructionNameMap[inst.opcode]+":", value, bitwidth)
885 }
886 locals[inst.localIndex] = makeLiteralInt(value, int(bitwidth))
887 case llvm.SIToFP, llvm.UIToFP:
888 var value float64
889 switch inst.opcode {
890 case llvm.SIToFP:
891 value = float64(operands[0].Int(r))
892 case llvm.UIToFP:
893 value = float64(operands[0].Uint(r))
894 }
895 bitwidth := operands[1].Uint(r)
896 if r.debug {
897 fmt.Fprintln(os.Stderr, indent+instructionNameMap[inst.opcode]+":", value, bitwidth)
898 }
899 switch bitwidth {
900 case 64:
901 locals[inst.localIndex] = literalValue{math.Float64bits(value)}
902 case 32:
903 locals[inst.localIndex] = literalValue{math.Float32bits(float32(value))}
904 default:
905 panic("unknown integer size in sitofp/uitofp")
906 }
907 default:
908 if r.debug {
909 fmt.Fprintln(os.Stderr, indent+inst.String())
910 }
911 return nil, mem, r.errorAt(inst, errUnsupportedInst)
912 }
913 }
914 return nil, mem, r.errorAt(bb.instructions[len(bb.instructions)-1], errors.New("interp: reached end of basic block without terminator"))
915 }
916 917 // Interpret an icmp instruction. Doesn't have side effects, only returns the
918 // output of the comparison. Returns an error when the comparison involves
919 // pointer values in ordering predicates (ULT, SGT, etc.) that the interp
920 // cannot evaluate symbolically.
921 func (r *runner) interpretICmp(lhs, rhs value, predicate llvm.IntPredicate) (bool, error) {
922 switch predicate {
923 case llvm.IntEQ, llvm.IntNE:
924 var result bool
925 lhsPointer, lhsErr := lhs.asPointer(r)
926 rhsPointer, rhsErr := rhs.asPointer(r)
927 if (lhsErr == nil) != (rhsErr == nil) {
928 // Fast path: only one is a pointer, so they can't be equal.
929 result = false
930 } else if lhsErr == nil {
931 // Both must be nil, so both are pointers.
932 // Compare them directly.
933 result = lhsPointer.equal(rhsPointer)
934 } else {
935 // Fall back to generic comparison.
936 result = lhs.asRawValue(r).equal(rhs.asRawValue(r))
937 }
938 if predicate == llvm.IntNE {
939 result = !result
940 }
941 return result, nil
942 case llvm.IntUGT:
943 return r.safeUintCmp(lhs, rhs, func(a, b uint64) bool { return a > b })
944 case llvm.IntUGE:
945 return r.safeUintCmp(lhs, rhs, func(a, b uint64) bool { return a >= b })
946 case llvm.IntULT:
947 return r.safeUintCmp(lhs, rhs, func(a, b uint64) bool { return a < b })
948 case llvm.IntULE:
949 return r.safeUintCmp(lhs, rhs, func(a, b uint64) bool { return a <= b })
950 case llvm.IntSGT:
951 return r.safeIntCmp(lhs, rhs, func(a, b int64) bool { return a > b })
952 case llvm.IntSGE:
953 return r.safeIntCmp(lhs, rhs, func(a, b int64) bool { return a >= b })
954 case llvm.IntSLT:
955 return r.safeIntCmp(lhs, rhs, func(a, b int64) bool { return a < b })
956 case llvm.IntSLE:
957 return r.safeIntCmp(lhs, rhs, func(a, b int64) bool { return a <= b })
958 default:
959 return false, errUnsupportedInst
960 }
961 }
962 963 // safeUintCmp compares two values as unsigned integers, returning an error
964 // if either is a pointer that cannot be converted to an integer.
965 func (r *runner) safeUintCmp(lhs, rhs value, cmp func(uint64, uint64) bool) (bool, error) {
966 lv, lok := r.tryUint(lhs)
967 rv, rok := r.tryUint(rhs)
968 if !lok || !rok {
969 return false, errUnsupportedInst
970 }
971 return cmp(lv, rv), nil
972 }
973 974 // safeIntCmp compares two values as signed integers, returning an error
975 // if either is a pointer that cannot be converted to an integer.
976 func (r *runner) safeIntCmp(lhs, rhs value, cmp func(int64, int64) bool) (bool, error) {
977 lv, lok := r.tryInt(lhs)
978 rv, rok := r.tryInt(rhs)
979 if !lok || !rok {
980 return false, errUnsupportedInst
981 }
982 return cmp(lv, rv), nil
983 }
984 985 // tryUint attempts to extract a uint64 from a value, returning false
986 // if the value is a pointer that cannot be converted.
987 func (r *runner) tryUint(v value) (uint64, bool) {
988 if _, err := v.asPointer(r); err == nil {
989 return 0, false // is a pointer, can't convert
990 }
991 return v.Uint(r), true
992 }
993 994 // tryInt attempts to extract an int64 from a value, returning false
995 // if the value is a pointer that cannot be converted.
996 func (r *runner) tryInt(v value) (int64, bool) {
997 if _, err := v.asPointer(r); err == nil {
998 return 0, false // is a pointer, can't convert
999 }
1000 return v.Int(r), true
1001 }
1002 1003 func (r *runner) runAtRuntime(fn *function, inst instruction, locals []value, mem *memoryView, indent string) *Error {
1004 numOperands := inst.llvmInst.OperandsCount()
1005 operands := make([]llvm.Value, numOperands)
1006 for i := 0; i < numOperands; i++ {
1007 operand := inst.llvmInst.Operand(i)
1008 if !operand.IsAInstruction().IsNil() || !operand.IsAArgument().IsNil() {
1009 var err error
1010 operand, err = locals[fn.locals[operand]].toLLVMValue(operand.Type(), mem)
1011 if err != nil {
1012 return r.errorAt(inst, err)
1013 }
1014 }
1015 operands[i] = operand
1016 }
1017 if r.debug {
1018 fmt.Fprintln(os.Stderr, indent+inst.String())
1019 }
1020 var result llvm.Value
1021 switch inst.opcode {
1022 case llvm.Call:
1023 llvmFn := operands[len(operands)-1]
1024 args := operands[:len(operands)-1]
1025 for _, op := range operands {
1026 if op.Type().TypeKind() == llvm.PointerTypeKind {
1027 err := mem.markExternalStore(op)
1028 if err != nil {
1029 return r.errorAt(inst, err)
1030 }
1031 }
1032 }
1033 result = r.builder.CreateCall(inst.llvmInst.CalledFunctionType(), llvmFn, args, inst.name)
1034 case llvm.Load:
1035 err := mem.markExternalLoad(operands[0])
1036 if err != nil {
1037 return r.errorAt(inst, err)
1038 }
1039 result = r.builder.CreateLoad(inst.llvmInst.Type(), operands[0], inst.name)
1040 if inst.llvmInst.IsVolatile() {
1041 result.SetVolatile(true)
1042 }
1043 if ordering := inst.llvmInst.Ordering(); ordering != llvm.AtomicOrderingNotAtomic {
1044 result.SetOrdering(ordering)
1045 }
1046 case llvm.Store:
1047 err := mem.markExternalStore(operands[1])
1048 if err != nil {
1049 return r.errorAt(inst, err)
1050 }
1051 result = r.builder.CreateStore(operands[0], operands[1])
1052 if inst.llvmInst.IsVolatile() {
1053 result.SetVolatile(true)
1054 }
1055 if ordering := inst.llvmInst.Ordering(); ordering != llvm.AtomicOrderingNotAtomic {
1056 result.SetOrdering(ordering)
1057 }
1058 case llvm.BitCast:
1059 result = r.builder.CreateBitCast(operands[0], inst.llvmInst.Type(), inst.name)
1060 case llvm.ExtractValue:
1061 indices := inst.llvmInst.Indices()
1062 // Note: the Go LLVM API doesn't support multiple indices, so simulate
1063 // this operation with some extra extractvalue instructions. Hopefully
1064 // this is optimized to a single instruction.
1065 agg := operands[0]
1066 for i := 0; i < len(indices)-1; i++ {
1067 agg = r.builder.CreateExtractValue(agg, int(indices[i]), inst.name+".agg")
1068 mem.instructions = append(mem.instructions, agg)
1069 }
1070 result = r.builder.CreateExtractValue(agg, int(indices[len(indices)-1]), inst.name)
1071 case llvm.InsertValue:
1072 indices := inst.llvmInst.Indices()
1073 // Similar to extractvalue, we're working around a limitation in the Go
1074 // LLVM API here by splitting the insertvalue into multiple instructions
1075 // if there is more than one operand.
1076 agg := operands[0]
1077 aggregates := []llvm.Value{agg}
1078 for i := 0; i < len(indices)-1; i++ {
1079 agg = r.builder.CreateExtractValue(agg, int(indices[i]), inst.name+".agg"+strconv.Itoa(i))
1080 aggregates = append(aggregates, agg)
1081 mem.instructions = append(mem.instructions, agg)
1082 }
1083 result = operands[1]
1084 for i := len(indices) - 1; i >= 0; i-- {
1085 agg := aggregates[i]
1086 result = r.builder.CreateInsertValue(agg, result, int(indices[i]), inst.name+".insertvalue"+strconv.Itoa(i))
1087 if i != 0 { // don't add last result to mem.instructions as it will be done at the end already
1088 mem.instructions = append(mem.instructions, result)
1089 }
1090 }
1091 1092 case llvm.Add:
1093 result = r.builder.CreateAdd(operands[0], operands[1], inst.name)
1094 case llvm.Sub:
1095 result = r.builder.CreateSub(operands[0], operands[1], inst.name)
1096 case llvm.Mul:
1097 result = r.builder.CreateMul(operands[0], operands[1], inst.name)
1098 case llvm.UDiv:
1099 result = r.builder.CreateUDiv(operands[0], operands[1], inst.name)
1100 case llvm.SDiv:
1101 result = r.builder.CreateSDiv(operands[0], operands[1], inst.name)
1102 case llvm.URem:
1103 result = r.builder.CreateURem(operands[0], operands[1], inst.name)
1104 case llvm.SRem:
1105 result = r.builder.CreateSRem(operands[0], operands[1], inst.name)
1106 case llvm.ZExt:
1107 result = r.builder.CreateZExt(operands[0], inst.llvmInst.Type(), inst.name)
1108 default:
1109 return r.errorAt(inst, errUnsupportedRuntimeInst)
1110 }
1111 locals[inst.localIndex] = localValue{result}
1112 mem.instructions = append(mem.instructions, result)
1113 return nil
1114 }
1115 1116 func intPredicateString(predicate llvm.IntPredicate) string {
1117 switch predicate {
1118 case llvm.IntEQ:
1119 return "eq"
1120 case llvm.IntNE:
1121 return "ne"
1122 case llvm.IntUGT:
1123 return "ugt"
1124 case llvm.IntUGE:
1125 return "uge"
1126 case llvm.IntULT:
1127 return "ult"
1128 case llvm.IntULE:
1129 return "ule"
1130 case llvm.IntSGT:
1131 return "sgt"
1132 case llvm.IntSGE:
1133 return "sge"
1134 case llvm.IntSLT:
1135 return "slt"
1136 case llvm.IntSLE:
1137 return "sle"
1138 default:
1139 return "cmp?"
1140 }
1141 }
1142