compiler: fix max possible slice

This commit improves make([]T, len) to be closer to upstream Go. The
difference is unlikely to have much real-world effect, but previously
certain make([]T, len) expressions would not result in a slice out of
bounds error in TinyGo while they would have done such a thing in Go
proper. In practice, available RAM is likely to be a bigger limiting
factor.

2 files changed, 29 insertions, 8 deletions

diff --git a/compiler/compiler.go b/compiler/compiler.go
index ea0d51a67..dda5f51eb 100644
--- a/compiler/compiler.go
+++ b/compiler/compiler.go
@@ -23,7 +23,7 @@ import (
 // Version of the compiler pacakge. Must be incremented each time the compiler
 // package changes in a way that affects the generated LLVM module.
 // This version is independent of the TinyGo version number.
-const Version = 15 // last change: add crypto assembly aliases
+const Version = 16 // last change: fix max slice size
 
 func init() {
 	llvm.InitializeAllTargets()
@@ -1439,6 +1439,28 @@ func (b *builder) getValue(expr ssa.Value) llvm.Value {
 	}
 }
 
+// maxSliceSize determines the maximum size a slice of the given element type
+// can be.
+func (c *compilerContext) maxSliceSize(elementType llvm.Type) uint64 {
+	// Calculate ^uintptr(0), which is the max value that fits in uintptr.
+	maxPointerValue := llvm.ConstNot(llvm.ConstInt(c.uintptrType, 0, false)).ZExtValue()
+	// Calculate (^uint(0))/2, which is the max value that fits in an int.
+	maxIntegerValue := llvm.ConstNot(llvm.ConstInt(c.intType, 0, false)).ZExtValue() / 2
+
+	// Determine the maximum allowed size for a slice. The biggest possible
+	// pointer (starting from 0) would be maxPointerValue*sizeof(elementType) so
+	// divide by the element type to get the real maximum size.
+	maxSize := maxPointerValue / c.targetData.TypeAllocSize(elementType)
+
+	// len(slice) is an int. Make sure the length remains small enough to fit in
+	// an int.
+	if maxSize > maxIntegerValue {
+		maxSize = maxIntegerValue
+	}
+
+	return maxSize
+}
+
 // createExpr translates a Go SSA expression to LLVM IR. This can be zero, one,
 // or multiple LLVM IR instructions and/or runtime calls.
 func (b *builder) createExpr(expr ssa.Value) (llvm.Value, error) {
@@ -1652,10 +1674,8 @@ func (b *builder) createExpr(expr ssa.Value) (llvm.Value, error) {
 		elemSize := b.targetData.TypeAllocSize(llvmElemType)
 		elemSizeValue := llvm.ConstInt(b.uintptrType, elemSize, false)
 
-		// Calculate (^uintptr(0)) >> 1, which is the max value that fits in
-		// uintptr if uintptr were signed.
-		maxSize := llvm.ConstLShr(llvm.ConstNot(llvm.ConstInt(b.uintptrType, 0, false)), llvm.ConstInt(b.uintptrType, 1, false))
-		if elemSize > maxSize.ZExtValue() {
+		maxSize := b.maxSliceSize(llvmElemType)
+		if elemSize > maxSize {
 			// This seems to be checked by the typechecker already, but let's
 			// check it again just to be sure.
 			return llvm.Value{}, b.makeError(expr.Pos(), fmt.Sprintf("slice element type is too big (%v bytes)", elemSize))
@@ -1664,7 +1684,8 @@ func (b *builder) createExpr(expr ssa.Value) (llvm.Value, error) {
 		// Bounds checking.
 		lenType := expr.Len.Type().Underlying().(*types.Basic)
 		capType := expr.Cap.Type().Underlying().(*types.Basic)
-		b.createSliceBoundsCheck(maxSize, sliceLen, sliceCap, sliceCap, lenType, capType, capType)
+		maxSizeValue := llvm.ConstInt(b.uintptrType, maxSize, false)
+		b.createSliceBoundsCheck(maxSizeValue, sliceLen, sliceCap, sliceCap, lenType, capType, capType)
 
 		// Allocate the backing array.
 		sliceCapCast, err := b.createConvert(expr.Cap.Type(), types.Typ[types.Uintptr], sliceCap, expr.Pos())
diff --git a/compiler/testdata/slice.ll b/compiler/testdata/slice.ll
index f3e2aac63..7d027fb8b 100644
--- a/compiler/testdata/slice.ll
+++ b/compiler/testdata/slice.ll
@@ -127,7 +127,7 @@ slice.next:                                       ; preds = %entry
 
 define hidden { [3 x i8]*, i32, i32 } @main.makeArraySlice(i32 %len, i8* %context, i8* %parentHandle) unnamed_addr {
 entry:
-  %slice.maxcap = icmp slt i32 %len, 0
+  %slice.maxcap = icmp ugt i32 %len, 1431655765
   br i1 %slice.maxcap, label %slice.throw, label %slice.next
 
 slice.throw:                                      ; preds = %entry
@@ -146,7 +146,7 @@ slice.next:                                       ; preds = %entry
 
 define hidden { i32*, i32, i32 } @main.makeInt32Slice(i32 %len, i8* %context, i8* %parentHandle) unnamed_addr {
 entry:
-  %slice.maxcap = icmp slt i32 %len, 0
+  %slice.maxcap = icmp ugt i32 %len, 1073741823
   br i1 %slice.maxcap, label %slice.throw, label %slice.next
 
 slice.throw:                                      ; preds = %entry