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

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

Comments

Projects
None yet
5 participants
@josharian
Copy link
Contributor

commented Mar 22, 2017

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

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 22, 2017

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

This comment has been minimized.

Copy link
Contributor Author

commented Mar 22, 2017

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

@josharian josharian closed this Mar 22, 2017

@mvdan

This comment has been minimized.

Copy link
Member

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

This comment has been minimized.

Copy link
Contributor Author

commented Mar 22, 2017

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

This comment has been minimized.

Copy link
Contributor

commented Mar 23, 2017

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.
You can’t perform that action at this time.