cmd/compile: range loop over []byte, []int can avoid base pointer increments

[randall77]

var t [256]byte

func f(b *[16]byte) {
    for i, v := range b {
        b[i] = t[v]
    }
}

compiles to:

    0x000f 00015 (tmp1.go:7)    MOVBLZX (AX), DX
    0x0012 00018 (tmp1.go:7)    LEAQ    "".t(SB), BX
    0x0019 00025 (tmp1.go:7)    MOVBLZX (BX)(DX*1), DX
    0x001d 00029 (tmp1.go:7)    MOVQ    "".b+8(FP), BX
    0x0022 00034 (tmp1.go:7)    MOVB    DL, (BX)(CX*1)
    0x0025 00037 (tmp1.go:6)    INCQ    AX
    0x0028 00040 (tmp1.go:6)    INCQ    CX
    0x002b 00043 (tmp1.go:6)    CMPQ    CX, $16
    0x002f 00047 (tmp1.go:6)    JLT $0, 15

It looks like we strength-reduced the index into b into a pointer increment. But the terminating condition still uses the integer, so we end up having 2 induction variables instead of one. We should either compute the terminating condition using an end pointer (and throw away the induction variable CX), or throw away the pointer induction variable (AX) and use an indexed load.

@brtzsnr

[brtzsnr]

I don't recall any strength reduction code in the current compiler. This is I think how the code is generated by the frontend and is one of the test cases that a SR will hopefully address.

Alternatively, should the frontend generate better code?

[josharian]

We'd have to be careful that end pointers don't confuse the GC. See related comments in gc/range.go (which is indeed probably the place for improvements here). See also my pending bool2int CL for an interaction between SSA and range / end-of-slice front end code.

[dr2chase]

A potential sort-of-optimization for the future is to keep the locally-root (might not be really-root, depending on what our callers fed us) pointers safely on the stack, and then let the derived and sometimes-off-the-end pointers be marked as not live as long as we knew a 1:1 correspondence to the local roots. Means that the GC scans less, means that off-the-end is okay, means that more often the GC's offset calculation isn't needed.

[dr2chase]

Except for pointers to stack-allocated things, oops, never mind.

[rsc]

This is not a strength reduction. It's just the code generated for range loops over arrays/slices: there is a pointer being advanced and an integer index. The pointer advancement avoids a multiply and a bounds check, at least in the old system. You could change the range expansion to avoid the pointer++ when the element size is something that has cheap index calculation, and then mark the indexing as bounds-checked already.

[martisch]

Started working on this and created a CL that computes the element position directly each time if it is cheap to do. Currently looking at the effects, adjusting tests, benchmarking and evaluating e.g. if we could just compare against a pointer to the end of the array. I am planning to send a CL for 1.9 within the next 2 weeks.

with new CL:

        0x0000 00000 (/Users/martisch/test/main.go:7)   MOVQ    "".b+8(FP), AX
        0x0005 00005 (/Users/martisch/test/main.go:7)   MOVQ    $0, CX
        0x0007 00007 (/Users/martisch/test/main.go:7)   CMPQ    CX, $16
        0x000b 00011 (/Users/martisch/test/main.go:7)   JGE     $0, 42
        0x000d 00013 (/Users/martisch/test/main.go:7)   TESTB   AL, (AX) // can and should be outside the loop?
        0x000f 00015 (/Users/martisch/test/main.go:8)   MOVBLZX (AX)(CX*1), DX
        0x0013 00019 (/Users/martisch/test/main.go:8)   LEAQ    "".t(SB), BX
        0x001a 00026 (/Users/martisch/test/main.go:8)   MOVBLZX (BX)(DX*1), DX
        0x001e 00030 (/Users/martisch/test/main.go:8)   MOVB    DL, (AX)(CX*1)
        0x0021 00033 (/Users/martisch/test/main.go:7)   INCQ    CX
        0x0024 00036 (/Users/martisch/test/main.go:7)   CMPQ    CX, $16
        0x0028 00040 (/Users/martisch/test/main.go:7)   JLT     $0, 13
        0x002a 00042 (/Users/martisch/test/main.go:10)  RET

without:

        0x0000 00000 (/Users/martisch/test/main.go:7)   MOVQ    "".b+8(FP), AX
        0x0005 00005 (/Users/martisch/test/main.go:7)   TESTB   AL, (AX)
        0x0007 00007 (/Users/martisch/test/main.go:6)   MOVQ    AX, CX
        0x000a 00010 (/Users/martisch/test/main.go:7)   MOVQ    $0, DX
        0x000c 00012 (/Users/martisch/test/main.go:7)   CMPQ    DX, $16
        0x0010 00016 (/Users/martisch/test/main.go:7)   JGE     $0, 47
        0x0012 00018 (/Users/martisch/test/main.go:8)   MOVBLZX (AX), BX
        0x0015 00021 (/Users/martisch/test/main.go:8)   LEAQ    "".t(SB), SI
        0x001c 00028 (/Users/martisch/test/main.go:8)   MOVBLZX (SI)(BX*1), BX
        0x0020 00032 (/Users/martisch/test/main.go:8)   MOVB    BL, (CX)(DX*1)
        0x0023 00035 (/Users/martisch/test/main.go:7)   INCQ    AX
        0x0026 00038 (/Users/martisch/test/main.go:7)   INCQ    DX
        0x0029 00041 (/Users/martisch/test/main.go:7)   CMPQ    DX, $16
        0x002d 00045 (/Users/martisch/test/main.go:7)   JLT     $0, 18
        0x002f 00047 (/Users/martisch/test/main.go:10)  RET

[rsc]

Thanks. Note that the "pointer to the end of the array" is not well defined in Go. You can't point past the last element (that's a pointer to a different object and will confuse the GC), you can't use an integer instead of a pointer (that won't be updated if the object is on the stack and moves, confusing the program itself), and you can't use a pointer to the last element (an array with 0 elements has no last element). You could use the pointer to the last element as long as there's a check for zero-size arrays that bypasses everything entirely. Anyway, just keep all that in mind. Thanks again.

[martisch]

@rsc thanks. What i had in mind was having a look at what you described: "You could use the pointer to the last element as long as there's a check for zero-size arrays".

On top off all what you mentioned one also needs to keep e.g. the order in which assignments are made in mind. I seem to have found a bug in the string range case (in new and old code) while working on the array range code. #18376