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: Optimise branches that could be behind other branches, to avoid running those branches when known to be false #46711

Open
JAicewizard opened this issue Jun 11, 2021 · 7 comments
Open

cmd/compile: Optimise branches that could be behind other branches, to avoid running those branches when known to be false #46711

JAicewizard opened this issue Jun 11, 2021 · 7 comments
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
Backlog

Comments

@JAicewizard
Copy link

JAicewizard commented Jun 11, 2021 •
edited

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

$ go version 1.16.3

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
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/jaap/.cache/go-build"
GOENV="/home/jaap/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/jaap/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/jaap/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.16.5"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/jaap/Projects/posit/go.mod"
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-build1569966214=/tmp/go-build -gno-record-gcc-switches"

What did you do?

type ui uint32
func foo(a,b ui) ui{
  if a == 1<<31 || b.num == 1<<31 {
    return 1 << 31
  }
  
  aneg := a.num&(1<<(32-1)) != 0
  if aneg {
    a.num = ui(-int32(a.num))
  }
  
  xneg := aneg
  bneg := b.num&(1<<(32-1)) != 0
  if bneg {
    xneg = !xneg
    b.num = ui(-int32(b.num))
  }
  ... // lots more code
}

What did you expect to see?

I expected this code to be compiled to something equivalent to

func foo(a,b ui) ui{
  aneg := a.num&(1<<(32-1)) != 0
  if aneg {
    if a == 1<<31 {
      return 1 << 31
    }
    a.num = ui(-int32(a.num))
  }
  
  xneg := aneg
  bneg := b.num&(1<<(32-1)) != 0
  if bneg {
    if b.num == 1<<31 {
      return 1 << 31
    }
    xneg = !xneg
    b.num = ui(-int32(b.num))
  }
  ... // lots more code
}

to avoid checking for a == 1<<31 || b.num == 1<<31 when it is known to not be true.

Of course this is only possible when all the operations in between are known to not affect the return, or have any other side-effects.

What did you see instead?

This optimization is not applied.
@bcmills bcmills changed the title Optimise branches that could be behind other branches, to avoid running those branches when known to be false cmd/compile: Optimise branches that could be behind other branches, to avoid running those branches when known to be false Jun 11, 2021
@bcmills bcmills assigned bcmills and unassigned bcmills Jun 11, 2021
@bcmills bcmills added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance labels Jun 11, 2021
@bcmills bcmills added this to the Backlog milestone Jun 11, 2021
@bcmills
Copy link
Contributor

bcmills commented Jun 11, 2021

(CC @randall77)

@davecheney
Copy link
Contributor

In your example a and b are declared uint32, but they also appear to have fields, eg b.num. Is this code correct?

@JAicewizard
Copy link
Author

They are most definitely supposed to be uint32.
The code I copy pasted it from has them as a struct containing 1 field; num:uint32. After deciding it would be nicer for the issue to have a and b be uint32, I aperantly also immediately forgot about that.

@davecheney
Copy link
Contributor

That could be an important clue; sometimes the desugaring from field to value can defeat analysis

@JAicewizard
Copy link
Author

JAicewizard commented Jun 12, 2021 •
edited

I just tested, and it is also present with just a straight up uint32 (technically an alias). I updated the code to reflect the fact that its an alias.

EDIT:
fun fact, embeded in a struct the first example is slower than a straight up uint32 alias, but for the second example the embeded version is faster than a straight up uint32. Even though they both show a benefit.

@randall77
Copy link
Contributor

I'm not sure we should do this transformation in general. Whether this transformation helps depends on the input value distribution - if they are 1<<31 a lot of the time, the code is better as is.

@JAicewizard
Copy link
Author

There could be some analysis on if the branch is likely to be taken. IIRC this is already done in one way or another (like optimizing for the branch predictor?).

Then you could make a check that does this if it is determined the branch is highly unlikely, and a subset of another branch, and no returns in between that could be taken.

I dont know if this is something you want to do in the gc, where compilation performance is also important, that is up to you. But I think that you could make programs faster on average using this optimization at a certain threshold.

@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
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Backlog
Development

No branches or pull requests
5 participants
@davecheney @bcmills @randall77 @gopherbot @JAicewizard