interp: implement runtime.sliceCopy

This implements the copy() built-in function. It may not work in all
cases, but should work in most cases.

This commit gets the following 3 packages to compile, according to
tinygo-site/imports/main.go:

  * encoding/base32
  * encoding/base64
  * encoding/pem (was blocked by encoding/base64)

6 files changed, 179 insertions, 7 deletions

diff --git a/interp/frame.go b/interp/frame.go
index 47c59f57e..adb19cce3 100644
--- a/interp/frame.go
+++ b/interp/frame.go
@@ -316,6 +316,49 @@ func (fr *frame) evalBasicBlock(bb, incoming llvm.BasicBlock, indent string) (re
 				ret = llvm.ConstInsertValue(ret, retPtr, []uint32{0})
 				ret = llvm.ConstInsertValue(ret, retLen, []uint32{1})
 				fr.locals[inst] = &LocalValue{fr.Eval, ret}
+			case callee.Name() == "runtime.sliceCopy":
+				elementSize := fr.getLocal(inst.Operand(4)).(*LocalValue).Value().ZExtValue()
+				dstArray := fr.getLocal(inst.Operand(0)).(*LocalValue).stripPointerCasts()
+				srcArray := fr.getLocal(inst.Operand(1)).(*LocalValue).stripPointerCasts()
+				dstLen := fr.getLocal(inst.Operand(2)).(*LocalValue)
+				srcLen := fr.getLocal(inst.Operand(3)).(*LocalValue)
+				if elementSize != 1 && dstArray.Type().ElementType().TypeKind() == llvm.ArrayTypeKind && srcArray.Type().ElementType().TypeKind() == llvm.ArrayTypeKind {
+					// Slice data pointers are created by adding a global array
+					// and getting the address of the first element using a GEP.
+					// However, before the compiler can pass it to
+					// runtime.sliceCopy, it has to perform a bitcast to a *i8,
+					// to make it a unsafe.Pointer. Now, when the IR builder
+					// sees a bitcast of a GEP with zero indices, it will make
+					// a bitcast of the original array instead of the GEP,
+					// which breaks our assumptions.
+					// Re-add this GEP, in the hope that it it is then of the correct type...
+					dstArray = dstArray.GetElementPtr([]uint32{0, 0}).(*LocalValue)
+					srcArray = srcArray.GetElementPtr([]uint32{0, 0}).(*LocalValue)
+				}
+				if fr.Eval.TargetData.TypeAllocSize(dstArray.Type().ElementType()) != elementSize {
+					return nil, nil, errors.New("interp: slice dst element size does not match pointer type")
+				}
+				if fr.Eval.TargetData.TypeAllocSize(srcArray.Type().ElementType()) != elementSize {
+					return nil, nil, errors.New("interp: slice src element size does not match pointer type")
+				}
+				if dstArray.Type() != srcArray.Type() {
+					return nil, nil, errors.New("interp: slice element types don't match")
+				}
+				length := dstLen.Value().SExtValue()
+				if srcLength := srcLen.Value().SExtValue(); srcLength < length {
+					length = srcLength
+				}
+				if length < 0 {
+					return nil, nil, errors.New("interp: trying to copy a slice with negative length?")
+				}
+				for i := int64(0); i < length; i++ {
+					// *dst = *src
+					dstArray.Store(srcArray.Load())
+					// dst++
+					dstArray = dstArray.GetElementPtr([]uint32{1}).(*LocalValue)
+					// src++
+					srcArray = srcArray.GetElementPtr([]uint32{1}).(*LocalValue)
+				}
 			case callee.Name() == "runtime.stringToBytes":
 				// convert a string to a []byte
 				bufPtr := fr.getLocal(inst.Operand(0))
diff --git a/interp/interp_test.go b/interp/interp_test.go
index b9f37e1ba..9e3808540 100644
--- a/interp/interp_test.go
+++ b/interp/interp_test.go
@@ -12,6 +12,7 @@ import (
 func TestInterp(t *testing.T) {
 	for _, name := range []string{
 		"basic",
+		"slice-copy",
 	} {
 		name := name // make tc local to this closure
 		t.Run(name, func(t *testing.T) {
diff --git a/interp/scan.go b/interp/scan.go
index 1d95bcff2..9b77c0911 100644
--- a/interp/scan.go
+++ b/interp/scan.go
@@ -35,6 +35,8 @@ func (e *Eval) hasSideEffects(fn llvm.Value) *sideEffectResult {
 		return &sideEffectResult{severity: sideEffectLimited}
 	case "runtime.interfaceImplements":
 		return &sideEffectResult{severity: sideEffectNone}
+	case "runtime.sliceCopy":
+		return &sideEffectResult{severity: sideEffectNone}
 	case "runtime.trackPointer":
 		return &sideEffectResult{severity: sideEffectNone}
 	case "llvm.dbg.value":
diff --git a/interp/testdata/slice-copy.ll b/interp/testdata/slice-copy.ll
new file mode 100644
index 000000000..ae5cda6c4
--- /dev/null
+++ b/interp/testdata/slice-copy.ll
@@ -0,0 +1,86 @@
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64--linux"
+
[email protected] = internal global [2 x i8] c"\03d"
[email protected] = internal unnamed_addr global { i8*, i64, i64 } { i8* getelementptr inbounds ([2 x i8], [2 x i8]* @main.uint8SliceSrc.buf, i32 0, i32 0), i64 2, i64 2 }
[email protected] = internal unnamed_addr global { i8*, i64, i64 } zeroinitializer
[email protected] = internal global [3 x i16] [i16 5, i16 123, i16 1024]
[email protected] = internal unnamed_addr global { i16*, i64, i64 } { i16* getelementptr inbounds ([3 x i16], [3 x i16]* @main.int16SliceSrc.buf, i32 0, i32 0), i64 3, i64 3 }
[email protected] = internal unnamed_addr global { i16*, i64, i64 } zeroinitializer
+
+declare i64 @runtime.sliceCopy(i8* %dst, i8* %src, i64 %dstLen, i64 %srcLen, i64 %elemSize) unnamed_addr
+
+declare i8* @runtime.alloc(i64) unnamed_addr
+
+declare void @runtime.printuint8(i8)
+
+declare void @runtime.printint16(i16)
+
+define void @runtime.initAll() unnamed_addr {
+entry:
+  call void @main.init()
+  ret void
+}
+
+define void @main() unnamed_addr {
+entry:
+  ; print(uintSliceSrc[0])
+  %uint8SliceSrc.buf = load i8*, i8** getelementptr inbounds ({ i8*, i64, i64 }, { i8*, i64, i64 }* @main.uint8SliceSrc, i64 0, i32 0)
+  %uint8SliceSrc.val = load i8, i8* %uint8SliceSrc.buf
+  call void @runtime.printuint8(i8 %uint8SliceSrc.val)
+
+  ; print(uintSliceDst[0])
+  %uint8SliceDst.buf = load i8*, i8** getelementptr inbounds ({ i8*, i64, i64 }, { i8*, i64, i64 }* @main.uint8SliceDst, i64 0, i32 0)
+  %uint8SliceDst.val = load i8, i8* %uint8SliceDst.buf
+  call void @runtime.printuint8(i8 %uint8SliceDst.val)
+
+  ; print(int16SliceSrc[0])
+  %int16SliceSrc.buf = load i16*, i16** getelementptr inbounds ({ i16*, i64, i64 }, { i16*, i64, i64 }* @main.int16SliceSrc, i64 0, i32 0)
+  %int16SliceSrc.val = load i16, i16* %int16SliceSrc.buf
+  call void @runtime.printint16(i16 %int16SliceSrc.val)
+
+  ; print(int16SliceDst[0])
+  %int16SliceDst.buf = load i16*, i16** getelementptr inbounds ({ i16*, i64, i64 }, { i16*, i64, i64 }* @main.int16SliceDst, i64 0, i32 0)
+  %int16SliceDst.val = load i16, i16* %int16SliceDst.buf
+  call void @runtime.printint16(i16 %int16SliceDst.val)
+  ret void
+}
+
+define internal void @main.init() unnamed_addr {
+entry:
+  ; equivalent of:
+  ;     uint8SliceDst = make([]uint8, len(uint8SliceSrc))
+  %uint8SliceSrc = load { i8*, i64, i64 }, { i8*, i64, i64 }* @main.uint8SliceSrc
+  %uint8SliceSrc.len = extractvalue { i8*, i64, i64 } %uint8SliceSrc, 1
+  %uint8SliceDst.buf = call i8* @runtime.alloc(i64 %uint8SliceSrc.len)
+  %0 = insertvalue { i8*, i64, i64 } undef, i8* %uint8SliceDst.buf, 0
+  %1 = insertvalue { i8*, i64, i64 } %0, i64 %uint8SliceSrc.len, 1
+  %2 = insertvalue { i8*, i64, i64 } %1, i64 %uint8SliceSrc.len, 2
+  store { i8*, i64, i64 } %2, { i8*, i64, i64 }* @main.uint8SliceDst
+
+  ; equivalent of:
+  ;     copy(uint8SliceDst, uint8SliceSrc)
+  %uint8SliceSrc.buf = extractvalue { i8*, i64, i64 } %uint8SliceSrc, 0
+  %copy.n = call i64 @runtime.sliceCopy(i8* %uint8SliceDst.buf, i8* %uint8SliceSrc.buf, i64 %uint8SliceSrc.len, i64 %uint8SliceSrc.len, i64 1)
+
+  ; equivalent of:
+  ;     int16SliceDst = make([]int16, len(int16SliceSrc))
+  %int16SliceSrc = load { i16*, i64, i64 }, { i16*, i64, i64 }* @main.int16SliceSrc
+  %int16SliceSrc.len = extractvalue { i16*, i64, i64 } %int16SliceSrc, 1
+  %int16SliceSrc.len.bytes = mul i64 %int16SliceSrc.len, 2
+  %int16SliceDst.buf.raw = call i8* @runtime.alloc(i64 %int16SliceSrc.len.bytes)
+  %int16SliceDst.buf = bitcast i8* %int16SliceDst.buf.raw to i16*
+  %3 = insertvalue { i16*, i64, i64 } undef, i16* %int16SliceDst.buf, 0
+  %4 = insertvalue { i16*, i64, i64 } %3, i64 %int16SliceSrc.len, 1
+  %5 = insertvalue { i16*, i64, i64 } %4, i64 %int16SliceSrc.len, 2
+  store { i16*, i64, i64 } %5, { i16*, i64, i64 }* @main.int16SliceDst
+
+  ; equivalent of:
+  ;     copy(int16SliceDst, int16SliceSrc)
+  %int16SliceSrc.buf = extractvalue { i16*, i64, i64 } %int16SliceSrc, 0
+  %int16SliceSrc.buf.i8ptr = bitcast i16* %int16SliceSrc.buf to i8*
+  %int16SliceDst.buf.i8ptr = bitcast i16* %int16SliceDst.buf to i8*
+  %copy.n2 = call i64 @runtime.sliceCopy(i8* %int16SliceDst.buf.i8ptr, i8* %int16SliceSrc.buf.i8ptr, i64 %int16SliceSrc.len, i64 %int16SliceSrc.len, i64 2)
+
+  ret void
+}
diff --git a/interp/testdata/slice-copy.out.ll b/interp/testdata/slice-copy.out.ll
new file mode 100644
index 000000000..281756433
--- /dev/null
+++ b/interp/testdata/slice-copy.out.ll
@@ -0,0 +1,20 @@
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64--linux"
+
+declare void @runtime.printuint8(i8) local_unnamed_addr
+
+declare void @runtime.printint16(i16) local_unnamed_addr
+
+define void @runtime.initAll() unnamed_addr {
+entry:
+  ret void
+}
+
+define void @main() unnamed_addr {
+entry:
+  call void @runtime.printuint8(i8 3)
+  call void @runtime.printuint8(i8 3)
+  call void @runtime.printint16(i16 5)
+  call void @runtime.printint16(i16 5)
+  ret void
+}
diff --git a/interp/values.go b/interp/values.go
index 374d5ad00..40bc3c907 100644
--- a/interp/values.go
+++ b/interp/values.go
@@ -98,13 +98,33 @@ func (v *LocalValue) GetElementPtr(indices []uint32) Value {
 		gep := llvm.ConstGEP(v.Underlying, getLLVMIndices(int32Type, indices))
 		return &LocalValue{v.Eval, gep}
 	}
-	switch v.Underlying.Opcode() {
-	case llvm.GetElementPtr, llvm.IntToPtr, llvm.BitCast:
-		int32Type := v.Underlying.Type().Context().Int32Type()
-		llvmIndices := getLLVMIndices(int32Type, indices)
-		return &LocalValue{v.Eval, llvm.ConstGEP(v.Underlying, llvmIndices)}
-	default:
-		panic("interp: GEP on a constant")
+	if !v.Underlying.IsAConstantExpr().IsNil() {
+		switch v.Underlying.Opcode() {
+		case llvm.GetElementPtr, llvm.IntToPtr, llvm.BitCast:
+			int32Type := v.Underlying.Type().Context().Int32Type()
+			llvmIndices := getLLVMIndices(int32Type, indices)
+			return &LocalValue{v.Eval, llvm.ConstGEP(v.Underlying, llvmIndices)}
+		}
+	}
+	panic("interp: unknown GEP")
+}
+
+// stripPointerCasts removes all const bitcasts from pointer values, if there
+// are any.
+func (v *LocalValue) stripPointerCasts() *LocalValue {
+	value := v.Underlying
+	for {
+		if !value.IsAConstantExpr().IsNil() {
+			switch value.Opcode() {
+			case llvm.BitCast:
+				value = value.Operand(0)
+				continue
+			}
+		}
+		return &LocalValue{
+			Eval:       v.Eval,
+			Underlying: value,
+		}
 	}
 }