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: constant evaluation could commute and associate #10931

Closed
josharian opened this issue May 22, 2015 · 4 comments
Closed

cmd/compile: constant evaluation could commute and associate #10931

josharian opened this issue May 22, 2015 · 4 comments
Labels
FrozenDueToAge Performance
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor 

func f(x int64) int64 { return x * 10 * 10 }

compiles to:

"".f t=1 size=32 value=0 args=0x10 locals=0x0
    0x0000 00000 (x.go:3)   TEXT    "".f(SB), $0-16
    0x0000 00000 (x.go:3)   FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0000 00000 (x.go:3)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (x.go:3)   MOVQ    "".x+8(FP), BX
    0x0005 00005 (x.go:3)   IMULQ   $10, BX
    0x0009 00009 (x.go:3)   IMULQ   $10, BX
    0x000d 00013 (x.go:3)   MOVQ    BX, "".~r1+16(FP)
    0x0012 00018 (x.go:3)   RET

Helping the compiler with a bit with associativity

func f(x int64) int64 { return x * (10 * 10) }

generates better code:

"".f t=1 size=16 value=0 args=0x10 locals=0x0
    0x0000 00000 (x.go:3)   TEXT    "".f(SB), $0-16
    0x0000 00000 (x.go:3)   FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0000 00000 (x.go:3)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0000 00000 (x.go:3)   MOVQ    "".x+8(FP), BX
    0x0005 00005 (x.go:3)   IMULQ   $100, BX
    0x0009 00009 (x.go:3)   MOVQ    BX, "".~r1+16(FP)
    0x000e 00014 (x.go:3)   RET

This is more pronounced (and more complicated) with division:

func f(x int64) int64 { return x * 100 / 10 }

generates:

"".f t=1 size=64 value=0 args=0x10 locals=0x0
    0x0000 00000 (x.go:3)   TEXT    "".f(SB), $0-16
    0x0000 00000 (x.go:3)   MOVQ    "".x+8(FP), BX
    0x0005 00005 (x.go:3)   FUNCDATA    $0, gclocals·23e8278e2b69a3a75fa59b23c49ed6ad(SB)
    0x0005 00005 (x.go:3)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0005 00005 (x.go:3)   MOVQ    BX, AX
    0x0008 00008 (x.go:3)   IMULQ   $100, BX
    0x000c 00012 (x.go:3)   IMULQ   $100, AX
    0x0010 00016 (x.go:3)   MOVQ    $7378697629483820647, R9
    0x001a 00026 (x.go:3)   MOVQ    AX, BP
    0x001d 00029 (x.go:3)   IMULQ   R9
    0x0020 00032 (x.go:3)   MOVQ    DX, R8
    0x0023 00035 (x.go:3)   SARQ    $2, R8
    0x0027 00039 (x.go:3)   SARQ    $63, BP
    0x002b 00043 (x.go:3)   SUBQ    BP, R8
    0x002e 00046 (x.go:3)   MOVQ    R8, "".~r1+16(FP)
    0x0033 00051 (x.go:3)   RET

Low priority.
@josharian josharian added this to the Unplanned milestone May 22, 2015
@josharian
Copy link
Contributor Author

Oops. Division does not associate like this, due to the possibility of overflow. Multiplication and addition stand. :)

@dr2chase
Copy link
Contributor

This might be fun to look into before SSA arrives, but simplification + reassociation-to-canonicalize-commons is definitely one of those things you do once you have SSA. I will point out however that one of my favorite stupid optimizer tricks from years ago was to convert ((long long int) x << 32) into x * 0x100000000LL .

@josharian josharian mentioned this issue Jun 12, 2015
Closed
@randall77
Copy link
Contributor

randall77 commented Oct 7, 2016 •
edited

Surprisingly, this is not fixed by SSA. The reason is that the rule to convert *10 into *5 *2 with a LEAQ (x)(x*4) and a SHL $1,xtriggers before the rule to combine two constant multiplies.

Constant multiply combining does work for other non-LEAQable multiplies. For instance, *19*19.

@ALTree
Copy link
Member

ALTree commented Jan 17, 2018

I tried these on tip

func F1(x int64) int64 { return x * 10 * 10 }
func F2(x int64) int64 { return 10 * x * 10 }
func F3(x int64) int64 { return 10 * 10 * x }

and they all generate a single IMULQ $100, so I'd say this is fixed.

@ALTree ALTree closed this as completed Jan 17, 2018
@golang golang locked and limited conversation to collaborators Jan 17, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@josharian @dr2chase @ALTree @randall77 @gopherbot