[MooreToCore] Support for Unsized Array Type

[chenbo-again]

Unsized array type in systemverilog like OpenArrayType, QueueType can't be lower to Arc Dialect, because Arc only has sized array type.

Common programming language like Cpp can directly call mmap provided by OS to get dynamic size array. I can't see this kind of ability in systemverilog.

So how to achieve that if we want to solve #8276? Can you give me some advice?

[fabianschuiki]

For these dynamically-sized containers, including StringType, we will need a little bit of runtime support code in Arcilator to do things like adding and removing items, accessing items, and more. Overall I think we need to figure out two things:

1. How do we represent things like QueueType, AssocArrayType, OpenArrayType, and StringType after MooreToCore lowering, in a core dialect.
2. How does Arcilator take the core dialect representation and implement and call the necessary functions to interact with the dynamic data structures, functions like string_concat, queue_push_front, or assoc_array_get.i42.

For the core dialect representation, we probably have two options:

1. Add types and ops to the Sim dialect to represent and work with the common container types. Things like !sim.queue<T>, !sim.array<T>, !sim.hashmap<K,V>, and !sim.string are likely useful to have in general. You'd then have ops like sim.queue.push %queue, %item to work with these types.
2. Use extern function declarations and some kind of opaque type to represent the containers and operations. Things like !emitc.opaque<"sv.array.i42"> or !emitc.opaque<"sv.assoc.string.i42"> for the types, and func.func private @sv.queue.push.i42(%queue: !emitc.opaque<"sv.queue.i42">, %item: i42) alongside func.call @sv.queue.push.i42(%queue, %item) to work with the types.

The first option requires more types and ops to be added to Sim dialect upfront, but will allow for optimizations at the Sim dialect level and further processing of these dynamic container types. The second option is quicker to setup, but we give up any chance to further optimize what we do with the containers, and we don't specify the semantics properly anywhere. I would suggest going with the first option.

For implementation in Arcilator, we are going to need a pass that takes all the dynamic container types like !sim.queue<i42> and operations like sim.queue.push %queue, %item, and replaces them with LLVM struct pointers and runtime function implementations:

// before:
func.func @foo(%arg0: !sim.queue<i42>) {
  ...
  sim.queue.push %arg0, %1 : !sim.queue<i42>
}
// after:
func.func @foo(%arg0: !llvm.ptr<!llvm.struct<{cap: i64, size: i64, data: !llvm.ptr}>>) {
  ...
  func.call @queue.push.i42(%arg0, %1)
}
func.func @queue.alloc.i42() -> !llvm.struct<{cap: i64, size: i64, data: !llvm.ptr}> {
  func.call @mmap // or some memref dialect alloc function
  ...
}
func.func @queue.drop.i42(%arg0: !llvm.ptr<!llvm.struct<{cap: i64, size: i64, data: !llvm.ptr}>>) ->  {
  func.call @free(%arg0) // or some memref dialect free function
}
func.func @queue.push.i42(%queue: !llvm.ptr<!llvm.struct<{cap: i64, size: i64, data: !llvm.ptr}>>, %item: i42) { ... }
func.func @queue.pop.i42(%queue: !llvm.ptr<!llvm.struct<{cap: i64, size: i64, data: !llvm.ptr}>>) -> i42 { ... }
// and other runtime functions

There are also ways to create C++ implementations of these container functions that we compile into a runtime library and then link against. That is going to be easier to maintain but a bit more tricky because the C++ implementation does not know what the types are that get stored in the containers. For example, it wouldn't know about the i42 in queue.push.i42; the best you could do would be a queue.push(queue, item, sizeof(i42)), treating the items as plain memory. Doing this may be simpler initially, but it will have its own limitations and annoyances 😁.

My recommendation: try to do this for a single dynamic data type first. Strings would be a good start, because they are relatively simple.

[fzi-hielscher]

There are also ways to create C++ implementations of these container functions that we compile into a runtime library and then link against. That is going to be easier to maintain but a bit more tricky because the C++ implementation does not know what the types are that get stored in the containers.

If I may chime in here, as I've tinkered with this last summer: I've mentioned a while ago in the context of printf lowering that I've got a basic implementation of a runtime library in Rust which handles type marshaling. I'd be curious to know if you could imagine this as a path forward for upstream arcilator, @fabianschuiki? The fundamental idea is to compile a static struct containing the information on the concrete MLIR types at each call site, and pass it to the runtime library separately from the dynamic values.
In practice it looks like this:

// API hook for calls from LLVM IR
#[no_mangle]
pub extern "C" fn _arc_print_fmt(
    state_ptr: *const u8,
    // Pointer to a static list of type descriptors (zero non-variadic arguments)
    mrec: VariadicMarshalingRecord<0>,
    // Pointer to dynamic argument data
    args: VariadicMarshaledArgs,
) {
    // Combine the static and dynamic argument info and
    // call the actual implementation.
    print_fmt_impl(state_ptr, mrec.variadic(args));
}

fn print_fmt_impl(state_ptr: *const u8, vals: VariadicMarshaledValues) {
  // Prepend the instance's name if possible  
  if !state_ptr.is_null() {
        // Use the state pointer to look up the calling simulation
        // instance in the global registry.
        // The registry is RwLocked to allow running multiple
        // instances in parallel.
        let registry = ARTLIB_REGISTRY.read().unwrap();
        let name = registry.get_instance(state_ptr).friendly_name();
        print!("{} >> ", name);
    }

    let mut mode = FmtTag::BINARY;
    for arg in vals {
        match arg.get_type_descriptor().tag() {
            TypeTag::FMT(tag) => {
                // Format specifiers are passed as value-less types.
                mode = tag;
            }
            TypeTag::INTEGER(bits @ ..=64) => {
                // Integers up to 64 bits are passed by value.
                let smallint = *arg.marshal_as::<u64>();
                print_integer(&smallint, bits, &mode);
            }
            TypeTag::INTEGER(bits) => {
                // Integers beyond 64 bits are passed by reference.
                let apint = arg.marshal_as::<APInt>();
                print_integer(apint.as_ref(), bits, &mode);
            }
            _ => {
                panic!("Non-formattable argument");
            }
        }
    }
    println!("")
}

Of course, calling a generic library implementation instead of hand crafting the LLVM IR for each type will have some impact on performance. But I think there are ways to mitigate that (LTO, function attributes, etc.).

[fabianschuiki]

@fzi-hielscher That's a really nice approach! The ease of maintainability of such a runtime library will probably outweigh the modest performance gains of an in-IR implementation for a long time. I'm all for something like this 😃

[chenbo-again]

@fabianschuiki @fzi-hielscher Thank you for detailed explain the pros and the cons, and also very nice examples. It seems like more information will benefit future works. I will make effort on that.

[Max-astro]

Hi @chenbo-again, it's Good to know you're working on this issue. Our team is trying to add some support for string type features like the issue #8283. We took @fabianschuiki 's advice, adding the sim.string type and some operator lowering functions from import-verilog to the Moore and core dialect. But we don't have a clear plan to support the sim.string type in the arcilator for now.

I'd love to discuss the plan with you if you have any ideas about implementing these dynamically-sized containers in the sim dialect😁.