[Wasm RyuJIT] Basic Control Flow

[kg]

To generate Wasm from RyuJIT we need a way to map our more general control flow to the limited control flow constructs available in Wasm.

Wasm represents control flow by having branches target specific blocks, where the block types are block and loop (with some syntactic sugar ones that decompose to block). Branches either travel to the start of a loop block or to the end of a non-loop block.

As a result, Wasm constrains control flow as follows:

• Any forward branches must be contained by the block they target.
  At minimum, this means that before you generate a forward branch you need to know its destination and wrap that branch in a block so you can target it with your branch. You need to ensure that block ends at the appropriate place.
• Any backward branches must be contained by the loop they target.
  At minimum, this means that you must know the location of all the backward branches in a method along with their targets, to ensure that you open a loop block at the backward branch target. You don't necessarily need to end that block in a particular place, since branches target its start instead of its end.

For control flow we can't represent using block and loop natively, we have to generate one or more loops with a dispatcher switch (br_table) at the top that performs a forward branch to the actual destination. This would turn a backward branch into a combination of backward-branch-to-dispatcher and forward-branch-to-destination, and require the use of a temporary local to select the destination. This is similar to the way roslyn-generated MoveNext methods work.

Preliminary Plan

We assume for now that finallys / filters / catches will be funclets. NAOT-LLVM does not use funclets for catches. If we end up doing the same, likely not a big deal to cope with this, as catches still only reachable via exceptions.

Convert all irreducible “normal” flow into proper loops

• Find sccs #120534 is one way we could do this, using a dispatch block. Note there are lots of really ugly CFGs out there, especially OSR + Async cases. Expect Async2 will give us similar wonky flow.
• We will need a “no exceptional flow” loop finding algorithm; should be a relatively simple tweak on what we have now
• We may want to do a similar dispatch trick for finally cloning; right now we only clone along one path out of the try; this would let us handle all paths without more code duplication.
• Run SCC fixing late, then use loop-aware RPO to get a good block ordering
  • Also stress mode that runs SCC fixing earlier (like the PR above) and in normal jitting
  • We may find cases where fixing the SCCs improves codegen, so might want to be able to run it as part of jitting for other targets too (though likely with a different fixing approach; see notes below about optimized modifications).

Tile this block ordering with WASM control flow structures

• In the short term we can just dump this out as text / wasm “assembly”
• Optionally leverage dominance/postdominance to try and maximize use of if/else
• LLVM/Wasm seems to be fairly aggressive in their use of select to eliminate branches, even doing costly seeming speculative evaluation. Will probably just rely on our current if-conversion here. May want to prioritize enabling if-conversion in loops?

Evaluate if more "optimized" approaches to resolving irreducible flow/SCCs make sense

• Defer until clearly needed, eg once we can profile certain key apps.
• Some prior art: Janssen and Corporaal; Ramsey; Unger and Mueller.

[AndyAyersMS]

More General Finally Cloning

Some high-level notes on what we need to do to eliminate all finally clauses from jitted code.

Multiple Continuations

The current finally cloner picks one path out of a try/finally and clones the finally along that path. If there are multiple paths then the remaining paths continue to invoke the finally that is shared with the exceptional path. A canonical example is something like this:

void Foo(int p)
{
    try
    {
        if (p == 0)
        {
            return;
        }
    }
    finally
    {
         Console.WriteLine("Hello, World!");
    }

    Console.WriteLine("Goodbye, World!");
}

where after the finally executes (normally) the method may return or print goodbye.

Typically the "fall through" path at the end of the try is the one chosen for cloning. So we transform the code to something that can't really be expressed in C#, but is something like:

// clone just one path

void Foo(int p)
{
    try
    {
        if (p == 0)
        {
            goto CallFinally;
        }

        goto ClonedFinally;
    }
    finally
    {
         Console.WriteLine("Hello, World!");
    }

ClonedFinally:
    Console.WriteLine("Hello, World!");
    Console.WriteLine("Goodbye, World!");
    goto Return;

CallFinally:
    // invoke finally shared with EH path

Return:
    return;

}

One option we could pursue is to clone for each path. This may involve a fair amount of code duplication:

// clone along all paths

void Foo(int p)
{
    try
    {
        if (p == 0)
        {
            goto ReturnPath;
        }
    }
    fault
    {
         Console.WriteLine("Hello, World!");
    }

    Console.WriteLine("Hello, World!");
    Console.WriteLine("Goodbye, World!");
    return;

ReturnPath:

    Console.WriteLine("Hello, World!");
    return;

}

Another is to create a shared normally-executed finally, and track where it should go afterwards via a state variable. This is conceptually similar to what we plan to do for irreducible loops:

// shared clone

void Foo(int p)
{
   int state = -1;
    try
    {
        if (p == 0)
        {
            state = 0;
            goto AfterTry;
        }
        state = 1;
    }
    fault
    {
         Console.WriteLine("Hello, World!");
    }

AfterTry:

    // Cloned finally
    Console.WriteLine("Hello, World!");

    // Jump to proper continuation
    switch (state)
    {
       case 0: goto Return;
       case 1: goto Goodbye;
       default: FailFast();
    }

Goodbye:

    Console.WriteLine("Goodbye, World!");

Return:
    return;
}

Finally with nested EH

The original work for finally cloning was done long before the JIT had the ability to duplicate/clone EH. Now that we have that ability, we should be able to handle cases where the finally itself contains EH regions. Given that these finallys are likely quite large the shared normally-executed case seems sensible.

Finally nested within EH

Likewise the current phase does not clone finallys that are within some other handler. This is the flip side of the condition above, and should also be something we can now handle.

Latent introduction of finally clauses

If the goal is to eliminate all finally clauses from the generated code, we may need to run this phase more than once. RuntimeAsync or similar transformations may want to introduce try/finally to ensure that certain post-dominating actions happen even if exceptions are thrown.

[SingleAccretion]

what we need to do to eliminate all finally clauses from jitted code.

Is this for performance or correctness? I don't think it is needed for correctness, since you can still express finallys as funclets by spilling all finally-live variables to memory (among other approaches).

[AndyAyersMS]

what we need to do to eliminate all finally clauses from jitted code.

Is this for performance or correctness? I don't think it is needed for correctness, since you can still express finallys as funclets by spilling all finally-live variables to memory (among other approaches).

More of a thought exercise at this point... just curious how much work is behind doing something like this. It's more than I thought. I'd forgotten about the nesting/nested limitation.