compiler: implement complex division

This is hard to do correctly, so copy the relevant files from the Go
compiler itself.

For related discussions:
* https://github.com/golang/go/issues/14644
* https://github.com/golang/go/issues/29846

6 files changed, 138 insertions, 1 deletions

diff --git a/LICENSE b/LICENSE
index d13286b67..960e8609f 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,5 +1,8 @@
 Copyright (c) 2018-2019 TinyGo Authors. All rights reserved.
 
+TinyGo includes portions of the Go standard library.
+Copyright (c) 2009-2019 The Go Authors. All rights reserved.
+
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are
 met:
diff --git a/compiler/compiler.go b/compiler/compiler.go
index d750f12e6..2a0246971 100644
--- a/compiler/compiler.go
+++ b/compiler/compiler.go
@@ -1856,8 +1856,20 @@ func (c *Compiler) parseBinOp(op token.Token, typ types.Type, x, y llvm.Value, p
 				cplx = c.builder.CreateInsertValue(cplx, r, 0, "")
 				cplx = c.builder.CreateInsertValue(cplx, i, 1, "")
 				return cplx, nil
+			case token.QUO:
+				// Complex division.
+				// Do this in a library call because it's too difficult to do
+				// inline.
+				switch r1.Type().TypeKind() {
+				case llvm.FloatTypeKind:
+					return c.createRuntimeCall("complex64div", []llvm.Value{x, y}, ""), nil
+				case llvm.DoubleTypeKind:
+					return c.createRuntimeCall("complex128div", []llvm.Value{x, y}, ""), nil
+				default:
+					panic("unexpected complex type")
+				}
 			default:
-				return llvm.Value{}, c.makeError(pos, "todo: binop on complex number: "+op.String())
+				panic("binop on complex: " + op.String())
 			}
 		} else if typ.Info()&types.IsBoolean != 0 {
 			// Operations on booleans
diff --git a/src/runtime/complex.go b/src/runtime/complex.go
new file mode 100644
index 000000000..131aa58f0
--- /dev/null
+++ b/src/runtime/complex.go
@@ -0,0 +1,65 @@
+// Copyright 2010 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime
+
+// inf2one returns a signed 1 if f is an infinity and a signed 0 otherwise.
+// The sign of the result is the sign of f.
+func inf2one(f float64) float64 {
+	g := 0.0
+	if isInf(f) {
+		g = 1.0
+	}
+	return copysign(g, f)
+}
+
+func complex64div(n complex64, m complex64) complex64 {
+	return complex64(complex128div(complex128(n), complex128(m)))
+}
+
+func complex128div(n complex128, m complex128) complex128 {
+	var e, f float64 // complex(e, f) = n/m
+
+	// Algorithm for robust complex division as described in
+	// Robert L. Smith: Algorithm 116: Complex division. Commun. ACM 5(8): 435 (1962).
+	if abs(real(m)) >= abs(imag(m)) {
+		ratio := imag(m) / real(m)
+		denom := real(m) + ratio*imag(m)
+		e = (real(n) + imag(n)*ratio) / denom
+		f = (imag(n) - real(n)*ratio) / denom
+	} else {
+		ratio := real(m) / imag(m)
+		denom := imag(m) + ratio*real(m)
+		e = (real(n)*ratio + imag(n)) / denom
+		f = (imag(n)*ratio - real(n)) / denom
+	}
+
+	if isNaN(e) && isNaN(f) {
+		// Correct final result to infinities and zeros if applicable.
+		// Matches C99: ISO/IEC 9899:1999 - G.5.1  Multiplicative operators.
+
+		a, b := real(n), imag(n)
+		c, d := real(m), imag(m)
+
+		switch {
+		case m == 0 && (!isNaN(a) || !isNaN(b)):
+			e = copysign(inf, c) * a
+			f = copysign(inf, c) * b
+
+		case (isInf(a) || isInf(b)) && isFinite(c) && isFinite(d):
+			a = inf2one(a)
+			b = inf2one(b)
+			e = inf * (a*c + b*d)
+			f = inf * (b*c - a*d)
+
+		case (isInf(c) || isInf(d)) && isFinite(a) && isFinite(b):
+			c = inf2one(c)
+			d = inf2one(d)
+			e = 0 * (a*c + b*d)
+			f = 0 * (b*c - a*d)
+		}
+	}
+
+	return complex(e, f)
+}
diff --git a/src/runtime/float.go b/src/runtime/float.go
new file mode 100644
index 000000000..459e58dd7
--- /dev/null
+++ b/src/runtime/float.go
@@ -0,0 +1,53 @@
+// Copyright 2017 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime
+
+import "unsafe"
+
+var inf = float64frombits(0x7FF0000000000000)
+
+// isNaN reports whether f is an IEEE 754 ``not-a-number'' value.
+func isNaN(f float64) (is bool) {
+	// IEEE 754 says that only NaNs satisfy f != f.
+	return f != f
+}
+
+// isFinite reports whether f is neither NaN nor an infinity.
+func isFinite(f float64) bool {
+	return !isNaN(f - f)
+}
+
+// isInf reports whether f is an infinity.
+func isInf(f float64) bool {
+	return !isNaN(f) && !isFinite(f)
+}
+
+// Abs returns the absolute value of x.
+//
+// Special cases are:
+//	Abs(±Inf) = +Inf
+//	Abs(NaN) = NaN
+func abs(x float64) float64 {
+	const sign = 1 << 63
+	return float64frombits(float64bits(x) &^ sign)
+}
+
+// copysign returns a value with the magnitude
+// of x and the sign of y.
+func copysign(x, y float64) float64 {
+	const sign = 1 << 63
+	return float64frombits(float64bits(x)&^sign | float64bits(y)&sign)
+}
+
+// Float64bits returns the IEEE 754 binary representation of f.
+func float64bits(f float64) uint64 {
+	return *(*uint64)(unsafe.Pointer(&f))
+}
+
+// Float64frombits returns the floating point number corresponding
+// the IEEE 754 binary representation b.
+func float64frombits(b uint64) float64 {
+	return *(*float64)(unsafe.Pointer(&b))
+}
diff --git a/testdata/float.go b/testdata/float.go
index 431d724c4..4063281b7 100644
--- a/testdata/float.go
+++ b/testdata/float.go
@@ -62,8 +62,10 @@ func main() {
 	println("complex64 add: ", c64 + -3+8i)
 	println("complex64 sub: ", c64 - -3+8i)
 	println("complex64 mul: ", c64 * -3+8i)
+	println("complex64 div: ", c64 / -3+8i)
 	c128 = -5+2i
 	println("complex128 add:", c128 + 2+6i)
 	println("complex128 sub:", c128 - 2+6i)
 	println("complex128 mul:", c128 * 2+6i)
+	println("complex128 div:", c128 / 2+6i)
 }
diff --git a/testdata/float.txt b/testdata/float.txt
index ac3004777..4b7e3357f 100644
--- a/testdata/float.txt
+++ b/testdata/float.txt
@@ -26,6 +26,8 @@
 complex64 add:  (+2.000000e+000+1.000000e+001i)
 complex64 sub:  (+8.000000e+000+1.000000e+001i)
 complex64 mul:  (-1.500000e+001+2.000000e+000i)
+complex64 div:  (-1.666667e+000+7.333333e+000i)
 complex128 add: (-3.000000e+000+8.000000e+000i)
 complex128 sub: (-7.000000e+000+8.000000e+000i)
 complex128 mul: (-1.000000e+001+1.000000e+001i)
+complex128 div: (-2.500000e+000+7.000000e+000i)