Optimize ADT structs for reuse

[EmilySillars]

Background Info

The current SSLANG object model features ADTs as a union (called ssm_value_t) of either a "packed_val" integer or "heap_ptr" to a struct on the heap. In the latter case, the struct on the heap will be a generic memory management header followed by an array of ssm_value_t fields.

By personalizing the amount of space the memory manager allocates for each ADT instance, and saving the "actual" size of its fields array in the header, we are able to specialize a generic SSLANG object structure for different ADT instances.
For example, given the following adt definition,

type Color
  RGB Int Int Int         
  CMYK Int Int Int Int
  White
  Black
  Sparkly

C implementations of each instance will have an ssm_mm header followed by a different number of fields:

let bg = RGB 192 192 192  
// 
//    .-----------------.              .-----------------.
// bg | xxxxxxx0        | -----------> | struct ssm_mm   | - tag set to RGB; val_count set to 3 for 3 fields
//    .-----------------.              |-----------------|
//                                     | ssm_value_t     | - contains 192 
//                                     |-----------------|
//                                     | ssm_value_t     | - contains 192 
//                                     |-----------------|
//                                     | ssm_value_t     | - contains 192 
//                                     .-----------------.

let ink = Black        
// 
//     .-----------------.
// ink | 00000111        | - tag set to Black and then marshalled
//     .-----------------.

let dot = RGB 204 255 204 
// 
//     .-----------------.             .-----------------.
// dot | xxxxxxx0        | ----------> | struct ssm_mm   | - tag set to RGB; val_count set to 3 for 3 fields
//     .-----------------.             |-----------------|
//                                     | ssm_value_t     | - contains 204 
//                                     |-----------------|
//                                     | ssm_value_t     | - contains 255
//                                     |-----------------|
//                                     | ssm_value_t     | - contains 204
//                                     .-----------------.

Optimization Idea

In this example, an instance of ADT Color gets assigned a value three different times.

//draw (brush : & Color) -> () =
// ...                      // ommitted for brevity

main ( brush : & Color ) -> () =
  brush <- RGB 192 192 192
  draw brush       
  brush <- Black 
  draw brush  
  brush <- RGB 204 255 204
  draw brush
  ()

In our current implementation, a new Color objected is allocated for each heap_ptr assignment:

  acts->__tmp_0 = ssm_new_adt(3U, RGB);                        // allocate new DCon w/ space for 3 fields
  ssm_adt_field(acts->__tmp_0, 0U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 1U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 2U) = ssm_marshal(192);
  ssm_assign(acts->brush, actg->priority, acts->__tmp_0);
  // draw 
  ssm_assign(acts->brush, actg->priority, ssm_marshal(Black)); //  nullary DCon
  // draw
  acts->__tmp_1 = ssm_new_adt(3U, RGB);                        //  allocate new DCon w/ space for 3 fields
  ssm_adt_field(acts->__tmp_1, 0U) = ssm_marshal(204);
  ssm_adt_field(acts->__tmp_1, 1U) = ssm_marshal(255);
  ssm_adt_field(acts->__tmp_1, 2U) = ssm_marshal(204);
  ssm_assign(acts->brush, actg->priority, acts->__tmp_1);
  // draw

If an ADT's value changes a lot during the course of a program, this pattern could be costly, requiring lots of repetitious deallocations and reallocations. To reduce needless memory freeing and reallocation, we can change the representation of SSLANG ADTs so if an ADT isn't always a packed value, it will be allocated a struct only the first time it's assigned a value; this struct would contain its max number of fields.
Then our generated code could change to something like:

  acts->__tmp_0 = ssm_new_adt(3U, RGB);              //  allocate new DCon w/ space for 3 (max # of) fields
  ssm_adt_field(acts->__tmp_0, 0U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 1U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 2U) = ssm_marshal(192);
  ssm_assign(acts->brush, actg->priority, acts->__tmp_0);
  // draw
  - change brush's ssm_mm->tag field to Black
  // draw
  - change brush's ssm_mm->tag field to RGB
  //  assign 3 fields
  ssm_adt_field(acts->brush, 0U) = ssm_marshal(204);
  ssm_adt_field(acts->brush, 1U) = ssm_marshal(255);
  ssm_adt_field(acts->brush, 2U) = ssm_marshal(204);
  // draw

Preventing ssm_drop from segfaulting

When the memory manager performs ssm_drop, it relies on val_count to signal when it can stop checking for fields to recurse on.
For each word after the header until val_count is reached, the memory manager checks whether the given word is even. If the word is even, it recurses on this field because it is a pointer to a heap object. If the word is odd, it skips this field because it's a packed value. Once val_count becomes the maximum number of fields in an ADT, it's possible for an ADT representation to contain garbage values in some of its fields if it's a smaller instance. In this situation it becomes possible for the memory manager to recurse on even garbage values and segfault.
By setting all the fields to an odd value before assignment, we prevent the possibility of drop accidentally recursing on even garbage values.

  acts->__tmp_0 = ssm_new_adt(3U, RGB);                    //  allocate new DCon w/ space for 3 (max # of) fields
  ssm_adt_field(acts->__tmp_0, 0U) = 0xffffffff;               //  set to odd value before assigning
  ssm_adt_field(acts->__tmp_0, 1U) = 0xffffffff;               //  set to odd value before assigning
  ssm_adt_field(acts->__tmp_0, 2U) = 0xffffffff;               //  set to odd value before assigning
  ssm_adt_field(acts->__tmp_0, 0U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 1U) = ssm_marshal(192);
  ssm_adt_field(acts->__tmp_0, 2U) = ssm_marshal(192);
  ssm_assign(acts->brush, actg->priority, acts->__tmp_0);
  - change brush's ssm_mm->tag field to Black
  ssm_adt_field(acts->brush, 0U) = 0xffffffff;               //  set to odd value to eliminate garbage
  ssm_adt_field(acts->brush, 1U) = 0xffffffff;               //  set to odd value to eliminate garbage
  ssm_adt_field(acts->brush, 2U) = 0xffffffff;               //  set to odd value to eliminate garbage
  - change brush's ssm_mm->tag field to RGB
  //  assign 3 fields
  ssm_adt_field(acts->brush, 0U) = 0xffffffff;               //  set to odd value to before assigning
  ssm_adt_field(acts->brush, 1U) = 0xffffffff;               //  set to odd value to before assigning
  ssm_adt_field(acts->brush, 2U) = 0xffffffff;               //  set to odd value to before assigning
  ssm_adt_field(acts->brush, 0U) = ssm_marshal(204);
  ssm_adt_field(acts->brush, 1U) = ssm_marshal(255);
  ssm_adt_field(acts->brush, 2U) = ssm_marshal(204);