Changes between Version 18 and Version 19 of Commentary/Compiler/IntegratedCodeGen


Ignore:
Timestamp:
Jun 9, 2008 10:59:49 AM (6 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/IntegratedCodeGen

    v18 v19  
    9292In practice, we first generate an "abstract control flow graph", `CmmAGraph`, which makes the business of generating fresh `BlockId`s more convenient, and convert that to a `CmmGraph`.  The former is convenient for ''construction'' but cannot be analysed; the latter is concrete, and can be analyzed, transformed, and optimized.   
    9393 
    94 === Establish the Machine Invariant === 
     94=== Instruction selection === 
    9595 
    9696Instruction selection: each {{{Cmm}}} {{{Middle}}} and {{{Last}}} node in the control-flow graph is replaced with a new graph in which the nodes are machine instructions. 
     
    9898CmmGraph Cmm.Middle Cmm.Last -> CmmGraph I386.Middle I386.Last 
    9999}}} 
    100 The {{{I386.Middle}}} type represents computational machine instructions; the {{{I376.Last}}} type represents control-transfer instructions.  The choice of representation is up to the author of the back end, but for continuity with the existing native code generators, we expect to begin by using algebraic data types inspired by the existing definitions in [[GhcFile(compiler/nativeGen/MachInstrs.hs)]]. 
     100The {{{I386.Middle}}} type represents computational machine instructions; the {{{I386.Last}}} type represents control-transfer instructions.  The choice of representation is up to the author of the back end, but for continuity with the existing native code generators, we expect to begin by using algebraic data types inspired by the existing definitions in [[GhcFile(compiler/nativeGen/MachInstrs.hs)]]. 
     101 
     102Note that the graph still contains: 
     103 * '''Variables''' (ie local register that are not yet mapped to particular machine registers) 
     104 * '''Stack-slot addressing modes''', which include late-bound compile-time constants, such as the offset in the frame of the a variable spill location, or BlockId stack-top-on-entry. 
     105 
     106The invariant is that each node could be done by one machine instruction, provided each `LocalReg` maps to a (suitable) physical register; and an instruction involving a stack-slot can cope with (Sp+n).   
    101107 
    102108An '''extremely important distinction''' from the existing code is that we plan to eliminate {{{#ifdef}}} and instead provide multiple datatypes, e.g., in {{{I386.hs}}}, {{{PpcInstrs.hs}}}, {{{Sparc.hs}}}, and so on.   
     
    131137Proc-point analysis: {{{LGraph Instrs}}} (with variables, stack slots, and compile-time constants) -> {{{LGraph Instrs}}} (with variables, stack slots, and compile-time constants) 
    132138  * Proc points are found, and the appropriate control-transfer instructions are inserted. 
    133   * Why so early? Depending on the back end (think of C as the worst case), the proc-point analysis might have to satisfy some horrible calling convention. We want to make these requirements explicit before we get to the register allocator.  We also want to '''exploit the register allocator''' to make the best possible decisions about ''which live variables (if any) should be in registers at a proc point''. 
     139  * Why so early(before register allocation, stack layout)? Depending on the back end (think of C as the worst case), the proc-point analysis might have to satisfy some horrible calling convention. We want to make these requirements explicit before we get to the register allocator.  We also want to '''exploit the register allocator''' to make the best possible decisions about ''which live variables (if any) should be in registers at a proc point''. 
    134140 
    135 === not yet done === 
    136  0. Register allocation: {{{LGraph Instrs}}} (with variables, stack slots, and compile-time constants) {{{-> LGraph Instrs}}} (with stack slots, and compile-time constants) 
    137   * Replace variable references with machine register and stack slots. 
    138  0. Stack Layout: {{{LGraph Instrs}}} (with stack slots, and compile-time constants) {{{-> LGraph Instrs}}} 
     141=== Register allocation === 
     142 
     143 
     144Register allocation replaces variable references with machine register and stack slots.  This may introduce spills and reloads (to account for register shortage), which which is why we may get new stack-slot references. 
     145 
     146That is, register allocation takes {{{LGraph Instrs}}} (with variables, stack slots) {{{-> LGraph Instrs}}} (with stack slots only).  No more variables!   
     147 
     148We no longer need to spill to the C stack, because we have fully allocated everything 
     149to machine registers. 
     150 
     151=== Stack layout === 
     152 
     153Stack Layout: {{{LGraph Instrs}}} (with stack slots, and compile-time constants) {{{-> LGraph Instrs}}} 
    139154  * Choose a stack layout. 
    140155  * Replace references to stack slots with addresses on the stack. 
    141156  * Replace compile-time constants with offsets into the stack. 
     157 
     158No more stack-slot references. 
     159 
     160=== Tidy up === 
     161 
    142162 0. Proc-point splitting: {{{LGraph Instrs -> [LGraph Instrs]}}}  
    143163  * Each proc point gets its own procedure.