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: constant folding math/bits functions #21872

Open
markus-oberhumer opened this issue Sep 13, 2017 · 20 comments
Open

cmd/compile: constant folding math/bits functions #21872

markus-oberhumer opened this issue Sep 13, 2017 · 20 comments
Labels
help wanted Performance Suggested Issues that may be good for new contributors looking for work to do.
Milestone

Comments

@markus-oberhumer
Copy link

What version of Go are you using (go version)?

Current git master 5779677

What did you expect to see?

There is a very easy optimization possibility of constant folding various functions from math/bits.

Would there be interest in implementing these?

Personally, I could work on this, but I'm pretty new to the compiler internals and don't have a CLA yet.

$ git diff 577967799c22e5a443ec49f494039f80e08202fe

diff --git a/src/cmd/compile/internal/ssa/gen/generic.rules b/src/cmd/compile/internal/ssa/gen/generic.rules
index 92b5b04962..7a81712ccc 100644
--- a/src/cmd/compile/internal/ssa/gen/generic.rules
+++ b/src/cmd/compile/internal/ssa/gen/generic.rules
@@ -142,6 +142,14 @@
 (Div32F (Const32F [c]) (Const32F [d])) -> (Const32F [f2i(float64(i2f32(c) / i2f32(d)))])
 (Div64F (Const64F [c]) (Const64F [d])) -> (Const64F [f2i(i2f(c) / i2f(d))])
 
+// TODO: add more functions from math.bits here
+(BitLen32 (Const32 [c])) && config.PtrSize == 4 -> (Const32 [int64(bits.Len32(uint32(c)))])
+(BitLen32 (Const32 [c])) && config.PtrSize == 8 -> (Const64 [int64(bits.Len32(uint32(c)))])
+(BitLen64 (Const64 [c])) && config.PtrSize == 4 -> (Const32 [int64(bits.Len64(uint64(c)))])
+(BitLen64 (Const64 [c])) && config.PtrSize == 8 -> (Const64 [int64(bits.Len64(uint64(c)))])
+// TODO: is there a "ConstInt" to avoid "PtrSize" checks and simplify the rules above ?
+// TODO: do we have to reimplement math.bits in the compiler because of bootstrap issues ?
+
 // Convert x * 1 to x.
 (Mul8  (Const8  [1]) x) -> x
 (Mul16 (Const16 [1]) x) -> x
diff --git a/src/cmd/compile/internal/ssa/gen/rulegen.go b/src/cmd/compile/internal/ssa/gen/rulegen.go
index c23a54d9b5..e7dc2b39af 100644
--- a/src/cmd/compile/internal/ssa/gen/rulegen.go
+++ b/src/cmd/compile/internal/ssa/gen/rulegen.go
@@ -155,10 +155,12 @@ func genRules(arch arch) {
        fmt.Fprintln(w)
        fmt.Fprintln(w, "package ssa")
        fmt.Fprintln(w, "import \"math\"")
+       fmt.Fprintln(w, "import \"math/bits\"")
        fmt.Fprintln(w, "import \"cmd/internal/obj\"")
        fmt.Fprintln(w, "import \"cmd/internal/objabi\"")
        fmt.Fprintln(w, "import \"cmd/compile/internal/types\"")
        fmt.Fprintln(w, "var _ = math.MinInt8  // in case not otherwise used")
+       fmt.Fprintln(w, "var _ = bits.UintSize // in case not otherwise used")
        fmt.Fprintln(w, "var _ = obj.ANOP      // in case not otherwise used")
        fmt.Fprintln(w, "var _ = objabi.GOROOT // in case not otherwise used")
        fmt.Fprintln(w, "var _ = types.TypeMem // in case not otherwise used")
@odeke-em odeke-em changed the title cmd/compile: constant folding math/bits functions (proposal) proposal: cmd/compile: constant folding math/bits functions Sep 14, 2017
@gopherbot gopherbot added this to the Proposal milestone Sep 14, 2017
@odeke-em
Copy link
Member

Thank you @markus-oberhumer for the proposal and for offering to work on it, very much appreciated to have contributors jump on board, welcome to the Go project!

So as you noticed, in deed that CLA would be necessary to review changes, please sign it if you can.
In the meantime I'll ping @randall77 @cherrymui.

@randall77
Copy link
Contributor

Yes, this optimization sounds like a good idea.
The config.PtrSize tests are unfortunate. It would be nice if we could reorganize the introduction of these ops in cmd/compile/internal/gc/ssa.go to make them unnecessary. I can't think of anything off the top of my head, however. @griesemer : do you remember why it is organized this way (the output size of the BitLen* ops being implicit)?

@odeke-em I think this is too small to be considered as a proposal. Just do it™®.

@odeke-em
Copy link
Member

Ahaha roger that @randall77 Just do it™® #ShiaLaBeouf.

Sure, I'll update the title as this is something that can be done with a CL, and has been accepted.

@odeke-em odeke-em changed the title proposal: cmd/compile: constant folding math/bits functions cmd/compile: constant folding math/bits functions Sep 14, 2017
@odeke-em odeke-em removed the Proposal label Sep 14, 2017
@odeke-em odeke-em modified the milestones: Proposal, Go1.10 Sep 14, 2017
@markus-oberhumer
Copy link
Author

I now have my Gerrit account and CLA ready, so I've started working on this optimization.

Implementation is indeed straightforward, but I've noticed some suprising issue while adding the test cases:

Choosing which functions are considered intrinsics in src/cmd/compile/internal/gc/ssa.go is made under consideration if an arch has efficient runtime instructions for handling that function, so any SSA constant folding is only made for specific archs.

For example, math.Sqrt(16.0) is not computed at compile time for GOARCH=386 because math.Sqrt is not considered an intrinsic for sys.I386.

I'm just wondering if this is a known issue and if there are any plans of improving this. Thanks!

@markus-oberhumer
Copy link
Author

markus-oberhumer commented Sep 21, 2017

(Wrong post - deleted).

@randall77
Copy link
Contributor

For example, math.Sqrt(16.0) is not computed at compile time for GOARCH=386 because math.Sqrt is not considered an intrinsic for sys.I386.
I'm just wondering if this is a known issue and if there are any plans of improving this. Thanks!

This hasn't really been an issue before. I suppose I would chalk it up to "unfortunate". You might be able to add an additional "argument is a constant" check which triggers intrinsification regardless of arch, but that would be an imperfect check at Node->SSA time.

Doesn't seem worth the trouble to fix.

@markus-oberhumer
Copy link
Author

Ok, thanks, but then unfortunately many archs will be missing the new constant-time optimizations.

@randall77
Copy link
Contributor

I think all the archs aside from 386 should be able to do all the intrinsics. It just hasn't been implemented yet for some of them.

Another option is to always do the intrinsic, and convert back to a call for those archs which can't do the intrinsic. That would allow your optimization to trigger in all cases.

That would be a lot of work, though.

@markus-oberhumer
Copy link
Author

I think all the archs aside from 386 should be able to do all the intrinsics. It just hasn't been implemented yet for some of them.

Well, for example math.bits Reverse64() will only be constant-folded for GOARCH=arm64, because no other CPU has a RBIT instruction.

But I agree that changing this would be a lot of work (and a much better understanding of the compiler than I have right now).

@odeke-em
Copy link
Member

odeke-em commented Nov 6, 2017

How's it going here @markus-oberhumer and @randall77? It's just your friendly Go triager :)

