Handle arrays properly in the runtime (part 1)

• Support passing pointers between the host code and runtime
• Calculate runtime sizes of arrays that need to be allocated
• TODO: handle non-zero constant arrays
• TODO: better host code interface

hercules_cg/src/common.rs

 extern crate hercules_ir;
 
 use std::collections::HashMap;
+use std::iter::repeat;
 
 use self::hercules_ir::*;
 
@@ -258,6 +259,27 @@ impl<'a> FunctionContext<'a> {
         res.sort();
         res
     }
+
+    /*
+     * Determine the array numbers for all the array constants. These are needed
+     * to know which pointer passed to the runtime corresponds to which array
+     * constant. Return a map from constant ID to array number - non-array
+     * constants don't have an array number.
+     */
+    pub(crate) fn array_constant_inputs(&self) -> Vec<Option<u32>> {
+        self.constants
+            .iter()
+            .scan(0, |num, cons| {
+                if cons.try_array_type(self.types).is_some() {
+                    let res = Some(*num);
+                    *num += 1;
+                    Some(res)
+                } else {
+                    Some(None)
+                }
+            })
+            .collect()
+    }
 }
 
 /*
@@ -327,14 +349,12 @@ impl<'a> PartitionContext<'a> {
 
         // Assemble the manifest.
         let mut manifest = PartitionManifest::default();
-        manifest.top_node = top_node.idx() as u32;
+        manifest.top_node = top_node;
 
         // The first inputs are the data inputs, from other partitions.
-        manifest.inputs.extend(
-            data_inputs
-                .iter()
-                .map(|x| PartitionInput::DataInput(x.idx() as u32)),
-        );
+        manifest
+            .inputs
+            .extend(data_inputs.iter().map(|x| PartitionInput::DataInput(*x)));
 
         // The next inputs are the function parameters, all in order.
         manifest.inputs.extend(
@@ -342,7 +362,9 @@ impl<'a> PartitionContext<'a> {
                 .map(|x| PartitionInput::FunctionArgument(x as u32)),
         );
 
-        // The next inputs are the array constants, all in order.
+        // The next inputs are the array constants, all in order. TODO: only
+        // include constant inputs for constants actually used by this function,
+        // not all the constants in the module.
         manifest.inputs.extend(
             (0..(function
                 .constants
@@ -359,11 +381,9 @@ impl<'a> PartitionContext<'a> {
         );
 
         // The outputs are the data outputs of this partition.
-        manifest.outputs.extend(
-            data_outputs
-                .iter()
-                .map(|x| PartitionOutput::DataOutput(x.idx() as u32)),
-        );
+        manifest
+            .outputs
+            .extend(data_outputs.iter().map(|x| PartitionOutput::DataOutput(*x)));
 
         // If there are multiple control returns, also output the node being
         // returned from.
@@ -374,7 +394,7 @@ impl<'a> PartitionContext<'a> {
         // Store the successor partitions.
         manifest.successor_partitions = control_successors
             .into_iter()
-            .map(|(part_id, control_id)| (control_id.idx() as u32, part_id.idx() as u32))
+            .map(|(part_id, control_id)| (control_id, part_id))
             .collect();
 
         PartitionContext {
@@ -423,13 +443,13 @@ pub(crate) fn generate_type_string(ty: &Type, llvm_types: &Vec<String>) -> Strin
                 "{}".to_string()
             }
         }
+        Type::Summation(_) => todo!(),
         Type::Array(_, _) => {
             // Array types becomes pointers. The element type and dynamic
             // constant bounds characterize the access code we generate later,
             // not the type itself.
             "ptr".to_string()
         }
-        Type::Summation(_) => todo!(),
     }
 }
 
@@ -524,3 +544,194 @@ pub(crate) fn generate_dynamic_constant_strings(module: &Module) -> Vec<String>
 
     llvm_dynamic_constants
 }
+
+/*
+ * Calculate in-memory size and alignment of a type. The size is optional, since
+ * array types with dynamic constant dimensions may not have a compile time
+ * known size.
+ */
+pub fn type_size_and_alignment(module: &Module, ty: TypeID) -> (Option<usize>, usize) {
+    match module.types[ty.idx()] {
+        Type::Control(_) => {
+            panic!("PANIC: Can't calculate in-memory size and alignment of control type.")
+        }
+        Type::Boolean => (Some(1), 1),
+        Type::Integer8 => (Some(1), 1),
+        Type::Integer16 => (Some(2), 2),
+        Type::Integer32 => (Some(4), 4),
+        Type::Integer64 => (Some(8), 8),
+        Type::UnsignedInteger8 => (Some(1), 1),
+        Type::UnsignedInteger16 => (Some(2), 2),
+        Type::UnsignedInteger32 => (Some(4), 4),
+        Type::UnsignedInteger64 => (Some(8), 8),
+        Type::Float32 => (Some(4), 4),
+        Type::Float64 => (Some(8), 8),
+        Type::Product(ref fields) => {
+            let (size, align) = fields
+                .iter()
+                .map(|ty| type_size_and_alignment(module, *ty))
+                .fold(
+                    (Some(0), 1),
+                    |(acc_size, acc_align), (field_size, field_align)| {
+                        // Alignment of product is maximum alignment of fields.
+                        let new_align = std::cmp::max(acc_align, field_align);
+                        if let (Some(acc_size), Some(field_size)) = (acc_size, field_size) {
+                            // Pre-padding is so that the new field has proper
+                            // alignment within the product.
+                            let mut pre_padding = field_align - acc_size % field_align;
+                            if pre_padding == field_align {
+                                pre_padding = 0;
+                            }
+                            (Some(acc_size + pre_padding + field_size), new_align)
+                        } else {
+                            (None, new_align)
+                        }
+                    },
+                );
+
+            if let Some(size) = size {
+                // Post-padding is so that the overall in-memory size has the
+                // right alignment in an array, and is only done at the end.
+                let mut post_padding = align - size % align;
+                if post_padding == align {
+                    post_padding = 0;
+                }
+                (Some(size + post_padding), align)
+            } else {
+                (None, align)
+            }
+        }
+        Type::Summation(_) => todo!(),
+        Type::Array(elem, ref dims) => {
+            let (maybe_elem_size, elem_align) = type_size_and_alignment(module, elem);
+
+            // We can only calculate the number of elements at compile time if
+            // every dynamic constant dimension is a compile-time constant.
+            let maybe_num_elems = dims.iter().fold(Some(1), |acc, dim| {
+                Some(acc? * module.dynamic_constants[dim.idx()].try_constant()?)
+            });
+
+            // Even if the number of elements is compile-time known, the element
+            // type may have unknown compile-time size.
+            if let (Some(elem_size), Some(num_elems)) = (maybe_elem_size, maybe_num_elems) {
+                (Some(elem_size * num_elems), elem_align)
+            } else {
+                (None, elem_align)
+            }
+        }
+    }
+}
+
+/*
+ * Calculate in-memory bytes representing constant. Return the in-memory bytes
+ * and the alignment of the constant, if it's non-zero. If it's zero, optionally
+ * return the size of the constant, and its alignment. TODO: decide on how to
+ * represent memory layouts at the compiler level.
+ */
+pub fn embed_constant(module: &Module, cons: ConstantID) -> ConstantBytes {
+    let unchecked = match module.constants[cons.idx()] {
+        // Handle zero constant scalars below.
+        Constant::Boolean(v) => ConstantBytes::NonZero(vec![v as u8], 1),
+        Constant::Integer8(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 1),
+        Constant::Integer16(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 2),
+        Constant::Integer32(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 4),
+        Constant::Integer64(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 8),
+        Constant::UnsignedInteger8(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 1),
+        Constant::UnsignedInteger16(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 2),
+        Constant::UnsignedInteger32(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 4),
+        Constant::UnsignedInteger64(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 8),
+        Constant::Float32(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 4),
+        Constant::Float64(v) => ConstantBytes::NonZero(v.to_ne_bytes().to_vec(), 8),
+        Constant::Product(ty, ref fields) => {
+            let field_bytes: Vec<ConstantBytes> = fields
+                .iter()
+                .map(|field| embed_constant(module, *field))
+                .collect();
+
+            if field_bytes.iter().all(|cb| {
+                if let ConstantBytes::Zero(_, _) = cb {
+                    true
+                } else {
+                    false
+                }
+            }) {
+                // If all of the fields are zero constants, then this is a zero
+                // constant.
+                let (size, align) = type_size_and_alignment(module, ty);
+                ConstantBytes::Zero(size, align)
+            } else {
+                // We only construct the in-memory bytes if there is a non-zero
+                // bytes somewhere.
+                let (mut bytes, align) = field_bytes.into_iter().fold(
+                    (vec![], 0),
+                    |(mut acc_bytes, acc_align), field| {
+                        // Alignment of product is maximum alignment of fields.
+                        let new_align = std::cmp::max(acc_align, field.align());
+
+                        // Pre-padding is so that the new field has proper
+                        // alignment within the product.
+                        while acc_bytes.len() % field.align() != 0 {
+                            acc_bytes.push(0);
+                        }
+                        match field {
+                            ConstantBytes::NonZero(bytes, _) => acc_bytes.extend(&bytes),
+                            ConstantBytes::Zero(size, _) => acc_bytes.extend(repeat(0).take(size.expect("PANIC: Attempted to embed a zero constant with unknown size into a non-zero constant product. Non-zero constants must have compile-time known size. This is probably because an array field is a zero constant with non-constant dynamic constant dimensions."))),
+                        }
+                        (acc_bytes, new_align)
+                    },
+                );
+
+                // Post-padding is so that the overall in-memory vector has the
+                // right size, and is only done at the end.
+                while bytes.len() % align != 0 {
+                    bytes.push(0);
+                }
+                ConstantBytes::NonZero(bytes, align)
+            }
+        }
+        Constant::Summation(_, _, _) => todo!(),
+        Constant::Array(ty, ref elements) => {
+            let element_bytes: Vec<ConstantBytes> = elements
+                .iter()
+                .map(|element| embed_constant(module, *element))
+                .collect();
+
+            let (size, align) = type_size_and_alignment(module, ty);
+            if element_bytes.iter().all(|cb| {
+                if let ConstantBytes::Zero(_, _) = cb {
+                    true
+                } else {
+                    false
+                }
+            }) {
+                // If all of the fields are zero constants, then this is a zero
+                // constant.
+                ConstantBytes::Zero(size, align)
+            } else {
+                let array_bytes: Vec<u8> = element_bytes
+                    .into_iter()
+                    .map(|cb| match cb {
+                        ConstantBytes::NonZero(bytes, _) => bytes,
+                        ConstantBytes::Zero(size, _) => vec![0; size.expect("PANIC: Attempted to embed a zero constant with unknown size into a non-zero constant array. Non-zero constants must have compile-time known size. This is probably because an array element is a zero constant with non-constant dynamic constant dimensions.")],
+                    })
+                    .flatten()
+                    .collect();
+                assert_eq!(array_bytes.len(), size.expect("PANIC: Size of a non-zero constant array is unknown at compile time. All non-zero constants must have compile time known size."), "PANIC: Size of array type calculated by type_size_and_alignment differs from calculated in-memory byte representation's size.");
+                ConstantBytes::NonZero(array_bytes, align)
+            }
+        }
+        Constant::Zero(ty) => {
+            let (size, align) = type_size_and_alignment(module, ty);
+            ConstantBytes::Zero(size, align)
+        }
+    };
+
+    // Catch all code for making zero constant scalars actually
+    // ConstantBytes::Zero variants.
+    if let ConstantBytes::NonZero(bytes, align) = &unchecked {
+        if module.constants[cons.idx()].is_strictly_scalar() && bytes.iter().all(|x| *x == 0) {
+            return ConstantBytes::Zero(Some(bytes.len()), *align);
+        }
+    }
+    unchecked
+}