Repository: go
Issue: cmd/compile: enhancements to the gc inliner and optimizer
Labels: compiler/runtime

**Background**
I recently tried optimizing some hash functions in Go to find out what is possible without resorting to using assembler. I knew gc had an "inliner" but I didn't have any experience with it. I spent some time reading the "inl.c" code.

**Summary**
Go's inliner seems to work well and I got speed increase of 30% on some hash functions using it. However, the way it is currently configured and controlled effectively turns if off for most cases. Most users won't figure out how to set the `level` (-gcflags="-l -l -l -l -l -l -m") and even less will be willing to recompile the tool chain to change the _hard coded_ `hairiness` variable set to more than 40. The inliner would be more effective if it could handle closures and variadic functions. Finally, a simple idiom recognizer would allow a simple function such as `rot()` to be turned into a single instruction. Taken together these  changes could yield significant performance improvements to certain kinds of Go packages.

Here are my impressions, suggestions, and requests:

A simple code example is here, it's just one one Jenkin's Hash functions:
https://play.golang.org/p/rmDG7MR5F9
This comes from:
https://github.com/tildeleb/hashland/blob/master/jenkins/jenkins.go
The main project is:
https://github.com/tildeleb/hashland/

**Observations and Impressions**
1. The inliner works pretty well but you need to add the following flags to build to get it work:
`go build -gcflags="-l -l -l -l -l -l -m"`
1. .The inliner has  budget for the complexity of functions it is willing to inline. The variable is called `hairiness`. It is current set to 40 and that's not very hairy. In the example above. I had to break `mix()` and `final()` into 3 functions of two lines each, to get them to inline. 40 really seems like a very small budget to me. Hard coding a parameter like this is just wrong.
2. Currently closures can't be inlined. Using the example above, that means the closures `mix()` and `final()` which close over the hash state variables a, b, and c need to moved out of the function "HashWords". Since the state variables a, b, and c are lo longer closed over they need to be passed to and returned from the `mix()` and `final() functions`. For example:
   `a, b, c = mix(a, b, c)`. If all hash functions had 3 state variables that might be OK.

However, other more advanced hash functions have more state. For example in Jenkin's SpookyV2 I had to write:
`h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11 = Mix(inul, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11)`

Which I hope we can all agree is out of control and is why I believe why closures are the preferred solution to many inlining based use cases.

The downside of the closures is that if you have multiple versions of a hash function that use the same mix() and final() code, those closures need to be duplicated inside the top level functions.

Again, I prefer the closures. The source code is cleaner, easier to read, and probably easier to optimize because the optimizer doesn't need to optimize out the calling and return stack push/pop sequences to get good code quality.
1. Go needs an idiom recognizer. Consider the example again. The function `rot(x, k)` gets inlined but it doesn't generate a rot insturction. Other compilers are able to do this. Actually, I think a case can be made to add a rotate (no carry)  operator (`>>>` or `<<<`) to the language for this particular case, but that's another "issue" as they say. BTW Go generates about 22 instructions to get the rotate done.
2. Variadic functions aren't inlined. I am considering proposing the following as a new interface for hash functions that would be complementary to the current hash streaming interface.
   
   `Hash32(b []byte, seeds ...uint32) uint32`  
   `Hash64(b []byte, seeds ...uint64) uint64`  
   `Hash128(b []byte, seeds ...uint64) (uint64, uint64)`  
   `Hash(in []byte, out []byte, seeds ...uint64) []byte`  

Because of this I would like to see inlining of variadic functions.

FWIW I still have to benchmark this vs other alternative calling sequences.

**Suggestions**
1. Increase the default "hairiness" from 40. 40 really isn't very much. Set the default "level" to a value higher that 0 or 1.
2. Optimizer command line flags.
   In the short term add temporary native command line flags to set `hairiness` and `level.` I know the Go team eschews command line flags but some control over the optimization process has been around since the unix epoch and is probably inevitable.

For example:
`% go build -ilbudget=120 illevel=6`
1. Extend the inliner to inline closures and variadic functions.
2. Over the medium term add a simple idiom recognizer so common idioms such as `rot` in the example above can be turned into single instructions, really (2-3 instructions counting the `MOVQ` to the registers instead of the 20+ now generated to get a rot.
3. Consider adding a rot operator to the language.