SBCL Internals The pages on this CLiki-driven site can be edited by anybody at any time. No warranty of any kind can therefore be made; any implied warranties of merchantability or fitness for a particular purpose are expressly disclaimed

Most phases operate on an Intermediate Representation, a data structure used by the compiler to represent the code at some phase of the compilation process. The two major IRs are

• The Implicit Continuation Representation (ICR, more usually known as IR1) represents the lisp-level semantics of the source code during the initial phases. Frontend phases such as partial evaluation and semantic analysis operate on this representation. IR1 is roughly equivalent to a subset of Common Lisp, but is represented as a flow-graph rather than a syntax tree.
• The Virtual Machine Representation (VMR, more usually IR2) represents the implementation of the source code on a virtual machine. The virtual machine may vary depending on the the target hardware, but VMR is sufficiently stylized that most of the phases which manipulate it are portable.

Each phase is briefly described here. The phases from ``local call analysis'' to ``constraint propagation'' all interact; for maximum optimization, they are generally repeated until nothing new is discovered. The source files which primarily contained each phase in CMUCL are also listed - note that SBCL did some fairly substantial moving around of files, so some of this may now be untrue .

1. ICR conversion

   Convert the source into ICR, doing macroexpansion and simple source-to-source transformation. All names are resolved at this time, so we don't have to worry about name conflicts later on. Files: {\tt ir1tran, srctran, typetran}

2. Local call analysis

   Find calls to local functions and convert them to local calls to the correct entry point, doing keyword parsing, etc. Recognize once-called functions as lets. Create external entry points (XEP?s) for entry-point functions. Files: {locall}

3. Find components

   Find flow graph components and compute depth-first ordering. Separate top-level code from run-time code, and determine which components are top-level components. Files: {dfo}

4. ICR optimize

   A grab-bag of all the non-flow ICR optimizations. Fold constant functions, propagate types and eliminate code that computes unused values. Special-case calls to some known global functions by replacing them with a computed function. Merge blocks and eliminate IF-IFs. Substitute let variables. Files: {ir1opt, ir1tran, typetran, seqtran, vm/vm-tran}

5. Type constraint propagation

   Use global flow analysis to propagate information about lexical variable types. Eliminate unnecessary type checks and tests. Files: {constraint}

6. Type check generation

   Emit explicit ICR code for any necessary type checks that are too complex to be easily generated on the fly by the back end. Files: {checkgen}

7. Event driven operations

   Various parts of ICR are incrementally recomputed, either eagerly on modification of the ICR, or lazily, when the relevant information is needed.

   • Check that type assertions are satisfied, marking places where type checks need to be done.

   • Locate let calls.

   • Delete functions and variables with no references

   Files: {ir1util}, {ir1opt}

8. ICR finalize

   This phase is run after all components have been compiled. It scans the global variable references, looking for references to undefined variables and incompatible function redefinitions. Files: {ir1final}, {main}.

9. Environment analysis

   Determine which distinct environments need to be allocated, and what context needed to be closed over by each environment. We detect non-local exits and set closure variables. We also emit cleanup code as funny function calls. This is the last pure ICR pass. Files: {envanal}

10. Global TN allocation (GTN?)

    Iterate over all defined functions, determining calling conventions and assigning TNs to local variables. Files: {gtn}

11. Local TN allocation (LTN?)

    Use type and policy information to determine which VMR translation to use for known functions, and then create TNs for expression evaluation temporaries. We also accumulate some random information needed by VMR conversion. Files: {ltn}

12. Control analysis

    Linearize the flow graph in a way that minimizes the number of branches. The block-level structure of the flow graph is basically frozen at this point. Files: {control}

13. Stack analysis

    Maintain stack discipline for unknown-values continuation in the presence of local exits. Files: {stack}

14. Entry analysis

    Collect some back-end information for each externally callable function.

15. VMR conversion

    Convert ICR into VMR by translating nodes into VOPs. Emit type checks. Files: {ir2tran, vmdef}

16. Copy propagation

    Use flow analysis to eliminate unnecessary copying of TN values. Files: {copyprop}

17. Representation selection

    Look at all references to each TN to determine which representation has the lowest cost. Emit appropriate move and coerce VOPs for that representation.

18. Lifetime analysis

    Do flow analysis to find the set of TNs whose lifetimes overlap with the lifetimes of each TN being packed. Annotate call VOPs with the TNs that need to be saved. Files: {life}

19. Pack

    Find a legal register allocation, attempting to minimize unnecessary moves. Files: {pack}

20. Code generation

    Call the VOP generators to emit assembly? code. Files: {codegen}

21. Pipeline reorganization

    On some machines, move memory references backward in the code so that they can overlap with computation. On machines with delayed branch? instructions, locate instructions that can be moved into delay slots. Files: {assem-opt}- this file is not part of the SBCL port, only CMU CL

22. Assembly

    Resolve branches and convert in to object code and fixup information. Files: {assembler}

23. Dumping

    Convert the compiled code into an object file or in-core function. Files: {debug-dump}, {dump}, {vm/core}

See also the Papers section for MacLachlan's paper on the Python compiler.

Doing:

(compile-file "foo" :trace-file t)

will dump IR1 after optimization and IR2 before and after register allocation (IIRC), as well as disassembly, to foo.trace.

Pages in this topic: Backend   IR1   IR2   Performance   Source File List   stack allocation   Type Checking   VOP  

Also linked from: Frontend   index   Peephole Optimizer  

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively