Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
navytux opened this issue Mar 24, 2017 · 8 comments

Comments

Projects
None yet
6 participants
@navytux
Copy link
Contributor

commented Mar 24, 2017

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

@josharian

This comment has been minimized.

Copy link
Contributor

commented Mar 24, 2017

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

@josharian

This comment has been minimized.

Copy link
Contributor

commented May 18, 2017

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

This comment has been minimized.

Copy link
Contributor

commented May 19, 2017

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

This comment has been minimized.

Copy link
Contributor

commented May 19, 2017

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

This comment has been minimized.

Copy link

commented May 19, 2017

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

@josharian

This comment has been minimized.

Copy link
Contributor

commented May 19, 2017

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.

josharian added a commit to josharian/go that referenced this issue May 23, 2017

cmd/compile: use right shifts to eliminate bounds checks
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

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

gopherbot pushed a commit that referenced this issue Aug 9, 2017

cmd/compile: use right shifts to eliminate bounds checks
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>

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

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

@aclements

This comment has been minimized.

Copy link
Member

commented May 18, 2018

@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

This comment has been minimized.

Copy link
Contributor

commented May 31, 2018

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 josharian closed this May 31, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.