Merge branch 'autopar_rebase2' into autopar_develdevel/autopar_devel

Quickly commit changes in the rebase branch.

12 files changed, 206 insertions, 88 deletions

diff --git a/libgo/go/math/big/arith_decl.go b/libgo/go/math/big/arith_decl.go
index 0a139f1..61df0df 100644
--- a/libgo/go/math/big/arith_decl.go
+++ b/libgo/go/math/big/arith_decl.go
@@ -3,7 +3,7 @@
 // license that can be found in the LICENSE file.
 
 // +build ignore
-// +build !math_big_pure_go,!riscv64
+// +build !math_big_pure_go
 
 package big
 
diff --git a/libgo/go/math/big/arith_decl_pure.go b/libgo/go/math/big/arith_decl_pure.go
index 8853eb6..ee8f922 100644
--- a/libgo/go/math/big/arith_decl_pure.go
+++ b/libgo/go/math/big/arith_decl_pure.go
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// -build math_big_pure_go riscv64
+// -build math_big_pure_go
 
 package big
 
diff --git a/libgo/go/math/big/arith_decl_s390x.go b/libgo/go/math/big/arith_decl_s390x.go
index 3936d3f..712f115 100644
--- a/libgo/go/math/big/arith_decl_s390x.go
+++ b/libgo/go/math/big/arith_decl_s390x.go
@@ -7,18 +7,13 @@
 
 package big
 
+import "internal/cpu"
+
 func addVV_check(z, x, y []Word) (c Word)
 func addVV_vec(z, x, y []Word) (c Word)
 func addVV_novec(z, x, y []Word) (c Word)
 func subVV_check(z, x, y []Word) (c Word)
 func subVV_vec(z, x, y []Word) (c Word)
 func subVV_novec(z, x, y []Word) (c Word)
-func addVW_check(z, x []Word, y Word) (c Word)
-func addVW_vec(z, x []Word, y Word) (c Word)
-func addVW_novec(z, x []Word, y Word) (c Word)
-func subVW_check(z, x []Word, y Word) (c Word)
-func subVW_vec(z, x []Word, y Word) (c Word)
-func subVW_novec(z, x []Word, y Word) (c Word)
-func hasVectorFacility() bool
 
-var hasVX = hasVectorFacility()
+var hasVX = cpu.S390X.HasVX
diff --git a/libgo/go/math/big/arith_s390x_test.go b/libgo/go/math/big/arith_s390x_test.go
index 0e8ac85..be1ca7d 100644
--- a/libgo/go/math/big/arith_s390x_test.go
+++ b/libgo/go/math/big/arith_s390x_test.go
@@ -31,15 +31,3 @@ func TestFunVVnovec(t *testing.T) {
 		}
 	}
 }
-
-func TestFunVWnovec(t *testing.T) {
-	if hasVX == true {
-		for _, a := range sumVW {
-			arg := a
-			testFunVW(t, "addVW_novec", addVW_novec, arg)
-
-			arg = argVW{a.x, a.z, a.y, a.c}
-			testFunVW(t, "subVW_novec", subVW_novec, arg)
-		}
-	}
-}
diff --git a/libgo/go/math/big/float.go b/libgo/go/math/big/float.go
index b3c3295..da964ee 100644
--- a/libgo/go/math/big/float.go
+++ b/libgo/go/math/big/float.go
@@ -224,7 +224,9 @@ func (x *Float) Mode() RoundingMode {
 	return x.mode
 }
 
-// Acc returns the accuracy of x produced by the most recent operation.
+// Acc returns the accuracy of x produced by the most recent
+// operation, unless explicitly documented otherwise by that
+// operation.
 func (x *Float) Acc() Accuracy {
 	return x.acc
 }
diff --git a/libgo/go/math/big/floatconv.go b/libgo/go/math/big/floatconv.go
index 95e32d3..57b7df3 100644
--- a/libgo/go/math/big/floatconv.go
+++ b/libgo/go/math/big/floatconv.go
@@ -290,7 +290,7 @@ func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b i
 	return new(Float).SetPrec(prec).SetMode(mode).Parse(s, base)
 }
 
-var _ fmt.Scanner = &floatZero // *Float must implement fmt.Scanner
+var _ fmt.Scanner = (*Float)(nil) // *Float must implement fmt.Scanner
 
 // Scan is a support routine for fmt.Scanner; it sets z to the value of
 // the scanned number. It accepts formats whose verbs are supported by
