Signed non-negative divide by power of 2. #44530

xiyichan · 2021-02-23T07:55:46Z

What version of Go are you using (`go version`)?

$ go version
master

What operating system and processor architecture are you using (`go env`)?

go env Output

$ go env
GO111MODULE="on"
GOARCH="amd64"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/root/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://goproxy.io,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build079316562=/tmp/go-build -gno-record-gcc-switches"

What did you do?

package main
func main(){
        a(512)
        b(512)
}
func a(n int) int {
        i:=n/2
        return i
}
func b(n int) int {
        i:=n>>1
        return i
}

When I checked the source code in compile/ssa/gen/generic.rules l951, I found that function a should be optimized to b.

(Div8  n (Const8  [c])) && isNonNegative(n) && isPowerOfTwo8(c)  => (Rsh8Ux64  n (Const64 <typ.UInt64> [log8(c)]))
(Div16 n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo16(c) => (Rsh16Ux64 n (Const64 <typ.UInt64> [log16(c)]))
(Div32 n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo32(c) => (Rsh32Ux64 n (Const64 <typ.UInt64> [log32(c)]))
(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo64(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
(Div64 n (Const64 [-1<<63])) && isNonNegative(n)                 => (Const64 [0])

go tool compile -S main.go

What did you expect to see?

The same instructions should be used.

What did you see instead?

"".main STEXT nosplit size=1 args=0x0 locals=0x0 funcid=0x0
        0x0000 00000 (main.go:4)        TEXT    "".main(SB), NOSPLIT|ABIInternal, $0-0
        0x0000 00000 (main.go:4)        FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:4)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:7)        RET
        0x0000 c3                                               .
"".a STEXT nosplit size=24 args=0x10 locals=0x0 funcid=0x0
        0x0000 00000 (main.go:9)        TEXT    "".a(SB), NOSPLIT|ABIInternal, $0-16
        0x0000 00000 (main.go:9)        FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:9)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:10)       MOVQ    "".n+8(SP), AX
        0x0005 00005 (main.go:10)       MOVQ    AX, CX
        0x0008 00008 (main.go:10)       SHRQ    $63, AX
        0x000c 00012 (main.go:10)       ADDQ    CX, AX
        0x000f 00015 (main.go:10)       SARQ    $1, AX
        0x0012 00018 (main.go:11)       MOVQ    AX, "".~r1+16(SP)
        0x0017 00023 (main.go:11)       RET
        0x0000 48 8b 44 24 08 48 89 c1 48 c1 e8 3f 48 01 c8 48  H.D$.H..H..?H..H
        0x0010 d1 f8 48 89 44 24 10 c3                          ..H.D$..
"".b STEXT nosplit size=14 args=0x10 locals=0x0 funcid=0x0
        0x0000 00000 (main.go:13)       TEXT    "".b(SB), NOSPLIT|ABIInternal, $0-16
        0x0000 00000 (main.go:13)       FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:13)       FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (main.go:14)       MOVQ    "".n+8(SP), AX
        0x0005 00005 (main.go:14)       SARQ    $1, AX
        0x0008 00008 (main.go:15)       MOVQ    AX, "".~r1+16(SP)
        0x000d 00013 (main.go:15)       RET
        0x0000 48 8b 44 24 08 48 d1 f8 48 89 44 24 10 c3        H.D$.H..H.D$..

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

ALTree · 2021-02-23T08:14:04Z

The two functions give different results when called with a negative number, so they're not equivalent. Of course in this case you're calling them with a positive argument, but they need to be compiled to handle every possible input.

xiyichan · 2021-02-23T08:21:24Z

The two functions give different results when called with a negative number, so they're not equivalent. Of course in this case you're calling them with a positive argument, but they need to be compiled to handle every possible input.

I can understand that.But I don't know how this optimization is reflected in the code.But I test that unsigned divided by 2 works.

ALTree · 2021-02-23T08:24:09Z

So can you expand on what issue are you seeing in the generated code? It's true that a and b are compiled differently, but that's expected.

ALTree · 2021-02-23T08:27:52Z

Oh you wanted to know when that SSA rule is triggered. For example, when the input and output arguments are of uint type (instead of int), both functions are compiled to a SHRQ, as you noticed.

xiyichan · 2021-02-23T08:35:17Z

Oh you wanted to know when that SSA rule is triggered. For example, when the input and output arguments are of uint type (instead of int), both functions are compiled to a SHRQ, as you noticed.

In this ssa,It can be triggered if the int is not negative.There are other rules that optimize uint.

