3 ms·

Transforming recursion into iteration for LLVM loop optimizations

• ambicapter 1y ago
  Hmm, wouldn't it be better to prove that the optimizations on a loop can also be performed on a recursion and then applying it? If they can't do that, how can they take the optimized loop, turn it back into a recursive structure, and assume that it is functionally identical to the starting recursive loop?
  • fluoridation 1y ago
    Presumably because each transformation step preserves semantics. What I'm wondering is what the point of the round-trip conversion is. If you've gone to the trouble of turning a function into an iteration, just leave like that.
    • Spivak 1y ago
      My guess would be because the transformation would be a user-visible change. If they produce a stack trace inside it wouldn't look as they expect.
    • ambicapter 1y ago
      That's my question, if each transformation step preserves semantics, how come they can't apply the optimization on the recursive form? I'm asking seeking clarification.
      • fluoridation 1y ago
        In general, proving things about recursive functions is more difficult. I could be wrong, but I think for example control flow graph builders usually stop at function boundaries, to keep the problem tractable. Turning a recursive function into an iteration makes it so you can see the whole execution as a single call, instead of having to hop around a virtual call stack. What I'm wondering is how they're able to turn the optimized form back into a recursive function. Surely there must be some recursive functions that if you optimize them they turn into simple loops or even a linear function is they're very bad.
• fellowniusmonk 1y ago
  Yngve depth is how many things your brain has to keep open at once when reading code. More nesting and overlapping, center-embedded obligations in recursive code (especially side effects) raise that load, independent of Big-O. Recursion isn’t a hardware thing; it compiles to iteration, so the trouble comes from how the code is written, not recursion itself. Optimizing for Kolmogorov complexity can make code shorter yet harder to parse, so naming and linearizing steps adds bytes but lowers the mental stack. Which is why heavily recursive code get's less optimization attention in most instances than loops.
  • bjoli 1y ago
    I find recursion clearer in many cases, even simple ones. Like, say, calculating gcd. The recursive approach uses one variable less, and expresses it in a way that is much closer to how I think about it.