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: 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

Comments

@JAicewizard
Copy link

@JAicewizard JAicewizard commented Jun 11, 2021

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 this to the Backlog milestone Jun 11, 2021
@bcmills
Copy link
Member

@bcmills bcmills commented Jun 11, 2021

(CC @randall77)

@davecheney
Copy link
Contributor

@davecheney davecheney commented Jun 12, 2021

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

@JAicewizard JAicewizard commented Jun 12, 2021

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

@davecheney davecheney commented Jun 12, 2021

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

@JAicewizard
Copy link
Author

@JAicewizard JAicewizard commented Jun 12, 2021

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

@randall77 randall77 commented Jun 23, 2021

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

@JAicewizard JAicewizard commented Jun 24, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants