4 ms·

It seems the TailRecursionElimination.cpp pass is responsible for that. It has some smarts to know that the xor instruction between the call and return can be t

• ufo 5y ago
  Thanks for investigating that! An accumulator is when we add an extra parameter to hold the "loop variable", like this: bool doit(int n, bool acc) { if (n == 0) return acc; else return doit(n-1, !acc); } bool isEven(int n) { return doit(n, true); } The function is now tail-recursive and behaves similarly to this loop: bool acc = true; while (n != 0) { acc = !acc; n = n - 1; } return acc; According to the comment on the top of the file, apparently llvm can create this accumulator variable if the operation is associative and commutative. That's because after introducing the accumulator, the evaluation order is outside->inside instead of inside->outside.
• b3morales 5y ago
  Further reading about the relationship between recursion, iteration, and accumulators: https://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html https://blog.moertel.com/posts/2013-05-11-recursive-to-itera... This transformation is one you can apply in your own source as well. An example from that link, the recursive def factorial(n): if n < 2: return 1 return n * factorial(n - 1) can be rewritten iteratively: def factorial1d(n, acc=1): while n > 1: (n, acc) = (n - 1, acc * n) return acc