Changes between Version 7 and Version 8 of Commentary/Compiler/Backends/NCG


Ignore:
Timestamp:
Nov 17, 2006 6:55:31 PM (7 years ago)
Author:
p_tanski
Comment:

--

Legend:

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

    v7 v8  
    1 = Native Code Generator = 
     1= Native Code Generator (NCG) = 
    22 
    33For other information related to this page, see: 
    44 * [http://www.cse.unsw.edu.au/~chak/haskell/ghc/comm/the-beast/ncg.html the Old GHC Commentary: Native Code Generator] page (comments regarding Maximal Munch and register allocation optimisations are mostly still valid) 
    55 * [wiki:BackEndNotes] for optimisation ideas regarding the current NCG 
     6 * The New GHC Commentary Cmm page: [wiki:Commentary/Compiler/CmmType The Cmm language] (the NCG code works from Haskell's implementation of C-- and many optimisations in the NCG relate to Cmm) 
    67 
    78=== Overview: Files, Parts === 
    89 
    9 After GHC has produced Cmm (use -ddump-cmm or -ddump-opt-cmm to view), the Native Code Generator (NCG) transforms [wiki:Commentary/Compiler/CmmType Cmm] into architecture-specific assembly code.  The NCG is located in [[GhcFile(compiler/nativeGen)]] and is separated into eight modules: 
     10After GHC has produced [wiki:Commentary/Compiler/CmmType Cmm] (use -ddump-cmm or -ddump-opt-cmm to view), the Native Code Generator (NCG) transforms Cmm into architecture-specific assembly code.  The NCG is located in [[GhcFile(compiler/nativeGen)]] and is separated into eight modules: 
    1011 
    1112 * [[GhcFile(compiler/nativeGen/AsmCodeGen.lhs)]][[BR]] 
     
    2425   defines the main 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]] 
    2526 * [[GhcFile(compiler/nativeGen/RegisterAlloc.hs)]][[BR]] 
    26    one of the most complicated modules in the NCG, {{{RegisterAlloc}}} manages the allocation of registers for each ''basic block'' of Haskell-abstracted assembler code: management involves ''liveness'' analysis, allocation or deletion of temporary registers, ''spilling'' temporary values to the ''spill stack'' (memory) and many optimisations.  ''Note: much of this detail will be described later; '''basic block''' is defined below.'' 
     27   one of the most complicated modules in the NCG, {{{RegisterAlloc}}} manages the allocation of registers for each ''basic block'' of Haskell-abstracted assembler code: management involves ''liveness'' analysis, allocation or deletion of temporary registers, ''spilling'' temporary values to the ''spill stack'' (memory) and many optimisations.  ''See [wiki:Commentary/Compiler/CmmType The Cmm language] for the definition of a ''basic block'' (in Haskell, ''{{{type CmmBasicBlock =  GenBasicBlock CmmStmt}}}'').'' 
    2728 
    2829and one header file: 
     
    3334The NCG has '''machine-independent'''  and '''machine-dependent''' parts.   
    3435 
    35 The '''machine-independent''' parts relate to generic operations, especially optimisations, on Cmm code.  The main machine-independent parts begin with ''Cmm blocks.''  A ''Cmm block'' is roughly parallel to a Cmm function or procedure in the same way as a compiler may generate a C function into an assembler symbol used as a label, composed of smaller ''basic blocks'' ({{{BasicBlock}}}) separated by branches (jumps)--every basic block ends in a branch instruction.  ''Cmm block''s are held as lists of {{{Cmm}}} statements ({{{[CmmStmt]}}}, defined in [[GhcFile(compiler/cmm/Cmm.hs)]], or the {{{type}}} synonym {{{CmmStmts}}}, defined in [[GhcFile(compiler/cmm/CmmUtils.hs)]]).  A machine-specific (assembler) instruction is represented as a {{{Instr}}}.  The machine-independent NCG parts: 
     36The '''machine-independent''' parts relate to generic operations, especially optimisations, on Cmm code.  The main machine-independent parts begin with ''Cmm blocks.''  (A ''Cmm block'' is a compilation unit of Cmm code, a file.  See [wiki:Commentary/Compiler/CmmType The Cmm language] for a discussion of what a ''Cmm block'' is but note that ''Cmm'' is a type synonym for {{{GenCmmTop CmmStatic CmmStmt}}}.)  A machine-specific (assembler) instruction is represented as a {{{Instr}}}.  The machine-independent NCG parts: 
    3637 1. optimise each Cmm block by reordering its basic blocks from the original order (the {{{Instr}}} order from the {{{Cmm}}}) to minimise the number of branches between basic blocks, in other words, by maximising fallthrough of execution from one basic block to the next.[[BR]][[BR]] 
    3738 1. lazily convert each Cmm block to abstract machine instructions ({{{Instr}}}) operating on an infinite number of registers--since the NCG Haskell files only contain instructions for the host computer on which GHC was compiled, these {{{Instr}}} are machine-specific; and,[[BR]][[BR]]