cmd/compile: Some bounds checks are not eliminated in arguments to append #19692

navytux · 2017-03-24T10:36:21Z

Please answer these questions before submitting your issue. Thanks!

What did you do?

Hello up there. Please consider the following function:

package xxx

const hex = "0123456789abcdef"

func AppendHexHi(buf []byte, b byte) []byte {
        return append(buf, hex[b >> 4])
}

(https://play.golang.org/p/-IHVJrTcq4)

When it is compiled the bounds check for hex[b >> 4] is not eliminated:

TEXT ·AppendHexHi(SB), $80-56 // bb.go:5
        // MOVQ    (TLS), CX (stack growth prologue)
        // CMPQ    SP, 16(CX)
        // JLS     206 
        // SUBQ    $80, SP
        // MOVQ    BP, 72(SP) (BP save)
        // LEAQ    72(SP), BP (BP init)
        // FUNCDATA $0, gclocals·564c88c798e834d77927d2fafb0b5dca(SB) (args)
        FUNCDATA   $1, gclocals·69c1753bd5f81501d95132d08af04464(SB) (locals)
        MOVBLZX    b+24(FP), AX  // bb.go:6
        SHRB       $4, AL 
        MOVBLZX    AL, AX
        CMPQ       AX, $16                                      <-- NOTE
        JCC        $0, pc199                                    <-- NOTE
        MOVQ       buf+8(FP), CX
        LEAQ       1(CX), DX
        LEAQ       go.string."0123456789abcdef"(SB), BX
        MOVBLZX    (BX)(AX*1), AX
        MOVQ       buf+16(FP), BX
        CMPQ       DX, BX
        JGT        $0, pc123
        MOVQ       buf+0(FP), SI
pc89:   
        MOVB       AL, (SI)(CX*1)
        MOVQ       SI, _r2+32(FP)
        MOVQ       DX, _r2+40(FP)
        MOVQ       BX, _r2+48(FP)
        // MOVQ    72(SP), BP (BP restore)
        // ADDQ    $80, SP (SP restore)
        RET
pc123:  
        MOVB       AL, _autotmp_3-1(SP)
        LEAQ       type.uint8(SB), SI
        MOVQ       SI, (SP)
        MOVQ       buf+0(FP), SI
        MOVQ       SI, 8(SP)
        MOVQ       CX, 16(SP)
        MOVQ       BX, 24(SP)
        MOVQ       DX, 32(SP)
        PCDATA     $0, $0 
        CALL       runtime.growslice(SB)
        MOVQ       40(SP), SI 
        MOVQ       48(SP), AX
        MOVQ       56(SP), BX
        LEAQ       1(AX), DX
        MOVBLZX    _autotmp_3-1(SP), AX
        MOVQ       buf+8(FP), CX
        JMP        pc89
pc199:
        // PCDATA  $0, $1 (stack growth)
        // CALL    runtime.panicindex(SB)                       <-- NOTE
        // UNDEF
        // NOP
        // PCDATA  $0, $-1       // bb.go:5
        // CALL    runtime.morestack_noctxt(SB)
        // JMP     0

However if I write it this way:

func AppendHexHi2(buf []byte, b byte) []byte {
        h := hex[b >> 4]
        return append(buf, h)
}

there is no bounds check generated:

#include "funcdata.h"

TEXT ·AppendHexHi2(SB), $80-56 // bb.go:17
        NO_LOCAL_POINTERS
        // MOVQ    (TLS), CX (stack growth prologue)
        // CMPQ    SP, 16(CX)
        // JLS     189
        // SUBQ    $80, SP
        // MOVQ    BP, 72(SP) (BP save)
        // LEAQ    72(SP), BP (BP init)
        // FUNCDATA $0, gclocals·d1dbd7a71866e7826348713921ec98d8(SB) (args)
        // FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) (no locals)
        MOVBLZX    b+24(FP), AX        // bb.go:18
        SHRB       $4, AL
        MOVBLZX    AL, AX
        LEAQ       go.string."0123456789abcdef"(SB), CX
        MOVBLZX    (CX)(AX*1), AX
        MOVQ       buf+8(FP), CX       // bb.go:19
        LEAQ       1(CX), DX
        MOVQ       buf+16(FP), BX
        CMPQ       DX, BX
        JGT        $0, pc113
        MOVQ       buf+0(FP), SI
pc79:
        MOVB       AL, (SI)(CX*1)
        MOVQ       SI, _r2+32(FP)
        MOVQ       DX, _r2+40(FP)
        MOVQ       BX, _r2+48(FP)
        // MOVQ    72(SP), BP (BP restore)
        // ADDQ    $80, SP (SP restore)
        RET
pc113:
        MOVB       AL, h-1(SP)         // bb.go:18
        LEAQ       type.uint8(SB), SI  // bb.go:19
        MOVQ       SI, (SP)
        MOVQ       buf+0(FP), SI
        MOVQ       SI, 8(SP)
        MOVQ       CX, 16(SP)
        MOVQ       BX, 24(SP)
        MOVQ       DX, 32(SP)
        PCDATA     $0, $0
        CALL       runtime.growslice(SB)
        MOVQ       40(SP), SI
        MOVQ       48(SP), AX
        MOVQ       56(SP), BX
        LEAQ       1(AX), DX
        MOVBLZX    h-1(SP), AX
        MOVQ       buf+8(FP), CX
        JMP        pc79
        // NOP (stack growth)
        // PCDATA  $0, $-1             // bb.go:17
        // CALL    runtime.morestack_noctxt(SB)
        // JMP     0

Bounds checking is also not generated for hex[b & 0xf] irregardless of where it is under append or not:

func AppendHexLo(buf []byte, b byte) []byte {
        return append(buf, hex[b & 0xf])
}

func AppendHexLo2(buf []byte, b byte) []byte {
        h := hex[b & 0xf]
        return append(buf, h)
}

Seem being under append affects only shifts.

What did you expect to see?

No bounds checking is generated for all cases.

What did you see instead?

Bounds checking was generated for append(buf, hex[b >> 4])

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

Yes, but there bounds checking is also emitted for AppendHexLo.

System details

go version devel +3e63cdf850 Fri Mar 24 06:59:33 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-build598453076=/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 +3e63cdf850 Fri Mar 24 06:59:33 2017 +0000 linux/amd64
GOROOT/bin/go tool compile -V: compile version devel +3e63cdf850 Fri Mar 24 06:59:33 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

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

josharian · 2017-03-24T16:40:21Z

cc @brtzsnr

josharian · 2017-05-18T20:04:25Z

I haven't dug into this, but I strongly suspect that the problem is that the argument to append gets assigned to a temp, and BCE doesn't propagate through the temp appropriately.

davidrjenni · 2017-05-19T16:50:08Z

For

func AppendHexHi2(buf []byte, b byte) []byte {
        h := hex[b >> 4]
        return append(buf, h)
}

the bounds check is eliminated here in the call to bounded.

In

func AppendHexHi(buf []byte, b byte) []byte { return append(buf, hex[b >> 4]) }

BCE does not work, because the right shift expression is assigned to a temp node (so the right node of the index expression is ONAME, not ORSH). and bounded cannot handle that.

Maybe someone can give a hint?

josharian · 2017-05-19T19:48:04Z

I think it just needs a new generic ssa rule along the lines of:

(IsInBounds (ZeroExt8to64 (Rsh8Ux64 _ (Const64 [c]))) (Const64 [d])) && 0 <= c && c <= 8 && 1<<uint(8-c)-1 < d -> (ConstBool [1])

I need to think a bit more to make sure this is right, though, and also generalize it to other widths and variants.

gopherbot · 2017-05-19T22:34:57Z

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

josharian · 2017-05-19T22:36:13Z

We may have missed the 1.9 window for these, not sure. Mailed a CL.

If/when that CL goes in, I plan to repurpose this issue to be able removing bounded from walk.go and doing all these optimizations in SSA form, which would have prevented this issue from arising in the first place. We're close on that--I think we just need to add some division-based rules and do some testing.

These rules trigger a few times during make.bash. When we eliminate boundedness checks from walk.go we'll rely on them more heavily. Updates golang#19692 Change-Id: I268c36ae2f1401c68dd685b15f2d30f5d6971176

These rules trigger a few times during make.bash. When we eliminate boundedness checks from walk.go we'll rely on them more heavily. Updates #19692 Change-Id: I268c36ae2f1401c68dd685b15f2d30f5d6971176 Reviewed-on: https://go-review.googlesource.com/43775 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>

aclements · 2018-05-18T18:27:33Z

@josharian, since this issue is pretty old, maybe open a new issue tracking the idea to move bounded into SSA and close this one?

josharian · 2018-05-31T03:33:41Z

I have some work in progress locally to move bounded into SSA. It's pretty close, just a few minor regalloc sticking points. So I'll close this now and not bother with a new issue. :) Thanks for the ping.

josharian added the Performance label Mar 24, 2017

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

bradfitz modified the milestones: Go1.9Maybe, Go1.10 Jul 20, 2017

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

bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

josharian closed this as completed May 31, 2018

golang locked and limited conversation to collaborators May 31, 2019

gopherbot added the FrozenDueToAge label May 31, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: Some bounds checks are not eliminated in arguments to append #19692

cmd/compile: Some bounds checks are not eliminated in arguments to append #19692

navytux commented Mar 24, 2017

josharian commented Mar 24, 2017

josharian commented May 18, 2017

davidrjenni commented May 19, 2017

josharian commented May 19, 2017

gopherbot commented May 19, 2017

josharian commented May 19, 2017

aclements commented May 18, 2018

josharian commented May 31, 2018

cmd/compile: Some bounds checks are not eliminated in arguments to append #19692

cmd/compile: Some bounds checks are not eliminated in arguments to append #19692

Comments

navytux commented Mar 24, 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 24, 2017

josharian commented May 18, 2017

davidrjenni commented May 19, 2017

josharian commented May 19, 2017

gopherbot commented May 19, 2017

josharian commented May 19, 2017

aclements commented May 18, 2018

josharian commented May 31, 2018