News for hackers. Stuff that matters.
Re:Using Obscure Graph Theory to Solve Programming Languages... by chc4 on Wednesday May 14, 2025 @08:18AM (#43983632)
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.
Re:Using Obscure Graph Theory to Solve Programming Languages... by mananaysiempre on Wednesday May 14, 2025 @09:08AM (#43984098)
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.
Re:Using Obscure Graph Theory to Solve Programming Languages... by chc4 on Wednesday May 14, 2025 @04:09PM (#43988666)
The "equivalent-but-more-efficient program" example given at the top is almost exactly that, though
Re:Using Obscure Graph Theory to Solve Programming Languages... by tylerhou on Wednesday May 14, 2025 @04:21PM (#43988765)
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.