// Unsigned divide by power of 2.  Strength reduce to a shift.
(Div8u  n (Const8  [c])) && isPowerOfTwo8(c)  => (Rsh8Ux64  n (Const64 <typ.UInt64> [log8(c)]))
(Div16u n (Const16 [c])) && isPowerOfTwo16(c) => (Rsh16Ux64 n (Const64 <typ.UInt64> [log16(c)]))
(Div32u n (Const32 [c])) && isPowerOfTwo32(c) => (Rsh32Ux64 n (Const64 <typ.UInt64> [log32(c)]))
(Div64u n (Const64 [c])) && isPowerOfTwo64(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
(Div64u n (Const64 [-1<<63]))                 => (Rsh64Ux64 n (Const64 <typ.UInt64> [63]))

// Signed non-negative divide by power of 2.
(Div8  n (Const8  [c])) && isNonNegative(n) && isPowerOfTwo8(c)  => (Rsh8Ux64  n (Const64 <typ.UInt64> [log8(c)]))
(Div16 n (Const16 [c])) && isNonNegative(n) && isPowerOfTwo16(c) => (Rsh16Ux64 n (Const64 <typ.UInt64> [log16(c)]))
(Div32 n (Const32 [c])) && isNonNegative(n) && isPowerOfTwo32(c) => (Rsh32Ux64 n (Const64 <typ.UInt64> [log32(c)]))
(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo64(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
(Div64 n (Const64 [-1<<63])) && isNonNegative(n)                 => (Const64 [0])

randall77 · 2021-02-23T15:51:47Z

// Signed divide by power of 2.
// n / c =       n >> log(c) if n >= 0
//       = (n+c-1) >> log(c) if n < 0
// We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
(Div8  <t> n (Const8  [c])) && isPowerOfTwo8(c) =>
  (Rsh8x64
    (Add8  <t> n (Rsh8Ux64  <t> (Rsh8x64  <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [int64( 8-log8(c))])))
    (Const64 <typ.UInt64> [int64(log8(c))]))
(Div16 <t> n (Const16 [c])) && isPowerOfTwo16(c) =>
  (Rsh16x64
    (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [int64(16-log16(c))])))
    (Const64 <typ.UInt64> [int64(log16(c))]))
(Div32 <t> n (Const32 [c])) && isPowerOfTwo32(c) =>
  (Rsh32x64
    (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [int64(32-log32(c))])))
    (Const64 <typ.UInt64> [int64(log32(c))]))
(Div64 <t> n (Const64 [c])) && isPowerOfTwo64(c) =>
  (Rsh64x64
    (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [int64(64-log64(c))])))
    (Const64 <typ.UInt64> [int64(log64(c))]))

xiyichan · 2021-02-23T16:03:20Z

// Signed divide by power of 2.
// n / c =       n >> log(c) if n >= 0
//       = (n+c-1) >> log(c) if n < 0
// We conditionally add c-1 by adding n>>63>>(64-log(c)) (first shift signed, second shift unsigned).
(Div8  <t> n (Const8  [c])) && isPowerOfTwo8(c) =>
  (Rsh8x64
    (Add8  <t> n (Rsh8Ux64  <t> (Rsh8x64  <t> n (Const64 <typ.UInt64> [ 7])) (Const64 <typ.UInt64> [int64( 8-log8(c))])))
    (Const64 <typ.UInt64> [int64(log8(c))]))
(Div16 <t> n (Const16 [c])) && isPowerOfTwo16(c) =>
  (Rsh16x64
    (Add16 <t> n (Rsh16Ux64 <t> (Rsh16x64 <t> n (Const64 <typ.UInt64> [15])) (Const64 <typ.UInt64> [int64(16-log16(c))])))
    (Const64 <typ.UInt64> [int64(log16(c))]))
(Div32 <t> n (Const32 [c])) && isPowerOfTwo32(c) =>
  (Rsh32x64
    (Add32 <t> n (Rsh32Ux64 <t> (Rsh32x64 <t> n (Const64 <typ.UInt64> [31])) (Const64 <typ.UInt64> [int64(32-log32(c))])))
    (Const64 <typ.UInt64> [int64(log32(c))]))
(Div64 <t> n (Const64 [c])) && isPowerOfTwo64(c) =>
  (Rsh64x64
    (Add64 <t> n (Rsh64Ux64 <t> (Rsh64x64 <t> n (Const64 <typ.UInt64> [63])) (Const64 <typ.UInt64> [int64(64-log64(c))])))
    (Const64 <typ.UInt64> [int64(log64(c))]))

