wiki:Commentary/Compiler/CPS

Version 4 (modified by guest, 7 years ago) (diff)

Added todo item about extra jumps at block ends

CPS Conversion

This part of the compiler is still under construction and it not presently in ghc-HEAD. These notes are to document it for when it does get merged in.

Overview

This pass takes Cmm with native proceedure calls and an implicit stack and produces Cmm with only tail calls implemented as jumps and an explicit stack. In a word, it does CPS conversion. (All right, so that's two words.)

Design Aspects

  • Proc-Point Analysis
  • Calling Conventions
  • Live Value Analysis
  • Stack Layout

Simple Design

  • Split blocks into multiple blocks at function calls
    • TODO eliminate extra jump at block ends when there is already a jump at the end of the call
  • Do liveness analysis
  • Split every block into a separate function
  • Pass all live values as parameters (probably slow)
    • Must arrange for both the caller and callee to know argument order
      • Simple design: callee just chooses some order and all callers must comply
    • Eventually could be passed implicitly but keeping things explicit makes things easier
    • Evantually could use a custom calling convention
  • Save live values before a call in the continuation
    • Must arrange for bot the caller and callee to know field order
      • Simple design: callee just chooses some order and all callers must comply
    • Eventually needs to be optimized to reduce continuation shuffling
      • Can register allocation algorithms be unified with this into one framework?

Pipeline

  • CPS
    • Make closures and stacks manifest
    • Makes all calls are tail calls
  • Parameter Elimination
    • Makes calling convention explicit
    • For externally visible functions calling conventions is machine specific, but not backend specific because functions compiled from different backends must be be able to call eachother
    • For local functions calling convention can be left up to the backend because it can take advantage of register allocation.
      • However, the first first draft will specify the standard calling convention for all functions even local ones because:
        • It's simpler
        • The C code generator can't handle function parameters because of the Evil Mangler
        • The NCG doesn't yet understand parameters