Photo by Muneeb Qureshi on Unsplash

Predecessor and Dominator Phis

Recently, I realized that I had used phi nodes, i.e. nodes that join data flow between joined control flow branches, in a quite unusual way. The common way to use them is to have a list that provides exactly one value per incoming control flow edge and associating the value with it. I would call this approach predecessor phi, since values are associated with predecessors. However, in the Tyr compilers over the past years, I used an approach that used dominators instead. I.e. it would be allowed to associate the source of the value with any block that must have been passed when coming from that edge — assuming chosen values are still unambiguous wich isn’t an issue in practice.

Since I couldn’t remember having ever heard or read of a comparison of the two options, I asked about it but still couldn’t get an answer. So, this is my attempt to diagnose the differences.

TL;DR

Inserting is easier with dominators while deletion is much easier with predecessors. I haven’t looked into register allocation or similar in detail. Also, dominator phis allow creation of phi nodes before knowing the CFG between the source value and the phi node which can be beneficial or even required. Here, it does not matter if you create a “temporary” dominator phi and create a “real” predecessor phi. What matters is storing the information during compilation.

History

Tyr started as a research project with the goal to look into type-oriented programming. The compiler chose essentially a rule-based AST to SSA approach without any auxiliary structures like labeled instruction lists. Thus, for any AST node type, there always was and still is a translation rule that directly created the resulting SSA including phis. This included implicit conversions even in early versions. However, these implicit conversions can be force inline functions, i.e. it could happen that an arbitrary number of nodes were inserted into e.g. the end of syntactic translation of a then branch and the phi joining the result with that of the else branch. Just based on code that came from essentially the type system. There was no such thing as tracking open branches since it wasn’t required. Even in the upcoming release, the compiler will still use a similar pattern and works with at most one open branch at a time and, hence, no tracking, since the current branch is always the open branch.

A reason why I never really considered changing this behavior is that the language now has generalized binders resulting in a lot of very complex inlining logic where multiple inlining activities can happen at the same time. I honestly do not see how to track open branches and phi target updates in that context with acceptable complexity. So, I conclude that a clear advantage of dominator phis is control flow transformations that insert code between the source of a phi argument and the phi itself.

Such transformations can also be caused by cleanup code like try finally. Also, phi handling is much easier with such translations, because existing phis can be left untouched.

Unless such insertions can terminate the phi or all paths towards it for an input. This is something that started to surface when introducing exceptions. With break and continue introduced earlier, the issue formally speaking existed as well, but didn’t surface since examples that trigger the issue and are legal Tyr code are non-trivial and non-obvious. An example would be interleaving returning from binder applications: return blocks passed in this test. Interleaving in the sense of inlining since returns get mixed into child function calls resulting in control flow that is structurally incompatible with that of the called functions since the passed returns abort branches in the called function.

Conversion

Also, LLVM always required predecessor Phis, but I never really minded because translating source blocks to predecessors wasn’t an issue. It also never occurred to me until now that the choice could have any significant downsides because I had to track LLVM predecessors anyway since a block in TIR can result in multiple blocks in LLVM. All BR and switch instructions for instance are simple in TIR but create somewhat complex code in LLVM. Especially, class switch (example), which is a single instruction in TIR and a more or less complex graph in LLVM. But also LLVM’s invoke requires transformations because TIR is range-based in that regard to reduce the number of blocks and make the algorithms simpler.

The conversion in the backend started with simple entry and exit block tracking. Eventually, it was replaced by an LLVM-dominator-tree-based approach. The current implementation uses the TIR idoms in the frontend that are present anyway. The algorithm is essentially a parallel reverse walk on idoms. Every round tries to match all source blocks. Survivors get replaced by their idoms until no block survives. Integrity of the CFG guarantees successful termination. Also, there are no transformation rules that would replace a diamond-shaped part with a U-shaped part changing the number of inputs of an existing phi node. Additionally, in TIR, reachability ignoring predicate evaluation from the single root node is a strong invariant of a CFG.

Conclusion

Unfortunately, reality isn’t always simple and binary. For instance, inserting a throw terminates regular control flow, creates new control flow and is obviously itself an insertion:

try {
  var r = if x b.eval() else y
  …
} catch e { … }
with b = throw new NullAccess

Since dominators are good for insertions, I chose to stay with dominator phis until the current cfg reaches a point where deletions would be allowed and rewrite them to predecessor phis then. This sounds kind of expensive, but it isn’t in practice as the idom path to chosen dominators is usually short and it makes the compiler so much simpler since it perfectly fits with what is currently built and what is used to build from. Personally, I would call the approach temporary dominator phis.