Sounds like we should run the new SSA backend against https://github.com/dvyukov/gosmith / go-fuzz.

This error isn't from the SSA backend. It has existed since 1.5.
Go 1.4 happily accepts this code. Probably worse than an ICE.

I did a little bit of investigating. Consider the following two programs:

P_1:

package p

type k [1]m
type m map[k]int

OUT_1:
./p_1.go:4: invalid map key type k

The first line creates a forward declaration for k. The next line sets the value of m to a map with key 'k' and runs checkMapKeyType. It fails properly because [1]map[anything]anything is not a comparison type.

Now consider the same program with the two lines swapped:

P_2:

package p

type m map[k]int
type k [1]m

OUT_2:
./p_2.go:4: internal compiler error: bad type for map key: m

The difference is subtle. The first line creates a forward type for m. The second line creates a forward type for k, and checkMapKeyType([1]m) is called. The entire key [1]m is treated as a forward type instead of as array with an element that's a forward type. Instead of erroring out, checkMapKeyType does nothing and waits for the type [1]m to be fully resolved, which I don't believe will ever happen because of the mutually recursive type definitions. This is eventually caught here:

https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/reflect.go#L1006

I took at stab at a fix: https://go-review.googlesource.com/#/c/21830/

New results:

P_1 (original bug):

package p

type v []m
type m map[x]int
type x [4]v

OUT_1:
./orig.go:4: invalid map key type x

P_2:

package p

type m map[k]int
type k [1]m

OUT_2:

./p_2.go:3: invalid map key type k

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