I saw you message @tjakway; I'll have a look at this tomorrow.

This is looking like a great start. However, a few things,

• The new flag -fannotate-loops will need documentation in docs/users-guide/using-optimization.rst
• In GHC we have a tradition of writing Notes, comments which provide an overview of the various moving parts of a new feature. Could you write a Note for this (perhaps in LoopAnnotations.hs). See [https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/typecheck/TcTypeable.hs;34e3523354916b0fb8a0dc93041d25812f7e6181$34), for an example.

I'll happily do a more in-depth substantive review once the note is in place.

RegAlloc unit tests are failing right now

@tjakway, how is this going? Is there any way I can help?

I ran benchmarks comparing this patch vs. master (2be55b85):

• with no flags
• with -fannotate-loops (linear allocator + enable optimization)
• with -fregs-graph -fannotate-loops (graph allocator + enable optimization)

The benchmark on master was not run with any extra flags.
All the percents are vs. running nofib on master.

Some observations:

• The majority of the speed-up seems to be from RegAlloc.Linear.SpillCost, which ironically I only wrote because weighting loops requires some measure of spill cost in the first place. It just counts how many times a register was used in a basic block then spills the least-used one, which appears to give a speed-up of 4.1%.
• Patch with loop annotations had a slightly worse mean runtime (-4.1%) vs. patch without loop annotations (-4.3%) but a slightly better min (-51.6% vs. -50.3%). Not sure if this is close enough to be definitive.
• Code size was not affected, which is good. The patch doesn’t change the number of spills so if we ended up with larger executables that would be strange.
• Is something up with exact-reals? Got

warning: dubious run time results for exact-reals [...]
warning: dubious mut time results for exact-reals [...]{F1492031}

at the top of all the comparisons. I’ll have to look at that.

• The graph allocator with the optimization is slower (-3.4%) than both linear runs (-4.1% and -4.3%) but still better than master.

Also: will need to verify this, but it shouldn't slow down compilation if -O <2 because the spillQuickly path will be taken through linearSpill which preserves the behavior of HEAD (i.e. spill whichever reg we find first without performing any cost measures).

Yay! I'm happy to see you pick this up again.

Patch with loop annotations had a slightly worse mean runtime (-4.1%) vs. patch without loop annotations (-4.3%) but a slightly better min (-51.6% vs. -50.3%). Not sure if this is close enough to be definitive.

Interesting. Were there significant regressions due to the annotations?

In D2903#114535, @bgamari wrote:

Yay! I'm happy to see you pick this up again.

Patch with loop annotations had a slightly worse mean runtime (-4.1%) vs. patch without loop annotations (-4.3%) but a slightly better min (-51.6% vs. -50.3%). Not sure if this is close enough to be definitive.

Interesting. Were there significant regressions due to the annotations?

The relevant data from master_vs_annotate_loops.txt:

           Min           -51.6%
           Max            +5.6% 
Geometric Mean            -4.1%

The benchmarks with regressions are:

• CSD (+2.0%)
• fannkuch-redux (+1.2%)
• integer (only +0.1%)
• mate (+5.6%)
• wheel-sieve1 (+1.0%)

I'll have to look at the Cmm to puzzle that out but it suggests not putting -fannotate-loops in -O2, at least for now (which the patch doesn't). This might seem a little confusing because the patch does change the behavior of -O2 without any other flags, but by enabling spill costs, which had a max of +1.7%, a min of -50.3%, and a geometric mean of -4.3%. The patch also adds the -fannotate-loops flag, which the user must manually pass. ... Let me know if this is still unclear.

In D2903#114550, @tjakway wrote:

...

I'll have to look at the Cmm to puzzle that out but it suggests not putting -fannotate-loops in -O2, at least for now (which the patch doesn't). This might seem a little confusing because the patch does change the behavior of -O2 without any other flags, but by enabling spill costs, which had a max of +1.7%, a min of -50.3%, and a geometric mean of -4.3%. The patch also adds the -fannotate-loops flag, which the user must manually pass. ... Let me know if this is still unclear.

Quite clear, thanks. A flag likely for changing the spill cost model will likely would be a good idea.

Also, quite impressive numbers. Good work!

I haven't reviewed the patch, but just to note that relying on the geometric mean of normalised results can be misleading. Browsing through the results it looks like

• Many programs are 1-3% faster
• One program is 12% faster
• One program is 50% faster (exact-reals)

I would double-check the two programs that got a lot faster and ensure that the speedup is legit.

Nevertheless, these are good results, nice work!

How are things going here, @tjakway? Let me know if you would like review or help.

First of this is a great idea!

For the new fancy code layout I've introduced a control flow representation into the native GHC backend.
See commit 912fd2b6ca0bc51076835b6e3d1f469b715e2760 for the commit. I think we should aim to extend the CFG representation there to allow tagging of loops. That way we can also use the information for code layout purposes.

Ideally this would be extended to a more principled static analysis eventually which could add more information by for example estimating block entry rates.

I haven't look at the code here in detail but if you plan to pick this up again a few things stood out to me.

• There seems to be no "big picture" description here. I think having a slightly more detailed "elevator pitch" in a Note would be worth having.
• Use LabelMap for maps from BlockId -> X
• Loops can easily be longer than 10 blocks. I imagine loop detection is a common need for compilers maybe there are algorithms that can be used that will scale even for large functions? Doesn't have to be in the first iteration though.
• If you keep the arbitrary cutoff make it larger than 10 and it should definitely be a flag.
• How does your current algorithm deal with irreducible control flow graphs? Iirc they are allowed in Cmm.

It's a great idea and I hope you get around to picking it back up.