x/tools/go/ssa: mistakenly converts slice index to int on 32 bit systems

[dominikh]

Consider this program:

package main

import "math"

func main() {
	var idx int64 = math.MaxInt32*2 + 8
	x := make([]int, 16)
	println(x[idx])
	println(x[int(idx)])
}

go/ssa compiles it to

func main():
0:                                                                entry P:0 S:0
	t0 = new [16]int (makeslice)                                   *[16]int
	t1 = slice t0[:16:int]                                            []int
	t2 = convert int <- int64 (4294967302:int64)                        int
	t3 = &t1[t2]                                                       *int
	t4 = *t3                                                            int
	t5 = println(t4)                                                     ()
	t6 = convert int <- int64 (4294967302:int64)                        int
	t7 = &t1[t6]                                                       *int
	t8 = *t7                                                            int
	t9 = println(t8)                                                     ()
	return

both times converting the index to int before using it. But on systems where int is 32 bits wide, this is not correct. Compare with the runtime behavior on GOARCH=386: The first indexing operation panics with panic: runtime error: index out of range [4294967302] with length 16 while the second one succeeds, accessing x[6], thanks to wrap-around.

https://go.dev/ref/spec#Index_expressions is the relevant section of the specification.

/cc @timothy-king

[timothy-king]

Thank you for the report. SSA is not faithfully translating the original program.

Here are possible options for resolving this:

1. Add a bounds check on the convert.
2. Expand the set of types accepted as dereference indices can be expanded. Then eliminate the conversion.

My thoughts:

• There are a lot of variants for bounds checking. The most obvious is to add a new basic block and branch on each conversion. This check can alternatively be built into the convert instruction (or a new instruction), i.e. panic if not in range. SSA can be made to be aware of the size of int when translating to eliminate noisy branches. (Probably are some variants I am missing.)
• The second option is the cleanest but is likely the hardest on direct users of the ssa package as they are expected to change the interpretation/assumptions of the Index and IndexAddr instructions everywhere. Index and IndexAddr phrase themselves in the documentation as "Index is an integer expression." It does not say "int expression". So we justifiably have wiggle room to eliminate the conversion.
• I do not believe we should make preserving the content of the panic a priority. As long as SSA says a panic happens, this is a sufficiently faithful translation.

Thoughts on the preferred resolution? In the meantime, I'll try to get some thoughts from the compiler folks for how to faithfully lower the check.

[timothy-king]

Relevant part of cmd/compile:

go/src/cmd/compile/internal/ssagen/ssa.go

Line 7378 in a42bbf4

func (s *state) extendIndex(idx, len *ssa.Value, kind ssa.BoundsKind, bounded bool) *ssa.Value {

This solutions requires knowing the sizes of the target architecture. x/tools/go/ssa currently lacks this information.

[mdempsky]

Expand the set of types accepted as dereference indices can be expanded. Then eliminate the conversion.

FWIW, this is the solution cmd/compile uses in its IR representation, where bounds checks are still implicit as part of the index operation.

It's only once we lower to SSA where bounds checks are explicit that we constrain the size of the index value, because it needs to be register-sized for instruction selection / register allocation.

[dominikh]

I'm in favour of option 2.

Adding explicit bounds checks with branches seems out of place. go/ssa doesn't explicitly encode panics in the CFG. Interface assertions, slice indexing, map writes, pointer dereferences, all are assumed to panic dynamically, without these edges being part of the CFG.

Adding a new instruction that checks the bounds before the conversion seems unnecessarily detailed, and somewhat redundant with IndexAddr also doing bounds checking on the int index. It also doesn't match the language specification: there is no "if the index doesn't fit into an int, we panic". There is only "if the index is out of bounds, we panic"

The only faithful representation of the language semantics is IndexAddr accepting any integer type. There is no conversion to int, and doing additional bounds checking and conversions outside the IndexAddr instruction creates new behavior that doesn't exist¹.

the hardest on direct users of the ssa package as they are expected to change the interpretation/assumptions of the Index and IndexAddr instructions everywhere

They don't have to change much. The type of the index is no longer guaranteed to be int, but that's about it. The instructions could already panic for out of bounds indices; now these indices can be larger than before. This doesn't seem any harder on them than adding an entirely new instruction.

¹: this is all considering that go/ssa is a high-level IR that represents the language as specified. It doesn't encode the actual, lowered to real instructions, behavior.

[zpavlinovic]

I also lean towards option 2. Adding explicit checks with branches also might increase the size of SSA unnecessarily.

[zpavlinovic]

The plan is to implement the fix based on option 2, which will happen after #48525 is done.

[gopherbot]

Change https://go.dev/cl/387996 mentions this issue: go/ssa: removes conversion of index value in Index and IndexAddr to int