Changes between Version 2 and Version 3 of SemiTagging


Ignore:
Timestamp:
Oct 11, 2006 12:58:08 PM (8 years ago)
Author:
alexey
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SemiTagging

    v2 v3  
    1414 
    1515This would require modifying 
    16 - the GC to set the LSB bit of constructor closure pointers, 
    17 - the GC and the RTS code to mask out the LSB pointer when dereferencing it, 
    18 - the code generation to test the LSB bit and case expressions and avoid the indirect jump. 
     16 * the GC to set the LSB bit of constructor closure pointers, 
     17 * the GC and the RTS code to mask out the LSB pointer when dereferencing it, 
     18 * the code generation to test the LSB bit and case expressions and avoid the indirect jump. 
    1919 
    2020== Using more than one bit == 
     
    2222We can go a bit further than this, too. Since there are 2 spare bits (4 on a 64-bit machine), we can encode 4 (16) states. Taking 0 to mean "unevaluted", that leaves 3 (15) states to encode the values for the "tag" of the constructor. eg. an evaluated Bool would use 1 to indicate False and 2 to indicate True. An evaluated list cell would use 1 to indicate [] and 2 to indicate (:). 
    2323 
    24 The nice thing about the current approach is that code size is small; implementing the test and jump will certainly add extra code to compiled case expressions. But the gains might be worth it. Complexity-wise this means masking out these bits when following any pointer to a heap object, which means carefully checking most of the runtime.  
     24The nice thing about the current approach is that code size is small; implementing the test and jump will certainly add extra code to compiled case expressions. But the gains might be worth it. Complexity-wise this means masking out these bits when following any pointer to a heap object, which means carefully checking most of the runtime. 
     25 
     26This would require modifying all of the above plus modifying 
     27 * the code generator so that it checks whether the number of constructors is smaller or equal than 3/15. 
     28 
     29== Using a tag directly in the pointer == 
     30 
     31Constructors without children (such as {{{False}}} and {{{True}}}) only need their tag to be represented. Hence we can drop the pointer altogether as follows: 
     32 
     33||  || bits 31..2 || bits 1 0 || 
     34|| cons. w/no children || tag || 01 || 
     35|| cons. w/children no. 1    || ptr || 10 || 
     36|| cons. w/children no. 2    || ptr || 11 || 
     37