cmd/compile: crash internal compiler error: schedule does not include all values (simple program)

[gwik]

What version of Go are you using (go version)?

go version go1.8.1 darwin/amd64

What operating system and processor architecture are you using (go env)?

GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/gwik/go"
GORACE=""
GOROOT="/usr/local/go"
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/st/k_6dl_dx5c919wbcjm0340x00000gp/T/go-build456109878=/tmp/go-build -gno-record-gcc-switches -fno-common"
CXX="clang++"
CGO_ENABLED="1"
PKG_CONFIG="pkg-config"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"

What did you do?

I was writing a simple token bucket algorithm when it failed to compile.
Here is the code, I reduced it to the smallest possible that still trigger the compiler error.

package main

import "time"

type Clock func() time.Time

type bucket struct {
	capacity int64
	tokens   int64
	rate     time.Duration

	lastFill time.Time
	clock    Clock
}

func (b *bucket) Take(i int64) {
	for {
		now := b.clock()
		fill := int64(b.rate) / b.capacity * int64(b.lastFill.Sub(now))
		if fill >= i {
			b.lastFill = now
			b.tokens = fill - i
			return
		}
		time.Sleep(b.rate / time.Duration(b.capacity))
	}
}

func main() {
}

What did you expect to see?

The compilation should succeed or fail because the program is invalid.

What did you see instead?

The compiler crashed with an internal error.

# command-line-arguments
./internalcompilererror.go:17: internal compiler error: schedule does not include all values

goroutine 1 [running]:
runtime/debug.Stack(0x0, 0x0, 0x0)
	/usr/local/go/src/runtime/debug/stack.go:24 +0x79
cmd/compile/internal/gc.Fatalf(0x16c4939, 0x24, 0x0, 0x0, 0x0)
	/usr/local/go/src/cmd/compile/internal/gc/subr.go:167 +0x226
cmd/compile/internal/gc.(*ssaExport).Fatalf(0x19c7b95, 0x11, 0x16c4939, 0x24, 0x0, 0x0, 0x0)
	/usr/local/go/src/cmd/compile/internal/gc/ssa.go:4984 +0x5d
cmd/compile/internal/ssa.(*Config).Fatalf(0xc4203b8000, 0xdffd3db700000011, 0x16c4939, 0x24, 0x0, 0x0, 0x0)
	/usr/local/go/src/cmd/compile/internal/ssa/config.go:343 +0x6e
cmd/compile/internal/ssa.(*Func).Fatalf(0xc420398480, 0x16c4939, 0x24, 0x0, 0x0, 0x0)
	/usr/local/go/src/cmd/compile/internal/ssa/func.go:414 +0x6b
cmd/compile/internal/ssa.schedule(0xc420398480)
	/usr/local/go/src/cmd/compile/internal/ssa/schedule.go:287 +0x126f
cmd/compile/internal/ssa.Compile(0xc420398480)
	/usr/local/go/src/cmd/compile/internal/ssa/compile.go:69 +0x304
cmd/compile/internal/gc.buildssa(0xc420395170, 0x0)
	/usr/local/go/src/cmd/compile/internal/gc/ssa.go:180 +0x918
cmd/compile/internal/gc.compile(0xc420395170)
	/usr/local/go/src/cmd/compile/internal/gc/pgen.go:362 +0x204
cmd/compile/internal/gc.funccompile(0xc420395170)
	/usr/local/go/src/cmd/compile/internal/gc/dcl.go:1292 +0xdc
cmd/compile/internal/gc.Main()
	/usr/local/go/src/cmd/compile/internal/gc/main.go:464 +0x1f08
main.main()
	/usr/local/go/src/cmd/compile/main.go:50 +0xfe

[ALTree]

Go 1.7.5 is fine
go1.8, go1.8.1 and tip crash

Will try to bisect.

[cherrymui]

    v66 = DIVQ <int64,int64> v28 v32
    v68 = Select0 <time.Duration> v66
    v37 = Select0 <int64> v66

This is the problem. The scheduler assumes a tuple op (DIVQ) can have at most one Select0. But in this case v68 and v37 both are Select0 of v66, but not CSE'd because of the type difference.

[ALTree]

Git bisect says: "introduced in 25e0a36 (cmd/compile: clean up tuple types and selects)"

[cherrymui]

I tried to make the scheduler accepting more than one Select0's, but there is another problem. The result register is allocated at the tuple op (v66 DIVQ), and the Select0 is just a pesudo-op that doesn't allocate new register. So v68 and v37 use the same register, and both live. Register allocator crashes.
Probably we should CSE the two selectors regardless of type.

[cherrymui]

a simple repro (on AMD64):

type T int64
func f(x, y int64) (int64, T) {
        a := x / y
        b := T(x) / T(y)
        return a, b
}

[gopherbot]

CL https://golang.org/cl/41505 mentions this issue.

[randall77]

Reopening for 1.8.2.