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: optimize x * const == const (and friends) #19655

Closed
josharian opened this issue Mar 22, 2017 · 5 comments
Closed

cmd/compile: optimize x * const == const (and friends) #19655

josharian opened this issue Mar 22, 2017 · 5 comments
Labels
FrozenDueToAge help wanted Performance Suggested Issues that may be good for new contributors looking for work to do.
Milestone
Go1.9Maybe

Comments

@josharian
Copy link
Contributor 

package p

func f(n int) bool {
	return n*8 == 64
}

Currently compiles to:

"".f t=1 size=21 args=0x10 locals=0x0
	0x0000 00000 (x.go:3)	TEXT	"".f(SB), $0-16
	0x0000 00000 (x.go:3)	FUNCDATA	$0, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB)
	0x0000 00000 (x.go:3)	FUNCDATA	$1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
	0x0000 00000 (x.go:4)	MOVQ	"".n+8(SP), AX
	0x0005 00005 (x.go:4)	SHLQ	$3, AX
	0x0009 00009 (x.go:4)	CMPQ	AX, $64
	0x000d 00013 (x.go:4)	SETEQ	AL
	0x0010 00016 (x.go:4)	MOVB	AL, "".~r1+16(SP)
	0x0014 00020 (x.go:4)	RET

Instead of multiplying (shifting), we should just compare to 8.

Real world example, from code I'm writing right now:

func (ctxt *Link) RegWidth() int {
	return ctxt.Arch.RegSize * 8
}

func foo(ctxt *Link) {
  if ctxt.RegWidth() == 64 {  // should inline and compile to ctxt.Arch.RegSize == 8
    // ...
  }
}

This is one of a family of generic optimizations. Care required in some cases (overflow, div by zero, etc.).

cc @randall77 @philhofer @martisch
@josharian josharian added help wanted Performance Suggested Issues that may be good for new contributors looking for work to do. labels Mar 22, 2017
@josharian josharian added this to the Go1.9Maybe milestone Mar 22, 2017
@mdempsky
Copy link
Member

I'm not entirely sure how much we can improve here, unfortunately.

C can optimize this because (signed) integer overflow is undefined behavior. Assuming x is a signed integer, x * 8 == 64 can only be true for x == 8.

In Go, if x is int32, then x * 8 == 64 is true for x == 8, but also x == 0x20000008, x == 0x40000008, etc.

@josharian
Copy link
Contributor Author

Indeed. I don't know why I thought we could in the first place.

@mvdan
Copy link
Member

mvdan commented Mar 22, 2017

Just a thought, but couldn't this be done if the Go compiler did some sort of value range propagation and could statically ensure no overflows?

I don't know if VRP is in the roadmap like SSA was, though.

@josharian
Copy link
Contributor Author

There's basic VRP around bounds check elimination. Larger VRP was considered and tabled because it didn't offer enough benefits for the compilation time.

@dr2chase
Copy link
Contributor

After we deal with many other things, it might make sense to revisit VRP. I think if we're careful about evaluation order, etc, we might be able to get the bang-for-buck high enough -- but that would be after we had args in registers, after we get better inlining turned on, after loop unrolling, etc.

@golang golang locked and limited conversation to collaborators Mar 23, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge help wanted Performance Suggested Issues that may be good for new contributors looking for work to do.
Projects
None yet
Milestone
Go1.9Maybe
Development

No branches or pull requests
5 participants
@mdempsky @josharian @dr2chase @mvdan @gopherbot