Changes between Version 1 and Version 2 of Commentary/Compiler/Backends/NCG/RegisterAllocator


Ignore:
Timestamp:
Sep 17, 2007 3:57:01 PM (8 years ago)
Author:
guest
Comment:

describe source files

Legend:

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

    v1 v2  
    33== Overview ==
    44
    5 The register allocator is split into two sections, the register allocator proper in nativeGen/Reg*.hs and a generic graph coloring library in utils/Graph*.hs.
     5GHC currently provides two register allocation algorithms, simple linear scan and graph coloring. Although some of the code is currently shared between the two, as we only want to maintain a single algorithm support for linear scan will be removed in a subsequent version.
     6
     7The register allocator code is split into two main sections, the register allocator proper and a generic graph coloring library. The graph coloring library is also used by the Stg->Cmm converter.
    68
    79=== The register allocator ===
    810
     11 * [[GhcFile(compiler/nativeGen/RegLiveness.hs)]] [[BR]]
     12   Defines {{{LiveInstr}}} and {{{LiveCmmTop}}} which carry native machine instructions annotated with register liveness information. It also provides functions to annotate native code ({{{NatCmmTop}}}) with this liveness information, and to slurp out sets of register conflicts for feeding into the coloring allocator.
     13
    914 * [[GhcFile(compiler/nativeGen/RegAllocColor.hs)]] [[BR]]
     15   Defines {{{regAlloc}}}, the main driver function for the graph coloring allocator. The driver accepts {{{LiveCmmTop}}}s which use virtual regs, and produces{{{NatCmmTops}}} which use real machine regs. This module also provides functions to help build and deep seq the register conflict graph.
    1016
    1117 * [[GhcFile(compiler/nativeGen/RegAllocLinear.hs)]] [[BR]]
     18   Defines the linear scan allocator. Its interface is identical to the coloring allocator.
     19
     20 * [[GhcFile(compiler/nativeGen/RegAllocInfo.hs)]] [[BR]]
     21   Defines the register information function, {{{regUsage}}}, which takes a set of real and virtual registers and returns the actual registers used by a particular {{{Instr}}}; register allocation is in AT&T syntax order (source, destination), in an internal function, {{{usage}}}; defines the {{{RegUsage}}} data type[[BR]][[BR]]
     22
     23 * [[GhcFile(compiler/nativeGen/RegSpillCost.hs)]] [[BR]]
     24   Defines {{{chooseSpill}}} which is responsible for selecting a virtual reg to spill to the stack when not enough real regs are available.
     25
     26 * [[GhcFile(compiler/nativeGen/RegSpill.hs)]] [[BR]]
     27   Defines {{{regSpill}}} which takes {{{LiveCmmTop}}}s and inserts spill/reload instructions virtual regs that wouldn't fit in real regs. {{{regSpill}}} simply inserts spill/reloads for every use/def of a particular virtual reg.
     28 
     29 * [[GhcFile(compiler/nativeGen/RegSpillClean.hs)]] [[BR]]
     30   The spill cleaner is run after registers have been allocated and erases spill/reload instructions inserted by {{{regSpill}}} which weren't strictly nessesary.
    1231
    1332 * [[GhcFile(compiler/nativeGen/RegAllocStats.hs)]] [[BR]]
    14 
    15  * [[GhcFile(compiler/nativeGen/RegArchBase.hs)]] [[BR]]
    16 
    17  * [[GhcFile(compiler/nativeGen/RegArchX86.hs)]] [[BR]]
    18 
    19  * [[GhcFile(compiler/nativeGen/RegCoalesce.hs)]] [[BR]]
    20 
    21  * [[GhcFile(compiler/nativeGen/RegLiveness.hs)]] [[BR]]
    22 
    23  * [[GhcFile(compiler/nativeGen/RegSpillClean.hs)]] [[BR]]
    24 
    25  * [[GhcFile(compiler/nativeGen/RegSpillCost.hs)]] [[BR]]
    26 
    27  * [[GhcFile(compiler/nativeGen/RegSpill.hs)]] [[BR]]
    28 
    29  * [[GhcFile(compiler/nativeGen/RegAllocInfo.hs)]] [[BR]]
    30 
     33   Defines data types and pretty printers used for collecting statistics and debugging info from the coloring allocator.
    3134
    3235=== Graph coloring ===
    3336
    3437 * [[GhcFile(compiler/util/GraphBase.hs)]] [[BR]]
     38   Defines the basic {{{Graph}}}, {{{Node}}} and {{{Triv}}} types used by the coloring algorithm.
    3539
    3640 * [[GhcFile(compiler/util/GraphColor.hs)]] [[BR]]
     41   Defines the function {{{colorGraph}}} which is responsible for assigning colors (real regs) to nodes (virtual regs) in the register conflict graph. For more detail see [[wiki:Commentary/Compiler/GraphColoring Graph Coloring]].
    3742
    3843 * [[GhcFile(compiler/util/GraphOps.hs)]] [[BR]]
     44   Defines functions to perform basic operations on the graphs such as adding, deleting, and coalescing nodes.
    3945
    4046 * [[GhcFile(compiler/util/GraphPps.hs)]] [[BR]]
     47   Defines functions for pretty print graphs in human readable-ish and graphviz format.
    4148
     49=== Miscellanea ===
    4250
     51 * [[GhcFile(compiler/nativeGen/RegCoalesce.hs)]] [[BR]]
     52   Defines a function {{{regCoalesce}}} that does aggressive coalescing directly on {{{LiveCmmTops}}}, without using the graph. This isn't used at the moment but has been left in incase we want to rejig the allocator when the new CPS converter comes online.
     53
     54 * [[GhcFile(compiler/nativeGen/RegArchBase.hs)]] [[BR]]
     55   Defines utils for calculating whether a register in the conflict graph is trivially colorable, in a generic way which handles aliasing between register classes. This module is not used directly by GHC. TODO: link to description of algorithm.
     56
     57 * [[GhcFile(compiler/nativeGen/RegArchX86.hs)]] [[BR]]
     58   Contains a description of the aliasing constraints between the register sets on x86. This module is not used directly by GHC.
     59