+++
title = "Better way of rebuilding the order"
date = "2022-04-29"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["3a8g4a"]
forwardlinks = []
zettelid = "3a8g4b"
+++

The previous way of rebuilding the order is actually not correct. It's
completely valid to have control-flow graphs where the variables in the
argument list are declared at the same kind of domination point. This
would lead to ambiguities and make it impossible to correctly rebuild
the code using the domination method above, as there is only one order
that is actually correct.

For μ-functions this is not a problem, because their execution is
dependent on predecessors, which is the same as for φ-functions. In that
case, we only have to look at the previous predecessors and the current
predecessors after having inserted the nodes to convert the η-functions.
If the predecessors are the same, then the registers are switched, and
otherwise they are kept the same, as that means the predecessors have
not changed.

However, for γ-functions this is a bit more complicated, because one
does not have the correct predecessors available anymore. In that case,
however, it's interesting to note that the only correctness argument
that is really necessary to find the right predecessor is to show that
there exists a path from the dominator to the program counter for which
the chosen predicate simplifies syntactically to the value T. In that
case, on knows that no other predicate will be true, and so this must be
the correct register to pick for that predecessor.