Thinking about a good design for MLIR regions

mlir-regions.md

In my opinion, one of the problems with MLIR's freedom of operation semantics is that we have no idea what the Region attached to an Operation actually means. Hence, it's impossible to automatically extend well-known SSA constructs such as GVN, CSE, ... into Regions, simply because we have no idea about the dominance relationship between the parent region containing the operation, and the child regions of the operation.

Here's a proposal on how we fix this. We add two three instructions into the base IR:

run: args * Region -> value
callcc: label * args * Region -> ()
return: value -> ()

• run runs a region, and returns the value returned by the region as an output. So we can write %x = run (%a1, %a2) { ... }.
• callcc runs a region, and forwards the value returned by the region to the basic block pointed to by label. So we can write `callcc ^next (%a1, %a2) { ... }
• return returns a value from a region to the caller.

We stipulate that every operation that contains a region is a macro for a particular region structure, and is elaborated into this structure. Thus, the IR will no longer have a dedicated func instruction, since we can run any region.

An %x = scf.if %cond { ... } { ... } will elaborate into the region:

%x = run (%cond) {
    ^entry(%cond):
      // new symbol for region values
      #then = { ... } 
      #else = { ... }
      condbr %cond ^then, ^else

    ^then:
      %out = run #then () 
      return %out

    ^else:
      %out = run #else () 
      return %out 
}

Anscf.for will elaborate into:

%x = run(%v) {
    ^entry(%v0):
      #loop = { ... }
      
    ^loop(%vi): 
      %vnext = run #loop (%vi)   
}

This ought to allow us to infer dominance from the elaboration specification, since attached regions are literally elaborated into real control flow.

Finally, we still need a way to represent cycles of call instructions. What do we do? We can simply allow references to region variables for regions that are at the same level of nesting.

Furthermore, the problem is that scf.if creates a region from which
we need to region values from. This complicates basically everything
about generating code, because I can't generate code with the semantics:

int foo(int x) {
    if (x == 1) { return -1; }
    if (x == 2) { return -2; }
    return -42;
}

because return can only return from the current region, not escape out of a parent region. We would
need this power to be able to useful things.