diff --git a/libgo/go/math/big/int.go b/libgo/go/math/big/int.go
index 18f122e..65f3248 100644
--- a/libgo/go/math/big/int.go
+++ b/libgo/go/math/big/int.go
@@ -447,11 +447,26 @@ func (z *Int) SetBytes(buf []byte) *Int {
 }
 
 // Bytes returns the absolute value of x as a big-endian byte slice.
+//
+// To use a fixed length slice, or a preallocated one, use FillBytes.
 func (x *Int) Bytes() []byte {
 	buf := make([]byte, len(x.abs)*_S)
 	return buf[x.abs.bytes(buf):]
 }
 
+// FillBytes sets buf to the absolute value of x, storing it as a zero-extended
+// big-endian byte slice, and returns buf.
+//
+// If the absolute value of x doesn't fit in buf, FillBytes will panic.
+func (x *Int) FillBytes(buf []byte) []byte {
+	// Clear whole buffer. (This gets optimized into a memclr.)
+	for i := range buf {
+		buf[i] = 0
+	}
+	x.abs.bytes(buf)
+	return buf
+}
+
 // BitLen returns the length of the absolute value of x in bits.
 // The bit length of 0 is 0.
 func (x *Int) BitLen() int {
@@ -465,8 +480,8 @@ func (x *Int) TrailingZeroBits() uint {
 }
 
 // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
-// If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m > 0, y < 0,
-// and x and n are not relatively prime, z is unchanged and nil is returned.
+// If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m != 0, y < 0,
+// and x and m are not relatively prime, z is unchanged and nil is returned.
 //
 // Modular exponentiation of inputs of a particular size is not a
 // cryptographically constant-time operation.
diff --git a/libgo/go/math/big/int_test.go b/libgo/go/math/big/int_test.go
index e3a1587..3c85573 100644
--- a/libgo/go/math/big/int_test.go
+++ b/libgo/go/math/big/int_test.go
@@ -1840,3 +1840,57 @@ func BenchmarkDiv(b *testing.B) {
 		})
 	}
 }
