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 · 17 comments
Open

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

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

Comments

@markus-oberhumer
Copy link

@markus-oberhumer markus-oberhumer commented Sep 13, 2017

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
@gopherbot gopherbot added the Proposal label Sep 14, 2017
@odeke-em
Copy link
Member

@odeke-em odeke-em commented Sep 14, 2017

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

@randall77 randall77 commented Sep 14, 2017

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

@odeke-em odeke-em commented Sep 14, 2017

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

@markus-oberhumer markus-oberhumer commented Sep 21, 2017

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 markus-oberhumer commented Sep 21, 2017

(Wrong post - deleted).

@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 21, 2017

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

@markus-oberhumer markus-oberhumer commented Sep 21, 2017

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

@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 21, 2017

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

@markus-oberhumer markus-oberhumer commented Sep 21, 2017

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 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

@mdempsky mdempsky commented Nov 29, 2017

Seems like an optimization request. Bumping to 1.11.

@josharian
Copy link
Contributor

@josharian josharian commented Apr 23, 2020

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

@markus-oberhumer
Copy link
Author

@markus-oberhumer markus-oberhumer commented Apr 23, 2020

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@30e05d8

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

Cheers,
Markus

@josharian
Copy link
Contributor

@josharian josharian commented Apr 23, 2020

@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

@markus-oberhumer markus-oberhumer commented Apr 23, 2020

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

@markus-oberhumer markus-oberhumer commented Apr 23, 2020

@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

@josharian josharian commented Apr 23, 2020

Aye aye.

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.