Changes between Version 19 and Version 20 of Commentary/Compiler/NewCodeGen


Ignore:
Timestamp:
May 16, 2008 5:26:39 PM (7 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/NewCodeGen

    v19 v20  
    11= Material about the new code generator =
    22
    3 This page summarises work that Norman Ramsey, Simon M, and Simon PJ are doing on re-architecting GHC's back end.
     3This page summarises work that Norman Ramsey, Simon M, Simon PJ, and John Dias are doing on re-architecting GHC's back end. You may want to see the [wiki:Commentary/Compiler/NewCodeGenPipeline short-term view of the pipeline].
    44
    55Bug list (code-gen related bugs that we may be able to fix):
     
    6767 * '''`CmmExpr`''' contains the data types for Cmm expressions, registers, and the like.  It does not depend on the dataflow framework at all.
    6868
    69 --------------------------------------
    70 == The pipeline: Make the new code generator work with the existing native codeGen ==
    71 
    72  * '''Code generator''' converts STG to `CmmGraph`.  Implemented in `StgCmm*` modules (in directory `codeGen`).
    73 
    74  * '''Simple control flow optimisation''', implemented in `CmmContFlowOpt`:
    75    * Branch chain elimination.
    76    * Remove unreachable blocks.
    77    * Block concatenation.  branch to K; and this is the only use of K. 
    78    * Common Block Elimination (like CSE). This essentially implements the Adams optimisation, we believe.
    79    * Consider (sometime): block duplication.  branch to K; and K is a short block.  Branch chain elimination is just a special case of this.
    80 
    81 
    82  * '''Proc-point analysis''' and '''transformation''', implemented in `CmmProcPointZ`.  (Adams version is `CmmProcPoint`.) The transformation part adds a `CopyIn` to the front of each proc-point, which expresses the idea that proc-points use a standard entry convention.
    83     * The analysis produces a set of `BlockId` that should become proc-point
    84     * The transformation inserts a `CopyIn` at the start of each proc-point, and a `CopyOut` just before each branch to a proc-point.
    85 
    86  * '''Add spill/reload''', implemented in `CmmSpillReload`, to spill live C-- variables before a call and reload them afterwards.  The middle node of the result is `Middle` (from `ZipCfgCmm` extended with `Spill` and `Reload` constructors. 
    87  Invariant: (something like) all variables in a block are gotten from `CopyIn` or `Reload`.
    88 
    89  * '''Stack slot layout'''.  Build inteference graph for variables live across calls, and allocate a stack slot for such variables.  That is, stack slot allocation is very like register allocation.
    90 
    91  * '''Lay out the stack'''
    92    * A `SlotId` is the offset of a stack slot from the old end (high address) of the frame.  It doesn't vary as the physical stack pointer moves.
    93    * A particular variable has one and only one `SlotId`. 
    94    * The stack layout pass produces a mapping of: ''(variable -> slotid, label -> slotid)''
    95    * Plus, it transforms the code by eliminating `CopyIn` and `CopyOut` in favour of assigments
    96 
    97  * '''Make the stack explicit'''.
    98    * Convert `Spill`, `Reload` to hardware-register and stack traffic.
    99    * Add stack-pointer adjustment instructions.
    100    * Avoid memory traffic at joins. (What does this mean?)
    101 
    102  * '''Split into multiple !CmmProcs'''.
    103 
    104 
    105 '''The Adams optimisation''' is done by stuff above.  Given:
    106 {{{
    107   call f returns to K
    108   K: CopyIn retvals; goto L
    109   L: <code>
    110 }}}
    111  transform to
    112 {{{
    113   call f returns to L
    114   L : CopyIn retvals; <code>
    115 }}}
    116  ''and'' move `CopyOut` into L's other predecessors.  !ToDo: explain why this is a good thing.  In fact Common Block Elimination does this, we think.
    117 
    11869-----------------------------------
    11970== Runtime system ==