Adding optimization documentation

[rybern]

Summary:

Stanc3's compiler optimizations are currently undocumented. I have created draft documentation, but I don't know where they should go.

Description:

Here is my draft of the optimization documentation: https://github.com/rybern/optimization-docs/blob/master/optimization-docs.md
Please let me know (A) how this draft can be improved, and (B) where I should fit them into the docs.

[SteveBronder]

Awesome! This circles back around to that there's not really a doxygen like solution for easily making docs for the compiler. Dune has a doc generator, but messing with it I've had trouble having both the public and private libraries documented in one site (the html it makes is also kind of ugly tbh)

I'm tempted to post a question on the ocaml subreddit to see how people handle this

[SteveBronder]

So for the optimization levels what if we phrased them like gcc where

1. Each optimization has the level it's turned on at (whether at all)
2. Each optimization level lists it's optimizations and has a line like

-O3 turns on all optimizations specified by -O2 and also turns on the following optimization flags:

To let users know O2 turns on all of O1 plus yadayada

It may be useful to cleanup the inline example. Even though that is the generated code, pseudo code may make it easier to understand what's happening there

[rybern]

Thanks Steve!

This circles back around to that there's not really a doxygen like solution for easily making docs for the compiler.

Yeah, I miss Haddock :(
Although we'll probably always need something like this doc to explain the user's options and how to use the interface. A Haddock-like solution would be great for actually documenting the code, which certainly needs doing too.

So for the optimization levels what if we phrased them like gcc where

Each optimization has the level it's turned on at (whether at all)
Each optimization level lists it's optimizations and has a line like
-O3 turns on all optimizations specified by -O2 and also turns on the following optimization flags:

Good idea, I'll do this

It may be useful to cleanup the inline example. Even though that is the generated code, pseudo code may make it easier to understand what's happening there

Yeah, I thought I would try to use a cleaned up version of the real mir-pretty printouts to prepare people to read those if they need to. I think most of them are readable, would it be sufficient to clean up or explain the function inlining example? There's some code generation I forgot to explain there (like why there's a loop).

[rok-cesnovar]

The docs are great! I think it would be better to group the descriptions by the proposed levels.

Would it be possible to have an unoptimized and optimized MIR side-by-side?

[SteveBronder]

Couple random Qs about the optims

• Doesn't expression propagation cause computation of the same thing multiple times?
• Is there a limit to the static loop unrolling? I imagine that could end up being bad if we unroll a 1:1000 loop
• gcc seems to do the opposite of Constant propagation with -fmerge-constants? Idk how those two would interact. Maybe it would let gcc have the opportunity to make some constants immediate
• gcc has an optim for inline functions only called once which may be nice for us as well to have in O1.

Are multiple passes of these optimizations performed if they are turned on?

[SteveBronder]

Also here's a weird one, a side side note. If a user told us a looping variable had a lower bound value of 4 like int<lower=4> N; we could unroll loops to give the compiler better opportunities for SIMD operations like

// pseudocode
N_mod = mod(N);
for (int i = 0; i < N - N_mod; ++i) {
  x[i] = y[i]
  x[i + 1] = y[i + 1]
  x[i + 2] = y[i + 2]
  x[i + 3] = y[i + 3]
}
// rest of loop
for (int i = N - N_mod; i < N; ++i) {
   x[i] = y[i];
}

[SteveBronder]

Yeah, I miss Haddock :(
Although we'll probably always need something like this doc to explain the user's options and how to use the interface. A Haddock-like solution would be great for actually documenting the code, which certainly needs doing too.

Yeah Haddock looks rad I've tried multiple times to get a nice doc solution for the compiler. I think what we need to do is to call the dune doc thing for both public and private, and then have I guess have a custom page that links to them? tbh could use something like bookdown or whatever to make the main page

[rybern]

The docs are great! I think it would be better to group the descriptions by the proposed levels.

Yeah, I think I'm going to combine yours and Steve's suggestion and organize by the optimizations that are added at each level.

Would it be possible to have an unoptimized and optimized MIR side-by-side?

Like physically side by side, as in a table? That might be cool. I didn't include the unoptimized MIR because I thought it would be too verbose and I knew I wanted to include the program.

[rybern]

Couple random Qs about the optims

• Doesn't expression propagation cause computation of the same thing multiple times?

Yep! That's why lazy code motion should be applied after expression propagation, it undoes that damage.

• Is there a limit to the static loop unrolling? I imagine that could end up being bad if we unroll a 1:1000 loop

There is no limit set, that could indeed be bad

• gcc seems to do the opposite of Constant propagation with -fmerge-constants? Idk how those two would interact. Maybe it would let gcc have the opportunity to make some constants immediate

Interesting, not sure what the answer is. Constant prop is still good for partial evaluation, but currently lazy code motion does not pull the constants back out (IIRC). Maybe it should, that would be an easy change.
Edit: yeah, looking at GCC, looks like LCM should factor out constants

• gcc has an optim for inline functions only called once which may be nice for us as well to have in O1.

This would require some work. It's currently done recursively in one pass (excluding recursive functions). Wouldn't be too hard if folks wanted it.

Are multiple passes of these optimizations performed if they are turned on?

Yes, some of them are. I think I mentioned it somewhere in the doc.

Also here's a weird one, a side side note. If a user told us a looping variable had a lower bound value of 4 like int<lower=4> N; we could unroll loops to give the compiler better opportunities for SIMD operations like

Yeah, could definitely do that. Taking better advantage of loop structure has some real possibilities.

I think what we need to do is to call the dune doc thing for both public and private, and then have I guess have a custom page that links to them? tbh could use something like bookdown or whatever to make the main page

That would be great, honestly whatever you're willing/able to put together would be highly appreciated.

[rok-cesnovar]

I didn't include the unoptimized MIR because I thought it would be too verbose and I knew I wanted to include the program.

The before/after comparison is easier to process for me at least.

[rybern]

@SteveBronder @rok-cesnovar Updated the doc draft with your suggestions: https://github.com/rybern/optimization-docs/blob/master/optimization-docs.md

I'd like to integrate this into the existing docs somewhere so that we can move this into a PR. Where do you think it should go?

[rok-cesnovar]

The docs look great! I think the before/after works nice. Makes it easy to understand.

I am not sure of the location, I am really not super familiar with this repository, to be honest. That is also more of a question for folks that have experience teaching Stan.

[SteveBronder]

I think the reference manual would be the right place for this. With all the compiler flags like diagnostic mode etc. maybe we should have a new section on compiler options

[SteveBronder]

Docs look good tho! One little thing

O3 includes optimizations specified by O1 and also:

O3 includes optimizations specified by O1 O2 and also: