Comment by mananaysiempre | Hacker News Reader

Comment by mananaysiempre | Hacker News Reader

Parent Full thread

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

[2] https://maskray.me/blog/2020-12-11-dominator-tree

[3] https://www.cs.princeton.edu/research/techreps/43

[4] https://dl.acm.org/doi/abs/10.1137/070693217

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...

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.

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.

The "equivalent-but-more-efficient program" example given at the top is almost exactly that, though

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.

Reply on news.ycombinator.com