cmd/compile: BCE does not take transitivity into account #19714

navytux · 2017-03-25T18:41:38Z

Please answer these questions before submitting your issue. Thanks!

What did you do?

Hello up there. Please consider the following function:

package xxx

func Aaa(b []byte, i int) {
        if !(0 <= i && i < len(b)) {
                return
        }

        for j := 0; j < i; j++ {
                b[j]++
        }
}

(https://play.golang.org/p/pACbUNtHoB)

here i is in valid range for b and j is iterating in [0,i) so it is also in valid range for b. However Aaa compiles to:

TEXT ·Aaa(SB), $8-32 // loopbce2.go:3
        // SUBQ    $8, SP
        // MOVQ    BP, (SP) (BP save)
        // LEAQ    (SP), BP (BP init)
        // FUNCDATA $0, gclocals·4032f753396f2012ad1784f398b170f4(SB) (args)
        FUNCDATA   $1, gclocals·69c1753bd5f81501d95132d08af04464(SB) (locals)
        MOVQ       i+24(FP), AX           // loopbce2.go:4
        TESTQ      AX, AX
        JLT        $0, pc80
        MOVQ       b+8(FP), CX
        CMPQ       AX, CX
        JGE        $0, pc80
        MOVQ       b+0(FP), DX            // loopbce2.go:8
        MOVQ       $0, BX                 // loopbce2.go:4
pc39:
        CMPQ       BX, AX                 // loopbce2.go:8
        JGE        $0, pc71
        CMPQ       BX, CX                 // loopbce2.go:9      <-- NOTE
        JCC        $0, pc64                                     <-- NOTE
        MOVBLZX    (DX)(BX*1), SI
        INCL       SI
        MOVB       SIB, (DX)(BX*1)
        INCQ       BX                     // loopbce2.go:8
        JMP        pc39
pc64:
        PCDATA     $0, $1                 // loopbce2.go:9
        CALL       runtime.panicindex(SB)                       <-- NOTE
        UNDEF
pc71:
        // MOVQ    (SP), BP (BP restore)  // loopbce2.go:11
        // ADDQ    $8, SP (SP restore)
        RET
pc80:
        // MOVQ    (SP), BP (BP restore)  // loopbce2.go:5
        // ADDQ    $8, SP (SP restore)
        RET

with b[j] access being bounds checked at runtime.

Just for the reference, if loop for j is in [0,len(b)):

        for j := 0; j < len(b); j++ {
                b[j]++
        }

no bounds checking is generated.

So looks like what is needed is to teach BCE that if i1 is in valid bounds, i2 in [0, i1] => i2 is also in valid bounds.

This actually came up as simplified case of

package xxx

func Encode(dst, src []byte) {
        if len(dst) < len(src) {
                return  // panic("dst overflow")
        }

        for i, v := range src {
                dst[i] = v
        }
}

where bounds checks are unneccessarily generated for dst[i].

The above case in turn tries to model e.g. encoding/hex.Encode in simplified way:

func Encode(dst, src []byte) int {
        //if len(dst) < len(src) * 2 {
        //      panic("dst overflow")
        //} 

        for i, v := range src {
                dst[i*2] = hextable[v>>4]
                dst[i*2+1] = hextable[v&0x0f]
        }   

        return len(src) * 2 
}

where even if initial check for len(dst) < len(src) * 2 => error is activated, still 2 bounds checks are generated (for dst[i*2] and dst[i*2+1]) making hex.Encode (together with #15808) much slower than it should be:

TEXT ·Encode(SB), $24-56 // hex.go:29
        // MOVQ    (TLS), CX (stack growth prologue)
        // CMPQ    SP, 16(CX)
        // JLS     207
        // SUBQ    $24, SP
        // MOVQ    BP, 16(SP) (BP save)
        // LEAQ    16(SP), BP (BP init)
        // FUNCDATA $0, gclocals·b9de2a960cf046391bcd3b554f7fabca(SB) (args)
        FUNCDATA   $1, gclocals·69c1753bd5f81501d95132d08af04464(SB) (locals)
        MOVQ       src+32(FP), AX         // hex.go:30
        MOVQ       AX, CX
        SHLQ       $1, AX
        MOVQ       dst+8(FP), DX
        CMPQ       DX, AX
        JLT        $0, pc177
        TESTQ      CX, CX                 // hex.go:34
        JLE        $0, pc148
        MOVQ       dst+0(FP), BX
        MOVQ       src+24(FP), SI
        MOVQ       $0, DI                 // hex.go:29
pc71:
        MOVBLZX    (SI), R8               // hex.go:34
        MOVQ       DI, R9                 // hex.go:35
        SHLQ       $1, DI
        MOVL       R8, R10
        SHRB       $4, R8B
        MOVBLZX    R8B, R8
        LEAQ       go.string."0123456789abcdef"(SB), R11 // hex.go:36  <-- #15808
        MOVBLZX    (R11)(R8*1), R8        // hex.go:35
        CMPQ       DI, DX                                       <-- NOTE
        JCC        $0, pc170                                    <-- NOTE
        MOVB       R8B, (BX)(DI*1)
        LEAQ       1(DI), R8              // hex.go:36
        ANDL       $15, R10
        MOVBLZX    (R11)(R10*1), R10
        CMPQ       R8, DX                                       <-- NOTE
        JCC        $0, pc163                                    <-- NOTE
        MOVB       R10B, 1(BX)(DI*1)
        INCQ       SI                     // hex.go:34
        LEAQ       1(R9), DI
        CMPQ       DI, CX
        JLT        $1, pc71
pc148:
        MOVQ       AX, _r2+48(FP)         // hex.go:39
        // MOVQ    16(SP), BP (BP restore)
        // ADDQ    $24, SP (SP restore)
        RET
pc163:
        // PCDATA  $0, $1 (stack growth)  // hex.go:36
        // CALL    runtime.panicindex(SB)
        // UNDEF
pc170:
        // PCDATA  $0, $1                 // hex.go:35
        // CALL    runtime.panicindex(SB)
        // UNDEF
pc177:
        // LEAQ    type.string(SB), AX    // hex.go:31
        // MOVQ    AX, (SP)
        // LEAQ    ·statictmp_12(SB), AX
        // MOVQ    AX, 8(SP)
        // PCDATA  $0, $1
        // CALL    runtime.gopanic(SB)
        // UNDEF
        // NOP
        // PCDATA  $0, $-1                // hex.go:29
        // CALL    runtime.morestack_noctxt(SB)
        // JMP     0

What did you expect to see?

No runtime bound checks.

What did you see instead?

Runtime bound check present for b[j] access.

Does this issue reproduce with the latest release (go1.8)?

Yes.

System details

go version devel +ecc6a81617 Sat Mar 25 00:35:35 2017 +0000 linux/amd64
GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/kirr/go"
GORACE=""
GOROOT="/home/kirr/src/tools/go/go"
GOTOOLDIR="/home/kirr/src/tools/go/go/pkg/tool/linux_amd64"
GCCGO="/usr/bin/gccgo"
CC="gcc"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build832545546=/tmp/go-build -gno-record-gcc-switches"
CXX="g++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOROOT/bin/go version: go version devel +ecc6a81617 Sat Mar 25 00:35:35 2017 +0000 linux/amd64
GOROOT/bin/go tool compile -V: compile version devel +ecc6a81617 Sat Mar 25 00:35:35 2017 +0000 X:framepointer
uname -sr: Linux 4.9.0-2-amd64
Distributor ID:	Debian
Description:	Debian GNU/Linux 9.0 (stretch)
Release:	9.0
Codename:	stretch
/lib/x86_64-linux-gnu/libc.so.6: GNU C Library (Debian GLIBC 2.24-9) stable release version 2.24, by Roland McGrath et al.
gdb --version: GNU gdb (Debian 7.12-6) 7.12.0.20161007-git

Thanks beforehand,
Kirill

/cc @randall77, @dr2chase

The text was updated successfully, but these errors were encountered:

josharian · 2017-03-25T21:46:15Z

cc @brtzsnr

rasky · 2018-03-13T03:10:15Z

I just submitted a CL that fixes the initial example.

The more complex example (hextable) has two additional problems: first, prove does not know how to handle loops; I have a solution coming for this though (which is merging loopbce into prove). Second, prove doesn't know how to handle math operations on indices or induction variables. This is harder.

Feel free to re-submit a new issue for the more complex case.

gopherbot · 2018-03-13T03:12:12Z

Change https://golang.org/cl/100277 mentions this issue: cmd/compile: in prove, add transitive closure of relations

navytux · 2018-03-13T08:07:48Z

@rasky thanks for taking a look at this problem.

navytux · 2018-05-01T09:15:59Z

@rasky, thanks again for your work on prove. I've moved simplified hex example to #25197.

josharian added the Performance label Mar 25, 2017

josharian added this to the Go1.9Maybe milestone Mar 25, 2017

josharian mentioned this issue May 18, 2017

cmd/compile: no way to hint to eliminate bounds checks in bvec.AndNot #20393

Closed

bradfitz added the NeedsFix The path to resolution is known, but the work has not been done. label Jun 28, 2017

bradfitz modified the milestones: Go1.10, Go1.9Maybe Jun 28, 2017

bradfitz modified the milestones: Go1.10, Go1.11 Nov 28, 2017

gopherbot closed this as completed in 5c40210 Apr 29, 2018

navytux mentioned this issue May 1, 2018

cmd/compile: BCE/Prove do not take arithmetic into account #25197

Open

golang locked and limited conversation to collaborators May 1, 2019

gopherbot added the FrozenDueToAge label May 1, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: BCE does not take transitivity into account #19714

cmd/compile: BCE does not take transitivity into account #19714

navytux commented Mar 25, 2017

josharian commented Mar 25, 2017

rasky commented Mar 13, 2018

gopherbot commented Mar 13, 2018

navytux commented Mar 13, 2018

navytux commented May 1, 2018

cmd/compile: BCE does not take transitivity into account #19714

cmd/compile: BCE does not take transitivity into account #19714

Comments

navytux commented Mar 25, 2017

What did you do?

What did you expect to see?

What did you see instead?

Does this issue reproduce with the latest release (go1.8)?

System details

josharian commented Mar 25, 2017

rasky commented Mar 13, 2018

gopherbot commented Mar 13, 2018

navytux commented Mar 13, 2018

navytux commented May 1, 2018