+
+func TestFillBytes(t *testing.T) {
+	checkResult := func(t *testing.T, buf []byte, want *Int) {
+		t.Helper()
+		got := new(Int).SetBytes(buf)
+		if got.CmpAbs(want) != 0 {
+			t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
+		}
+	}
+	panics := func(f func()) (panic bool) {
+		defer func() { panic = recover() != nil }()
+		f()
+		return
+	}
+
+	for _, n := range []string{
+		"0",
+		"1000",
+		"0xffffffff",
+		"-0xffffffff",
+		"0xffffffffffffffff",
+		"0x10000000000000000",
+		"0xabababababababababababababababababababababababababa",
+		"0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
+	} {
+		t.Run(n, func(t *testing.T) {
+			t.Logf(n)
+			x, ok := new(Int).SetString(n, 0)
+			if !ok {
+				panic("invalid test entry")
+			}
+
+			// Perfectly sized buffer.
+			byteLen := (x.BitLen() + 7) / 8
+			buf := make([]byte, byteLen)
+			checkResult(t, x.FillBytes(buf), x)
+
+			// Way larger, checking all bytes get zeroed.
+			buf = make([]byte, 100)
+			for i := range buf {
+				buf[i] = 0xff
+			}
+			checkResult(t, x.FillBytes(buf), x)
+
+			// Too small.
+			if byteLen > 0 {
+				buf = make([]byte, byteLen-1)
+				if !panics(func() { x.FillBytes(buf) }) {
+					t.Errorf("expected panic for small buffer and value %x", x)
+				}
+			}
+		})
+	}
+}
diff --git a/libgo/go/math/big/link_test.go b/libgo/go/math/big/link_test.go
new file mode 100644
index 0000000..2212bd4
--- /dev/null
+++ b/libgo/go/math/big/link_test.go
@@ -0,0 +1,63 @@
+// Copyright 2020 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 big
+
+import (
+	"bytes"
+	"internal/testenv"
+	"io/ioutil"
+	"os/exec"
+	"path/filepath"
+	"testing"
+)
+
+// Tests that the linker is able to remove references to Float, Rat,
+// and Int if unused (notably, not used by init).
+func TestLinkerGC(t *testing.T) {
+	if testing.Short() {
+		t.Skip("skipping in short mode")
+	}
+	t.Parallel()
+	tmp := t.TempDir()
+	goBin := testenv.GoToolPath(t)
+	goFile := filepath.Join(tmp, "x.go")
+	file := []byte(`package main
+import _ "math/big"
+func main() {}
+`)
+	if err := ioutil.WriteFile(goFile, file, 0644); err != nil {
+		t.Fatal(err)
+	}
+	cmd := exec.Command(goBin, "build", "-o", "x.exe", "x.go")
+	cmd.Dir = tmp
+	if out, err := cmd.CombinedOutput(); err != nil {
+		t.Fatalf("compile: %v, %s", err, out)
+	}
+
+	cmd = exec.Command(goBin, "tool", "nm", "x.exe")
+	cmd.Dir = tmp
+	nm, err := cmd.CombinedOutput()
+	if err != nil {
+		t.Fatalf("nm: %v, %s", err, nm)
+	}
+	const want = "runtime.(*Frames).Next"
+	if !bytes.Contains(nm, []byte(want)) {
+		// Test the test.
+		t.Errorf("expected symbol %q not found", want)
+	}
+	bad := []string{
+		"math/big.(*Float)",
+		"math/big.(*Rat)",
+		"math/big.(*Int)",
+	}
+	for _, sym := range bad {
+		if bytes.Contains(nm, []byte(sym)) {
+			t.Errorf("unexpected symbol %q found", sym)
+		}
+	}
+	if t.Failed() {
+		t.Logf("Got: %s", nm)
+	}
+}
diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go
index 1b771ca..6a3989b 100644
--- a/libgo/go/math/big/nat.go
+++ b/libgo/go/math/big/nat.go
@@ -740,7 +740,8 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) {
 // The remainder overwrites input u.
 //
 // Precondition:
-// - len(q) >= len(u)-len(v)
+// - q is large enough to hold the quotient u / v
+//   which has a maximum length of len(u)-len(v)+1.
 func (q nat) divBasic(u, v nat) {
 	n := len(v)
 	m := len(u) - n
@@ -779,6 +780,8 @@ func (q nat) divBasic(u, v nat) {
 		}
 
 		// D4.
+		// Compute the remainder u - (q̂*v) << (_W*j).
+		// The subtraction may overflow if q̂ estimate was off by one.
 		qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0)
 		qhl := len(qhatv)
 		if j+qhl > len(u) && qhatv[n] == 0 {
@@ -787,7 +790,11 @@ func (q nat) divBasic(u, v nat) {
 		c := subVV(u[j:j+qhl], u[j:], qhatv)
 		if c != 0 {
 			c := addVV(u[j:j+n], u[j:], v)
-			u[j+n] += c
+			// If n == qhl, the carry from subVV and the carry from addVV
+			// cancel out and don't affect u[j+n].
+			if n < qhl {
+				u[j+n] += c
+			}
 			qhat--
 		}
 
@@ -827,6 +834,10 @@ func (z nat) divRecursive(u, v nat) {
 	putNat(tmp)
 }
 
+// divRecursiveStep computes the division of u by v.
+// - z must be large enough to hold the quotient
+// - the quotient will overwrite z
+// - the remainder will overwrite u
 func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) {
 	u = u.norm()
 	v = v.norm()
@@ -1465,19 +1476,26 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
 }
 
 // bytes writes the value of z into buf using big-endian encoding.
-// len(buf) must be >= len(z)*_S. The value of z is encoded in the
-// slice buf[i:]. The number i of unused bytes at the beginning of
-// buf is returned as result.
+// The value of z is encoded in the slice buf[i:]. If the value of z
+// cannot be represented in buf, bytes panics. The number i of unused
+// bytes at the beginning of buf is returned as result.
 func (z nat) bytes(buf []byte) (i int) {
 	i = len(buf)
 	for _, d := range z {
 		for j := 0; j < _S; j++ {
 			i--
-			buf[i] = byte(d)
+			if i >= 0 {
+				buf[i] = byte(d)
+			} else if byte(d) != 0 {
+				panic("math/big: buffer too small to fit value")
+			}
 			d >>= 8
 		}
 	}
 
+	if i < 0 {
+		i = 0
+	}
 	for i < len(buf) && buf[i] == 0 {
 		i++
 	}
diff --git a/libgo/go/math/big/nat_test.go b/libgo/go/math/big/nat_test.go
index 32f29e3..89e913f 100644
--- a/libgo/go/math/big/nat_test.go
+++ b/libgo/go/math/big/nat_test.go
@@ -786,3 +786,21 @@ func TestNatDiv(t *testing.T) {
 		}
 	}
 }
+
+// TestIssue37499 triggers the edge case of divBasic where
+// the inaccurate estimate of the first word's quotient
+// happens at the very beginning of the loop.
+func TestIssue37499(t *testing.T) {
+	// Choose u and v such that v is slightly larger than u >> N.
+	// This tricks divBasic into choosing 1 as the first word
+	// of the quotient. This works in both 32-bit and 64-bit settings.
+	u := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706b39f8489c1d28e57bb5ba4ef9fd9387a3e344402c0a453381")
+	v := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706c")
+
+	q := nat(nil).make(8)
+	q.divBasic(u, v)
+	q = q.norm()
+	if s := string(q.utoa(16)); s != "fffffffffffffffffffffffffffffffffffffffffffffffb" {
+		t.Fatalf("incorrect quotient: %s", s)
+	}
+}
diff --git a/libgo/go/math/big/sqrt.go b/libgo/go/math/big/sqrt.go
index 53403aa..0d50164 100644
--- a/libgo/go/math/big/sqrt.go
+++ b/libgo/go/math/big/sqrt.go
@@ -4,17 +4,29 @@
 
 package big
 
-import "math"
-
-var (
-	three = NewFloat(3.0)
+import (
+	"math"
+	"sync"
 )
 
+var threeOnce struct {
+	sync.Once
+	v *Float
+}
+
+func three() *Float {
+	threeOnce.Do(func() {
+		threeOnce.v = NewFloat(3.0)
+	})
+	return threeOnce.v
+}
+
 // Sqrt sets z to the rounded square root of x, and returns it.
 //
 // If z's precision is 0, it is changed to x's precision before the
 // operation. Rounding is performed according to z's precision and
-// rounding mode.
+// rounding mode, but z's accuracy is not computed. Specifically, the
+// result of z.Acc() is undefined.
 //
 // The function panics if z < 0. The value of z is undefined in that
 // case.
@@ -61,61 +73,14 @@ func (z *Float) Sqrt(x *Float) *Float {
 	}
 	// 0.25 <= z < 2.0
 
-	// Solving x² - z = 0 directly requires a Quo call, but it's
-	// faster for small precisions.
-	//
-	// Solving 1/x² - z = 0 avoids the Quo call and is much faster for
-	// high precisions.
-	//
-	// 128bit precision is an empirically chosen threshold.
-	if z.prec <= 128 {
-		z.sqrtDirect(z)
-	} else {
-		z.sqrtInverse(z)
-	}
+	// Solving 1/x² - z = 0 avoids Quo calls and is faster, especially
+	// for high precisions.
+	z.sqrtInverse(z)
 
 	// re-attach halved exponent
 	return z.SetMantExp(z, b/2)
 }
 
-// Compute √x (up to prec 128) by solving
-//   t² - x = 0
-// for t, starting with a 53 bits precision guess from math.Sqrt and
-// then using at most two iterations of Newton's method.
-func (z *Float) sqrtDirect(x *Float) {
-	// let
-	//   f(t) = t² - x
-	// then
-	//   g(t) = f(t)/f'(t) = ½(t² - x)/t
-	// and the next guess is given by
-	//   t2 = t - g(t) = ½(t² + x)/t
-	u := new(Float)
-	ng := func(t *Float) *Float {
-		u.prec = t.prec
-		u.Mul(t, t)        // u = t²
-		u.Add(u, x)        //   = t² + x
-		u.exp--            //   = ½(t² + x)
-		return t.Quo(u, t) //   = ½(t² + x)/t
-	}
-
-	xf, _ := x.Float64()
-	sq := NewFloat(math.Sqrt(xf))
-
-	switch {
-	case z.prec > 128:
-		panic("sqrtDirect: only for z.prec <= 128")
-	case z.prec > 64:
-		sq.prec *= 2
-		sq = ng(sq)
-		fallthrough
-	default:
-		sq.prec *= 2
-		sq = ng(sq)
-	}
-
-	z.Set(sq)
-}
-
 // Compute √x (to z.prec precision) by solving
 //   1/t² - x = 0
 // for t (using Newton's method), and then inverting.
@@ -128,6 +93,7 @@ func (z *Float) sqrtInverse(x *Float) {
 	//   t2 = t - g(t) = ½t(3 - xt²)
 	u := newFloat(z.prec)
 	v := newFloat(z.prec)
+	three := three()
 	ng := func(t *Float) *Float {
 		u.prec = t.prec
 		v.prec = t.prec
@@ -137,7 +103,6 @@ func (z *Float) sqrtInverse(x *Float) {
 		u.Mul(t, v)     // u = t(3 - xt²)
 		u.exp--         //   = ½t(3 - xt²)
 		return t.Set(u)
-
 	}
 
 	xf, _ := x.Float64()