@mdempsky mdempsky modified the milestones: Go1.10, Go1.11 Nov 29, 2017
@mdempsky
Copy link
Member

Seems like an optimization request. Bumping to 1.11.

@josharian josharian added Suggested Issues that may be good for new contributors looking for work to do. Performance help wanted labels Apr 25, 2018
@bradfitz bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018
@josharian
Copy link
Contributor

We started constant folding bits.TrailingZeros as part of 1.15.

@markus-oberhumer
Copy link
Author

Actually I did implement this 2 years ago, but I never found the energy to start using Gerrit...

In any case the implementation is as simple as outlined in my initial post.

And just in case anybody is interested, I've pushed my work (based on the go1.13 branch) to Github - please see

https://github.com/markus-oberhumer/golang--go/commits/constant-fold-math-bits--go1.13

and the actual commit at

markus-oberhumer-forks@30e05d8

A few test cases are still missing, but otherwise this should be complete.

Cheers,
Markus

@josharian
Copy link
Contributor

@markus-oberhumer thanks. Have you signed a CLA? Without that I'm afraid we can't look at your commit. If you have, and you don't mind, I can get your work incorporated, although the commit will be in my name. (I can credit you in the commit message.)

Alternatively, the Go project now accepts GitHub PRs...

@markus-oberhumer
Copy link
Author

Yes, I did sign the CLA back in 2017 and have a Gerrit account.

But as mentioned I never found the energy to actually start using Gerrit...

@markus-oberhumer
Copy link
Author

@josharian Please use whatever parts you find useful from my commit - this is much less work than me starting to rebase the commit to go1.15 and going through the review process.

Thanks!

@josharian
Copy link
Contributor

Aye aye.

Can a Googler (@ianlancetaylor maybe) check CLA status for me, just to confirm? Thanks.

@egonelbre
Copy link
Contributor

I can send a CL with the fixes and added tests - but CLA might still need to be checked.

@markus-oberhumer
Copy link
Author

JFTR, my account at https://cla.developers.google.com/clas says: "Google Individual CLA" signed "Sep 14, 2017 03:27 PDT".

@gopherbot
Copy link

Change https://golang.org/cl/280453 mentions this issue: cmd/compile/internal/ssa: constant fold some math/bits operations

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Performance Suggested Issues that may be good for new contributors looking for work to do.
Projects
None yet
Development

No branches or pull requests

8 participants