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

Created on 22 Mar 2017 · 5Comments · Source: golang/go

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

FrozenDueToAge Performance Suggested help wanted

Source

josharian

Most helpful comment

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.

mdempsky on 22 Mar 2017

👍3

All 5 comments

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.

mdempsky on 22 Mar 2017

👍3

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

josharian on 22 Mar 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.

mvdan on 22 Mar 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.

josharian on 22 Mar 2017

👍1

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.