Changes between Version 10 and Version 11 of Commentary/Compiler/Backends/NCG/RegisterAllocator


Ignore:
Timestamp:
Sep 18, 2007 3:00:01 PM (7 years ago)
Author:
guest
Comment:

reorder sections

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/Backends/NCG/RegisterAllocator

    v10 v11  
    4040For an overview of techniques for inserting spill code. 
    4141 
     42== Register pressure in Haskell code == 
     43 
     44Present GHC compiled code places very little pressure on the register set. Even on x86 with only 3 allocable registers, most modules do not need spill/reloads. This is a mixed blessing - on one hand the conflict graphs are small so we can avoid performance problems related to how the graph is represented, on the other hand it can be hard to find code to test against. Register pressure is expected to increase as the Stg->Cmm transform improves. 
     45 
     46In the meantime, here are some good sources for test code: 
     47 
     48 * '''Nofib'''[[BR]] 
     49   Only a few nofib benchmarks create spills with {{{-O2}}}, two are {{{spectral/hartel/genfft}}} and {{{spectral/sorting}}}. 
     50 
     51 * '''Turn on profiling.'''[[BR]] 
     52   Register pressure increases significantly when the module is compiled with profiling. [attachment:checkSpills.report] gives tuples of {{{(spills, reloads, reg-reg-moves)}}} present in output code generated by the three algorithms when compiled with {{{-O2 -prof}}}. Left to right are the stats for the linear, graph coloring and iterative coalescing algorithms. Note that most modules compile with no spill/reloads inserted, but a few (notably {{{real/compress2/Encode}}}) need several hundred. 
     53 
     54  I've found it useful to maintain three darcs repos when working on the allocator. {{{ghc-HEAD-work}}} compiled with {{{-Onot}}} for fast compilation during hacking, {{{ghc-HEAD-prof}}} for testing with profiling turned on, and {{{ghc-HEAD-validate}}} for running the validate script. Patches are created in {{{work}}}, pushed into {{{prof}}} where {{{checkSpills}}} is used to compile the nofib benchmarks with the most register pressure. Once we're happy that the performance is ok, the patch is then pushed into {{{validate}}} for validation before pushing to the main repo on {{{darcs.haskell.org}}} 
     55 
     56 * '''SHA from darcs'''[[BR]] 
     57   The {{{SHA1.lhs}}} module from the darcs source, compiled with {{{-O2}}} creates the most register pressure out of any Haskell code that I'm aware of. When compiling SHA1, GHC inlines several worker functions and the native code block that computes the hash ends up being around 1700 instructions long. vregs that live in the middle of the block have in the order of 30 conflict neighbors. (evidently, the conflict graph is too large for most of the graphviz layout algorithms to cope with) 
     58 
     59  For these reasons, {{{SHA1.lhs}}} can be treated as a good worst-case input to the allocator. In fact, the current linear allocator cannot compile it with {{{-O2 -prof}}} on x86 as it runs out of stack slots, which are allocated from a static pool. Make sure to test any changes to the allocator against this module. 
    4260 
    4361== Hacking/Debugging == 
     
    6987 * checkSpills 
    7088 
    71 == Register pressure in Haskell code == 
    72  
    73 Present GHC compiled code places very little pressure on the register set. Even on x86 with only 3 allocable registers, most modules do not need spill/reloads. This is a mixed blessing - on one hand the conflict graphs are small so we can avoid performance problems related to how the graph is represented, on the other hand it can be hard to find code to test against. Register pressure is expected to increase as the Stg->Cmm transform improves. 
    74  
    75 In the meantime, here are some good sources for test code: 
    76  
    77  * '''Nofib'''[[BR]] 
    78    Only a few nofib benchmarks create spills with {{{-O2}}}, two are {{{spectral/hartel/genfft}}} and {{{spectral/sorting}}}. 
    79  
    80  * '''Turn on profiling.'''[[BR]] 
    81    Register pressure increases significantly when the module is compiled with profiling. [attachment:checkSpills.report] gives tuples of {{{(spills, reloads, reg-reg-moves)}}} present in output code generated by the three algorithms when compiled with {{{-O2 -prof}}}. Left to right are the stats for the linear, graph coloring and iterative coalescing algorithms. Note that most modules compile with no spill/reloads inserted, but a few (notably {{{real/compress2/Encode}}}) need several hundred. 
    82  
    83   I've found it useful to maintain three darcs repos when working on the allocator. {{{ghc-HEAD-work}}} compiled with {{{-Onot}}} for fast compilation during hacking, {{{ghc-HEAD-prof}}} for testing with profiling turned on, and {{{ghc-HEAD-validate}}} for running the validate script. Patches are created in {{{work}}}, pushed into {{{prof}}} where {{{checkSpills}}} is used to compile the nofib benchmarks with the most register pressure. Once we're happy that the performance is ok, the patch is then pushed into {{{validate}}} for validation before pushing to the main repo on {{{darcs.haskell.org}}} 
    84  
    85  * '''SHA from darcs'''[[BR]] 
    86    The {{{SHA1.lhs}}} module from the darcs source, compiled with {{{-O2}}} creates the most register pressure out of any Haskell code that I'm aware of. When compiling SHA1, GHC inlines several worker functions and the native code block that computes the hash ends up being around 1700 instructions long. vregs that live in the middle of the block have in the order of 30 conflict neighbors. (evidently, the conflict graph is too large for most of the graphviz layout algorithms to cope with) 
    87  
    88   For these reasons, {{{SHA1.lhs}}} can be treated as a good worst-case input to the allocator. In fact, the current linear allocator cannot compile it with {{{-O2 -prof}}} on x86 as it runs out of stack slots, which are allocated from a static pool. Make sure to test any changes to the allocator against this module. 
    89  
    9089== Possible Improvements == 
    9190