1. 12 Sep, 2007 2 commits
  2. 11 Sep, 2007 1 commit
  3. 10 Sep, 2007 1 commit
  4. 07 Sep, 2007 1 commit
    • Ben.Lippmeier@anu.edu.au's avatar
      Add iterative coalescing to graph coloring allocator · 12d0b388
      Ben.Lippmeier@anu.edu.au authored
      Iterative coalescing interleaves conservative coalesing with the regular
      simplify/scan passes. This increases the chance that nodes will be coalesced
      as they will have a lower degree than at the beginning of simplify. The end
      result is that more register to register moves will be eliminated in the
      output code, though the iterative nature of the algorithm makes it slower
      compared to non-iterative coloring.
      
      Use -fregs-iterative  for graph coloring allocation with iterative coalescing
          -fregs-graph      for non-iterative coalescing.
      
      The plan is for iterative coalescing to be enabled with -O2 and have a 
      quicker, non-iterative algorithm otherwise. The time/benefit tradeoff
      between iterative and not is still being tuned - optimal graph coloring
      is NP-hard, afterall..
      12d0b388
  5. 06 Sep, 2007 2 commits
  6. 05 Sep, 2007 2 commits
    • Ben.Lippmeier@anu.edu.au's avatar
      Improve GraphColor.colorScan · 1dd44153
      Ben.Lippmeier@anu.edu.au authored
      Testing whether a node in the conflict graph is trivially 
      colorable (triv) is still a somewhat expensive operation.
      
      When we find a triv node during scanning, even though we remove
      it and its edges from the graph, this is unlikely to to make the
      nodes we've just scanned become triv - so there's not much point
      re-scanning them right away.
      
      Scanning now takes place in passes. We scan the whole graph for
      triv nodes and remove all the ones found in a batch before rescanning
      old nodes.
      
      Register allocation for SHA1.lhs now takes (just) 40% of total
      compile time with -O2 -fregs-graph on x86
      1dd44153
    • Ben.Lippmeier@anu.edu.au's avatar
      warning police · 272f0ba8
      Ben.Lippmeier@anu.edu.au authored
      272f0ba8
  7. 03 Sep, 2007 1 commit
    • Ben.Lippmeier@anu.edu.au's avatar
      Do conservative coalescing in register allocator · a7f409e8
      Ben.Lippmeier@anu.edu.au authored
      Avoid coalescing nodes in the register conflict graph if the
      new node will not be trivially colorable. Also remove the
      front end aggressive coalescing pass.
        
      For typical Haskell code the graph coloring allocator now does
      about as well as the linear allocator.
        
      For code with a large amount of register pressure it does much
      better, but takes longer.
        
      For SHA1.lhs from darcs on x86
         
                spills    reloads    reg-reg-moves
                inserted   inserted  left in code   compile-time
        linear    1068      1311        229            7.69(s)
        graph      387       902        340           16.12(s)
      a7f409e8
  8. 04 Sep, 2007 1 commit
  9. 03 Sep, 2007 2 commits
  10. 28 Aug, 2007 1 commit
  11. 01 Sep, 2007 1 commit
  12. 14 Aug, 2007 1 commit
    • Ben.Lippmeier@anu.edu.au's avatar
      Add graph coloring register allocator. · 0f7d268d
      Ben.Lippmeier@anu.edu.au authored
      Refactored linear allocator into separate liveness annotation and allocation stages.
      Added graph coloring allocator, use -fregs-graph to enable.
        New dump flags are
          -ddump-asm-native          -- output of cmm -> native transform.
          -ddump-asm-liveness        -- code annotated with register liveness info
          -ddump-asm-coalesce        -- output of register move coalescing
                                          (this is a separate pass when using the coloring allocator)
                                          (this could change in the future)
          -ddump-asm-regalloc        -- code after register allocation
          -ddump-asm-regalloc-stages -- blocks after each build/spill stage of coloring allocator
          -ddump-asm-conflicts       -- a global register liveness graph in graphviz format 
              
      The new register allocator will allocate some registers, but it's not
      quite ready for prime-time yet. The spill code generator needs some work...
      0f7d268d