Refactor linear reg alloc to remember past assignments.

When assigning registers we now first try registers we
assigned to in the past, instead of picking the "first"
one.

This is in extremely helpful when dealing with loops for
which variables are dead for part of the loop.

This is important for patterns like this:

        foo = arg1
    loop:
        use(foo)
        ...
        foo = getVal()
        goto loop;

There we:
* assign foo to the register of arg1.
* use foo, it's dead after this use as it's overwritten after.
* do other things.
* look for a register to put foo in.

If we pick an arbitrary one it might differ from the register the
start of the loop expect's foo to be in.
To fix this we simply look for past register assignments for
the given variable. If we find one and the register is free we
use that register.

This reduces the need for fixup blocks which match the register
assignment between blocks. In the example above between the end
and the head of the loop.

This patch also moves branch weight estimation ahead of register
allocation and adds a flag to control it (cmm-static-pred).
* It means the linear allocator is more likely to assign the hotter
  code paths first.
* If it assign these first we are:
  + Less likely to spill on the hot path.
  + Less likely to introduce fixup blocks on the hot path.

These two measure combined are surprisingly effective. Based on nofib
we get in the mean:

* -0.9% instructions executed
* -0.1% reads/writes
* -0.2% code size.
* -0.1% compiler allocations.
* -0.9% compile time.
* -0.8% runtime.

Most of the benefits are simply a result of removing redundant moves
and spills.

Reduced compiler allocations likely are the result of less code being
generated. (The added lookup is mostly non-allocating).

1 files changed, 1 insertions, 0 deletions

diff --git a/compiler/GHC/CmmToAsm/Reg/Linear/State.hs b/compiler/GHC/CmmToAsm/Reg/Linear/State.hs
index f96cc71239..ab05ab632a 100644
--- a/compiler/GHC/CmmToAsm/Reg/Linear/State.hs
+++ b/compiler/GHC/CmmToAsm/Reg/Linear/State.hs
@@ -1,4 +1,5 @@
 {-# LANGUAGE CPP, PatternSynonyms, DeriveFunctor #-}
+{-# LANGUAGE ScopedTypeVariables #-}
 
 #if !defined(GHC_LOADED_INTO_GHCI)
 {-# LANGUAGE UnboxedTuples #-}