4 ms·

I’m also a bit weirded out by the lack of mentions of dominators (in TFA or in the article[1] it links to). Once you have the dominator tree, though, you’re sti

I’m also a bit weirded out by the lack of mentions of dominators (in TFA or in the article[1] it links to). Once you have the dominator tree, though, you’re still going to need to answer LCA queries on it (in this problem and in an SSA-based compiler both), so there seems to be no way around this part. The algorithm in the article does O(1) queries with O(V+E) preprocessing (assuming linear-preprocessing LCA, which, yeah). What’s the best algorithm for dominator trees? People usually talk about Lengauer–Tarjan[2], which is linear in practice (linear except for UNION-FIND), and not the linear one by Georgiadis[3,4]. Unfortunately, I’m not a compiler person. [1] https://doi.org/10.1016/j.ipl.2010.02.014 https://doi.org/10.1016/j.ipl.2010.02.014 [2] https://maskray.me/blog/2020-12-11-dominator-tree https://maskray.me/blog/2020-12-11-dominator-tree [3] https://www.cs.princeton.edu/research/techreps/43 https://www.cs.princeton.edu/research/techreps/43 [4] https://dl.acm.org/doi/abs/10.1137/070693217 https://dl.acm.org/doi/abs/10.1137/070693217

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 ago
  I 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 ago
    The "equivalent-but-more-efficient program" example given at the top is almost exactly that, though
- tylerhou 1y ago
  I 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.
tylerhou 1y ago
In practice, if I have to implement dominators, it's probably for a toy language so I just go with the (fast quadratic) dataflow approach. It's simple to implement if you know what you're doing and if you already have a dataflow framework, it's pretty easy to implement: https://github.com/tylerhou/cs265/blob/main/tylerhou/lib/ssa.ml#L3-L30 https://github.com/tylerhou/cs265/blob/main/tylerhou/lib/ssa...

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 ago
I 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 ago
  The "equivalent-but-more-efficient program" example given at the top is almost exactly that, though
tylerhou 1y ago
I 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.

tylerhou 1y ago

In practice, if I have to implement dominators, it's probably for a toy language so I just go with the (fast quadratic) dataflow approach. It's simple to implement if you know what you're doing and if you already have a dataflow framework, it's pretty easy to implement: https://github.com/tylerhou/cs265/blob/main/tylerhou/lib/ssa.ml#L3-L30 https://github.com/tylerhou/cs265/blob/main/tylerhou/lib/ssa...