Changes between Version 17 and Version 18 of Commentary/Compiler/CPS

Jul 4, 2007 3:41:25 PM (10 years ago)
Michael D. Adams

Added section on loopholes in the


  • Commentary/Compiler/CPS

    v17 v18  
     299== Loopholes ==
     300There are a number of deviations from what one might expect from a CPS algorithm
     301due to the need to encode existing optimizations and idioms.
     303=== GC Blocks ===
     304For obvious reasons,
     305the stack used by GC blocks does not count tward the maximum amount of stack
     306used by the function.
     308This loophole is overloaded by the GC '''functions''' so they don't create their own
     309infinite loop.  The main block is marked as being the GC block so its stack usage
     310doesn't get checked.
     312=== Update Frames ===
     313Update frame have to be pushed onto the stack at the begining of an update function.
     314We could do this by wrapping the update function inside another function
     315that just does the work of calling that other function,
     316but since updates are so common we don't want to pay the cost
     317of that extra jump.
     318Thus a function can be annotated with a frame that should be pushed on entry.
     320Note that while the frame is equivalent to a tail call at the end of the function,
     321the frame must be pushed at the beginning of the function because parts of the blackhole
     322code look for these update frames to determine what thunks are under evaluation.
     324=== User defined continuations ===
     325Pushing an update frame on the stack requires the ability to define a
     326function that will pull that frame from the stack and have access to any
     327values within the frame.  This is done with user-defined continuations.
     329=== Branches to continuations ===
     330A GC block for a heap check after a call should only take one or two instructions.
     331However the natural code:
     333  r = foo(1, 2);
     334  goto L;
     335 L:
     336  if (Hp < HpLim) { do_gc(); goto L; }
     338would generate a trivial continuation for the {{{do_gc}}} call as
     339well as a trivial continuation for the {{{foo}}} call that just calls
     340the proc point {{{L}}}.
     342We solve this by changing the syntax to
     344  r = foo(1, 2);
     345  goto L;
     346 L:
     347  if (Hp < HpLim) { r = do_gc_p(r); goto L; }
     350Now the {{{do_gc_p}}} call has the same return signature as {{{foo}}}
     351and can use the same continuation.
     352(A call followed by a {{{goto}}} thus gets optimized down to just the call.)
    299354== Not in Scope of Current Work ==
    300355Improvements that could be made but that will not be implemented durring the curent effort.