cmd/compile: constant folding math/bits functions

[markus-oberhumer]

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]

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]

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]

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.

[markus-oberhumer]

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]

(Wrong post - deleted).

[randall77]

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]

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

[randall77]

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.