Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
gwik opened this issue Apr 24, 2017 · 9 comments
Closed

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

gwik opened this issue Apr 24, 2017 · 9 comments
Labels
FrozenDueToAge
Milestone
Go1.8.3

Comments

@gwik
Copy link
Contributor

gwik commented Apr 24, 2017

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 ALTree added the NeedsFix The path to resolution is known, but the work has not been done. label Apr 24, 2017
@ALTree
Copy link
Member

ALTree commented Apr 24, 2017

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

Will try to bisect.

@cherrymui
Copy link
Member 

    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
Copy link
Member

ALTree commented Apr 24, 2017

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

@cherrymui
Copy link
Member

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
Copy link
Member

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
}

@randall77 randall77 added this to the Go1.8.2 milestone Apr 24, 2017
@gopherbot
Copy link
Contributor

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

@randall77
Copy link
Contributor

Reopening for 1.8.2.

@randall77 randall77 reopened this May 9, 2017
@aclements aclements removed the NeedsFix The path to resolution is known, but the work has not been done. label May 16, 2017
@bradfitz bradfitz modified the milestones: Go1.8.2, Go1.8.3 May 18, 2017
@gopherbot
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 23, 2017
@tzneal @bradfitz
[release-branch.go1.8] cmd/compile: ignore types when considering tup…
195e20a 
…le select for CSE

Fixes #20097

Change-Id: I3c9626ccc8cd0c46a7081ea8650b2ff07a5d4fcd
Reviewed-on: https://go-review.googlesource.com/41505
Run-TryBot: Todd Neal <todd@tneal.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-on: https://go-review.googlesource.com/43997
Run-TryBot: Chris Broadfoot <cbro@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@bradfitz
Copy link
Contributor

Done in https://go-review.googlesource.com/c/43997/

@golang golang locked and limited conversation to collaborators May 23, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.8.3
Development

No branches or pull requests
7 participants
@bradfitz @gwik @aclements @ALTree @randall77 @gopherbot @cherrymui