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

Jump to bottom

cmd/compile: a flaw in algebraic simplification rules inside Go compiler #37508

Open
true-grue opened this issue Feb 27, 2020 · 1 comment
Open

cmd/compile: a flaw in algebraic simplification rules inside Go compiler #37508

true-grue opened this issue Feb 27, 2020 · 1 comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@true-grue
Copy link

true-grue commented Feb 27, 2020 •
edited

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

$ go version
go version go1.14 windows/amd64

Does this issue reproduce with the latest release?

Yes.

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

go env Output
$ go env
set GO111MODULE=                                                                                                                                                                              set GOARCH=amd64                                                                                                                                                                              set GOBIN=                                                                                                                                                                                    set GOCACHE=C:\Users\Peter\AppData\Local\go-build                                                                                                                                             set GOENV=C:\Users\Peter\AppData\Roaming\go\env                                                                                                                                               set GOEXE=.exe                                                                                                                                                                                set GOFLAGS=                                                                                                                                                                                  set GOHOSTARCH=amd64                                                                                                                                                                          set GOHOSTOS=windows                                                                                                                                                                          set GOINSECURE=                                                                                                                                                                               set GONOPROXY=                                                                                                                                                                                set GONOSUMDB=                                                                                                                                                                                set GOOS=windows                                                                                                                                                                              set GOPATH=C:\Users\Peter\go                                                                                                                                                                  set GOPRIVATE=                                                                                                                                                                                set GOPROXY=https://proxy.golang.org,direct                                                                                                                                                   set GOROOT=D:\Programs\Go                                                                                                                                                                     set GOSUMDB=sum.golang.org                                                                                                                                                                    set GOTMPDIR=                                                                                                                                                                                 set GOTOOLDIR=D:\Programs\Go\pkg\tool\windows_amd64                                                                                                                                           set GCCGO=gccgo                                                                                                                                                                               set AR=ar                                                                                                                                                                                     set CC=gcc                                                                                                                                                                                    set CXX=g++                                                                                                                                                                                   set CGO_ENABLED=1                                                                                                                                                                             set GOMOD=                                                                                                                                                                                    set CGO_CFLAGS=-g -O2                                                                                                                                                                         set CGO_CPPFLAGS=                                                                                                                                                                             set CGO_CXXFLAGS=-g -O2                                                                                                                                                                       set CGO_FFLAGS=-g -O2                                                                                                                                                                         set CGO_LDFLAGS=-g -O2                                                                                                                                                                        set PKG_CONFIG=pkg-config                                                                                                                                                                     set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0 -fdebug-prefix-map=C:\Users\Peter\AppData\Local\Temp\go-build872647486=/tmp/go-build -gno-record-gcc-switches

What did you do?

package main

func foo(x int, y int, z int, abc int) int {
    return (((((1000 - x) + y) - z) - 10) + abc) - 42;
}

What did you expect to see?

I was expecting to see "abc - x + y - z + 948" as the result.

What did you see instead?

"".foo STEXT nosplit size=46 args=0x28 locals=0x0
    0x0000 00000 (1.go:5)   TEXT    "".foo(SB), NOSPLIT|ABIInternal, $0-40
    0x0000 00000 (1.go:5)   PCDATA  $0, $-2
    0x0000 00000 (1.go:5)   PCDATA  $1, $-2
    0x0000 00000 (1.go:5)   FUNCDATA    $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (1.go:5)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (1.go:5)   FUNCDATA    $2, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (1.go:6)   PCDATA  $0, $0
    0x0000 00000 (1.go:6)   PCDATA  $1, $0
    0x0000 00000 (1.go:6)   MOVQ    "".y+16(SP), AX
    0x0005 00005 (1.go:6)   MOVQ    "".x+8(SP), CX
    0x000a 00010 (1.go:6)   SUBQ    CX, AX
    0x000d 00013 (1.go:6)   ADDQ    $1000, AX
    0x0013 00019 (1.go:6)   MOVQ    "".z+24(SP), CX
    0x0018 00024 (1.go:6)   SUBQ    CX, AX
    0x001b 00027 (1.go:6)   MOVQ    "".abc+32(SP), CX
    0x0020 00032 (1.go:6)   LEAQ    (CX)(AX*1), AX
    0x0024 00036 (1.go:6)   LEAQ    -52(AX), AX
    0x0028 00040 (1.go:6)   MOVQ    AX, "".~r4+40(SP)
    0x002d 00045 (1.go:6)   RET

So clearly there is a room for improvement in rules of algebraic simplifications of the compiler.

I suggest to add/replace just a few of reassociate rules in the file "https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/gen/generic.rules". I made my own set of rules for add/sub combinations which could be used here:

    # x + (C - z) -> C + (x - z)
    # x - (z - C) -> C + (x - z)
    # x - (z + C) -> (x - z) - C
    # x - (C - z) -> (x + z) - C
    # (x + C) - z -> C + (x - z)
    # (C - x) - z -> C - (x - z)
    # C + (D - x) -> (C + D) - x
    # C + (x - D) -> (C - D) + x
    # C - (x - D) -> (C + D) - x
    # C - (D - x) -> (C - D) + x

I've tested them with my own compiler tools. Hope you will find them useful!
@randall77 randall77 added this to the Unplanned milestone Feb 27, 2020
@randall77
Copy link
Contributor

Yes, it looks like we need to merge constants from a sub and an outer add.
Here's the SSA form (just before lowering):

b1:-
v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr>
v8 (?) = LocalAddr <*int> {~r4} v2 v1
v9 (3) = Arg <int> {x} (x[int])
v10 (3) = Arg <int> {y} (y[int])
v11 (3) = Arg <int> {z} (z[int])
v12 (3) = Arg <int> {abc} (abc[int])
v14 (?) = Const64 <int> [1000]
v23 (4) = VarDef <mem> {~r4} v1
v13 (+4) = Sub64 <int> v10 v9
v4 (4) = Const64 <int> [-52]
v16 (4) = Add64 <int> v14 v13
v17 (4) = Sub64 <int> v16 v11
v6 (4) = Add64 <int> v12 v17
v22 (4) = Add64 <int> v4 v6
v24 (4) = Store <mem> {int} v8 v22 v23
Ret v24 (+4)

We want to merge the constants v14 and v4 somehow.

@cagedmantis cagedmantis changed the title A flaw in algebraic simplification rules inside Go compiler cmd/compile: a flaw in algebraic simplification rules inside Go compiler Feb 28, 2020
@cagedmantis cagedmantis added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 28, 2020
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@cagedmantis @true-grue @randall77 @gopherbot