Transforming recursion into iteration for LLVM loop optimizations

ambicapter 2 days ago | parent | next [-]

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 2 days ago | parent [-]

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 2 days ago | parent | next [-]

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 a day ago | parent | prev [-]

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 a day ago \| parent [-]
		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 2 days ago | parent | prev [-]

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 2 days ago \| parent [-]
		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.