4 ms·
You don't need to compute dominators. A topological sort of the graph gives you a computation order where your definitions are computed before their use.
by chc4 1y ago
You don't need to compute dominators. A topological sort of the graph gives you a computation order where your definitions are computed before their use.
- mananaysiempre 1y agoI mean, it does, but that’s not what TFA’s problem statement is, and I can imagine why one may not want to immediately take apart the expression into assembly-like SSA let $0 = f a b in let $1 = g $0 c in ... and instead leave some original structure in place and some tree-level simplifications available.
- chc4 1y agoThe "equivalent-but-more-efficient program" example given at the top is almost exactly that, though
- tylerhou 1y agoI don't see how a topological sort helps you determine where to place the computation. If an expression A is topologically before an expression B, that does not mean that A always is computed on the path to B. For an example, consider a three-node binary tree where R is the root, A is the left child, and B is the right child. A valid topological sort is R A B, but it is not the case that whenever B is computed, A has already been computed.