Design a Verona MLIR dialect

[rengolin]

Related to #104, this task is about lowering the operations, constructs (like if, when, where), lexical scopes, lambda logic, future registration, dispatch and completion, etc.

This can be a mix of existing dialects (std, loop) and Verona-specific constructs, but anything that touches specific Verona types must be Verona-specific nodes as well, so likely to be mostly Verona anyway.

Acceptance criteria:

• A consensus on the representation of each language construct
• A description of the steps needed to take from opaque MLIR to Verona dialect
• Examples in MLIR for each of the constructs and variations, with expected semantics

Not included:

• Implementation of the partial conversion process (has to be concurrent with Type Inference #105)

[plietar]

Two sources for the list of operations we need is the existing IR and Bytecode.
https://github.com/microsoft/verona/blob/master/src/compiler/ir/ir.h
https://github.com/microsoft/verona/blob/master/src/interpreter/bytecode.h

In the existing prototype, a number of runtime features were exposed as builtin functions rather than special syntax and ir statements (they do have special bytecode instructions though). I don’t know what makes more sense in MLIR.

[mjp41]

I would be keen to keep them as builtin functions, and only do something special when lowering to LLVM. I think this will help with experimentation (as long as the type system can express their requirements).

[mjp41]

I believe ponyc allows builtins to be given an LLVM command to replace them. This is very useful there for expanding the core libraries without doing anything at the front-end.

https://github.com/ponylang/ponyc/blob/eff764fb0173a1629d37ddc9a817d8fded5f36bd/packages/builtin/float.pony#L82

[davidchisnall]

Pony has a much weaker isolation model for foreign code, so I'm a bit nervous about accidentally introducing an unsafe keyword via a mechanism like that. I think I'd rather provide a small (well-documented) set of compiler builtins that the standard library can depend on. Ideally this should be sufficient to allow different compiler implementations to use the same standard library (and vice versa), though I don't consider that to be anything that we need to care about in the short term (OpenJDK and .NET 5 both went through this process, which was quite a useful exercise for both but not something that should block anything else for us).

[rengolin]

In MLIR, operations and function calls are treated equal (ish). For example, you can have an unnamed/undeclared "operator" by having its name in quotes and operands laid out like a function:

%0 = "verona.myop" (%a, %b) : (i64, f32) -> i32

You can also declare a "verona.myop" in the TD file and say it has a functional-type, and then it looks like this:

%0 = verona.myop (%a, %b) : (i64, f32) -> i32

Note the lack of quotes in the name. The former was a generic operand that needed additional logic to understand, the latter is an official verona operation, with accessors for the operands, result, types, etc.

Of course, you can go further and make it more neat, like other native operations:

%0 = verona.myop %a : i64, %b, f32 : i32

But that doesn't change the internal representation inside TableGen (and the compiler), where the operation is some form of Op<VeronaDialect, MyOp, ...>.

We could do this process as smooth or blunt as necessary, but the real issue, as @mjp41 said, is the type system. We need to make sure first, that we can create an opaque type system. If we can't, we'll have to be a lot more blunt than we may want, to get the type system in place before we can look at the actual operations, which may create a chicken-egg problem.

I'm hoping the two problems (operation and type definition) just happen to be orthogonal. If so, we can hopefully lower directly to an untyped verona dialect and then just do the type inference. But I'm not sure this is possible. Hopefully #101 will help us understand better.

[rengolin]

We're moving the high level IR to a different design, only having the low-level parts in MLIR, so all of the designs in this issue are being deprecated in favour of a more modular approach.