EBBs aren't working out all that well

[lars-t-hansen]

Cranelift uses extended basic blocks (EBBs) for its flow graphs: these are essentially single-entry multiple-exit linear sequences of instructions, they can be composed of what would normally be multiple basic blocks (BBs), namely, they are traces of BBs through subtrees of the BB flow graph. BBs are "classical" but EBBs have some theoretical advantages in that there are fewer of them (so less overhead of time and space) and larger (so some non-global optimizations have greater scope to work in) and faster (computing the immediate dominator of the non-first BB of an EBB is trivial).

However, EBBs have some disadvantages. As BBs are the classical representation of flow graphs, most of the literature uses BBs, and to use classical algorithms directly on EBBs we must perform a translation of the algorithm, or we must reconstruct the BB graph from the EBBs when that translation is not possible. Furthermore, EBBs have a dicey relationship with loops: an EBB can be partly in a loop and partly outside a loop (if a side exit from the EBB is the back edge), so a loop algorithm must either split the EBB at the exit (doable but not currently done, AIUI) or risk being unsound (probably the current situation).

It turns out that several passes of Cranelift reconstruct the BB graph. Supposedly (I have this from @sunfishcode) the SSA construction algorithm does this, and my experimental live range splitter must do it, because it needs to reconstruct the SSA after splitting.

The evidence is thus mounting that EBBs are not the best choice for the flow graphs and that we should consider moving to BBs. This would probably be a large undertaking.

[julian-seward1]

You could argue that CL spends most of its time and space dealing with instructions, not ebbs, so the additional overheads of this might be relatively modest.

This would probably be a large undertaking.

Yes, but to some extent it would be mechanical. We'd basically go looking for code fragments that say if insn.is_exit && !insn.is_last_in_ebb, replace with if false, and fold out dead control flow and representation accordingly.

We'd also have to change conditional jump instructions to specify both branch targets, I guess, and add a preferred-fallthrough indicator so we can make explicit the layout decisions that are implicit in the ebb scheme.

[nbp]

to use classical algorithms directly on EBBs we must perform a translation of the algorithm

I agree with this claim, and the overhead is a mental overhead that we have to cover all the cases.
From experience dealing with a Range Analysis which had many corner cases, I would recommend against the increasing complexity of the compiler, as these would later lead to security issues.

So, unless these translations could be mechanized, such as expressing logic on BB and having it applied implicitly on EBB, the memory overhead is probably not worth the security nightmare.

[nbp]

Summary of discussion with @lars-t-hansen , @sunfishcode and @sstangl:

The approach here is to first add a verification phase, which would be used to assert that EBB are expressing the same information as a BB would be expected to contain later on. Such as a single conditional branch and a fall-through instruction, with nothing in-between.

Then we can change the logic to fix all the test cases to be written down using this restricted-EBB.
Doing so will enable working on each phase of the compiler independently of each others.

When all phases are converted to this restricted-EBB, then we should be able to replace branching instruction to have multiple targets, and later on replace EBB representation by BB.