• Andreas Klebinger's avatar
    Refactor linear reg alloc to remember past assignments. · 13f6c9d0
    Andreas Klebinger authored
    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).
    13f6c9d0
Instr.hs 6.32 KB