I think int c >= 0 will use Signed non-negative divide by power of 2.
Now, when two variables are integer constants and >=0 will use Signed non-negative divide by power of 2.
Thank you very much.

randall77 · 2021-02-23T16:08:41Z

I'm afraid I don't understand what you're asking.
Is there a bug somewhere? Are you just trying to figure out the code?

ALTree · 2021-02-23T16:11:19Z

Oh, I think I got it. OP wants to know what kind of code will triggers this kind of rules:

(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo64(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))

Since

func a(n int) int {
        i:=n/2
        return i
}

doesn't, but also replacing with uint triggers different rules (the Div64u ones I believe?).

xiyichan · 2021-02-23T16:17:06Z

I'm afraid I don't understand what you're asking.
Is there a bug somewhere? Are you just trying to figure out the code?

I want to know when this rule(Signed non-negative divide by power of 2) is triggered?

xiyichan · 2021-02-23T16:19:48Z

Oh, I think I got it. OP wants to know what kind of code will triggers this kind of rules:
(Div64 n (Const64 [c])) && isNonNegative(n) && isPowerOfTwo64(c) => (Rsh64Ux64 n (Const64 <typ.UInt64> [log64(c)]))
Since
func a(n int) int {
        i:=n/2
        return i
}
doesn't, but also replacing with uint triggers different rules (the Div64u ones I believe?).

I've tried a lot of code and haven't triggered this rule yet. So I'm very curious about the circumstances that trigger this rule.

randall77 · 2021-02-23T16:44:01Z

len(s)/2 should trigger it. Or any other provably nonnegative value listed in cmd/compile/internal/ssa/prove.go:isNonNegative.

xiyichan · 2021-02-23T16:46:27Z

len(s)/2 should trigger it. Or any other provably nonnegative value listed in cmd/compile/internal/ssa/prove.go:isNonNegative.

thanks. i will try it

ALTree · 2021-02-23T16:48:43Z

The rules are triggered several times when compiling the standard library. I have verified that this line in the bytes package: https://github.com/golang/go/blob/master/src/bytes/buffer.go#L132

	c := cap(b.buf)
	if n <= c/2-m {

triggers the Div64 one.

Closing here since we don't use the issue tracker for questions.

xiyichan closed this as completed Feb 23, 2021

xiyichan reopened this Feb 23, 2021

ALTree closed this as completed Feb 23, 2021

golang locked and limited conversation to collaborators Feb 23, 2022

gopherbot added the FrozenDueToAge label Feb 23, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Signed non-negative divide by power of 2. #44530

Signed non-negative divide by power of 2. #44530

xiyichan commented Feb 23, 2021

ALTree commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021 •

edited

Loading

ALTree commented Feb 23, 2021

ALTree commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021 •

edited

Loading

randall77 commented Feb 23, 2021

xiyichan commented Feb 23, 2021 •

edited

Loading

randall77 commented Feb 23, 2021

ALTree commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021

xiyichan commented Feb 23, 2021

randall77 commented Feb 23, 2021

xiyichan commented Feb 23, 2021

ALTree commented Feb 23, 2021 •

edited

Loading

Signed non-negative divide by power of 2. #44530

Signed non-negative divide by power of 2. #44530

Comments

xiyichan commented Feb 23, 2021

What version of Go are you using (go version)?

What operating system and processor architecture are you using (go env)?

What did you do?

What did you expect to see?

What did you see instead?

ALTree commented Feb 23, 2021 • edited Loading

xiyichan commented Feb 23, 2021 • edited Loading

ALTree commented Feb 23, 2021

ALTree commented Feb 23, 2021 • edited Loading

xiyichan commented Feb 23, 2021 • edited Loading

randall77 commented Feb 23, 2021

xiyichan commented Feb 23, 2021 • edited Loading

randall77 commented Feb 23, 2021

ALTree commented Feb 23, 2021 • edited Loading

xiyichan commented Feb 23, 2021

xiyichan commented Feb 23, 2021

randall77 commented Feb 23, 2021

xiyichan commented Feb 23, 2021

ALTree commented Feb 23, 2021 • edited Loading

What version of Go are you using (`go version`)?

What operating system and processor architecture are you using (`go env`)?

ALTree commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021 •

edited

Loading

ALTree commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021 •

edited

Loading

xiyichan commented Feb 23, 2021 •

edited

Loading

ALTree commented Feb 23, 2021 •

edited

Loading

ALTree commented Feb 23, 2021 •

edited

Loading