4 ms·

This seems, at least upon first read, analogous to global value numbering (GVN). Or, depending on how you look at it, common subexpression elimination (CSE). I

This seems, at least upon first read, analogous to global value numbering (GVN). Or, depending on how you look at it, common subexpression elimination (CSE). I am mostly wondering why they are not mentioned in the article.

j2kun 1y ago
I came here to mention this as well. If this problem was so critical to the company the author was working at, it seems negligent to spend a _year_ reinventing a solved problem from scratch, especially given the author's apparent history of compiler experience.
kldx 1y ago
Wondered about the same thing. Perhaps the author deals with graphs with no side effects or branches? It would then trivially become CSE on a single basic block. SSA transformations are essentially equivalent to what the author appears to be doing in terms of let-bindings [0]. [0] https://dl.acm.org/doi/10.1145/278283.278285 https://dl.acm.org/doi/10.1145/278283.278285
sjurba 1y ago
Shit. I had the semi hard problem at my last job and I just realized that the most efficient way I could solve it would be to write a blog post on how proud I was of my (shitty) solution and wait for the snarky commenters to tell me the proper way to do it.. I love this fact about the internet! Thanks guys! Keep it up! Including the snarkyness. It’s part of what makes it great! (I am aware this is not a novel idea. Posting the wrong solution is better than asking for help.. It is just fun to see it in action)
- tekknolagi 1y ago
  This is not snark! This is me genuinely wondering.
tylerhou 1y ago
GVN and CSE only identify duplicate/common subexpressions. They do not tell you where to place the computation of the common subexpression. The canonical algorithm to do that is to compute the dominance relation. A node X dominates Y if every path to Y must go through X. Once you have computed the dominance relation, if a common subexpression is located at nodes N1, N2, N3, you can place the computation at some shared dominator of N1, N2, and N3. Because dominance is a statement about /all/ paths, there is a unique lowest dominator [1]. This is exactly the "lowest single common ancestor." Note that dominance is also defined for cyclic graphs. There may be faster algorithms to compute dominance for acyclic graphs. Expressions in non-lazy programming languages are almost always acyclic (e.g. in Haskell, you can write cyclic expressions). [1] Claim. Let A, B, and C be reachable nodes. Suppose A and B both dominate C. Then either A dominates B or B dominates A. Proof. We prove the contrapositive. If neither A dominates B nor B dominates A, then there exist paths a, b from the root such that path a passes through A but not B and path b passes through B but not A. If there is no path from A to C, then A cannot dominate C as C is reachable. Similarly, if there is no path from B to C, then B cannot dominate C. So assume there are paths a' from A to C and b' B to C. Then the path b.b' witnesses that A does not dominate C, and the path a.a' witnesses that B does not dominate C. (There might be a bug in the proof; I think I proved something too strong, but I'm going to bed.)
- deleted 1y ago
  [deleted]
- mananaysiempre 1y ago
  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

j2kun 1y ago

I came here to mention this as well. If this problem was so critical to the company the author was working at, it seems negligent to spend a _year_ reinventing a solved problem from scratch, especially given the author's apparent history of compiler experience.

kldx 1y ago

Wondered about the same thing. Perhaps the author deals with graphs with no side effects or branches? It would then trivially become CSE on a single basic block. SSA transformations are essentially equivalent to what the author appears to be doing in terms of let-bindings [0]. [0] https://dl.acm.org/doi/10.1145/278283.278285 https://dl.acm.org/doi/10.1145/278283.278285

sjurba 1y ago

Shit. I had the semi hard problem at my last job and I just realized that the most efficient way I could solve it would be to write a blog post on how proud I was of my (shitty) solution and wait for the snarky commenters to tell me the proper way to do it.. I love this fact about the internet! Thanks guys! Keep it up! Including the snarkyness. It’s part of what makes it great! (I am aware this is not a novel idea. Posting the wrong solution is better than asking for help.. It is just fun to see it in action)

tekknolagi 1y ago
This is not snark! This is me genuinely wondering.

tylerhou 1y ago

GVN and CSE only identify duplicate/common subexpressions. They do not tell you where to place the computation of the common subexpression. The canonical algorithm to do that is to compute the dominance relation. A node X dominates Y if every path to Y must go through X. Once you have computed the dominance relation, if a common subexpression is located at nodes N1, N2, N3, you can place the computation at some shared dominator of N1, N2, and N3. Because dominance is a statement about /all/ paths, there is a unique lowest dominator [1]. This is exactly the "lowest single common ancestor." Note that dominance is also defined for cyclic graphs. There may be faster algorithms to compute dominance for acyclic graphs. Expressions in non-lazy programming languages are almost always acyclic (e.g. in Haskell, you can write cyclic expressions). [1] Claim. Let A, B, and C be reachable nodes. Suppose A and B both dominate C. Then either A dominates B or B dominates A. Proof. We prove the contrapositive. If neither A dominates B nor B dominates A, then there exist paths a, b from the root such that path a passes through A but not B and path b passes through B but not A. If there is no path from A to C, then A cannot dominate C as C is reachable. Similarly, if there is no path from B to C, then B cannot dominate C. So assume there are paths a' from A to C and b' B to C. Then the path b.b' witnesses that A does not dominate C, and the path a.a' witnesses that B does not dominate C. (There might be a bug in the proof; I think I proved something too strong, but I'm going to bed.)

deleted 1y ago
[deleted]
mananaysiempre 1y ago
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