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


Ignore:
Timestamp:
Jul 4, 2007 3:41:25 PM (7 years ago)
Author:
Michael D. Adams
Comment:

Added section on loopholes in the

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/CPS

    v17 v18  
    297297}}} 
    298298 
     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. 
     302 
     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. 
     307 
     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. 
     311 
     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. 
     319 
     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. 
     323 
     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. 
     328 
     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: 
     332{{{ 
     333  r = foo(1, 2); 
     334  goto L; 
     335 L: 
     336  if (Hp < HpLim) { do_gc(); goto L; } 
     337}}} 
     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}}}. 
     341 
     342We solve this by changing the syntax to 
     343{{{ 
     344  r = foo(1, 2); 
     345  goto L; 
     346 L: 
     347  if (Hp < HpLim) { r = do_gc_p(r); goto L; } 
     348}}} 
     349 
     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.) 
     353 
    299354== Not in Scope of Current Work == 
    300355Improvements that could be made but that will not be implemented durring the curent effort.