Changes between Version 2 and Version 3 of SemiTagging

Timestamp:

10/11/06 05:58:08 (7 years ago)

Author:

alexey

Comment:

--

SemiTagging

@@ -14 +14 @@
 
 This would require modifying
-- the GC to set the LSB bit of constructor closure pointers,
-- the GC and the RTS code to mask out the LSB pointer when dereferencing it,
-- the code generation to test the LSB bit and case expressions and avoid the indirect jump.
+ * the GC to set the LSB bit of constructor closure pointers,
+ * the GC and the RTS code to mask out the LSB pointer when dereferencing it,
+ * the code generation to test the LSB bit and case expressions and avoid the indirect jump.
 
 == Using more than one bit ==
@@ -22 +22 @@
 We 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 (:).
 
-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. 
+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.
+
+This would require modifying all of the above plus modifying
+ * the code generator so that it checks whether the number of constructors is smaller or equal than 3/15.
+
+== Using a tag directly in the pointer ==
+
+Constructors without children (such as {{{False}}} and {{{True}}}) only need their tag to be represented. Hence we can drop the pointer altogether as follows:
+
+||  || bits 31..2 || bits 1 0 ||
+|| cons. w/no children || tag || 01 ||
+|| cons. w/children no. 1    || ptr || 10 ||
+|| cons. w/children no. 2    || ptr || 11 ||
+