The accumulator tail recursion transform claims to work for any associative
authorDuncan Sands <baldrick@free.fr>
Sat, 10 Jul 2010 20:31:42 +0000 (20:31 +0000)
committerDuncan Sands <baldrick@free.fr>
Sat, 10 Jul 2010 20:31:42 +0000 (20:31 +0000)
commit24080a98786cf393740cd035e27dd16c12827892
tree75c4b246a146e0140ce0cdb1b5c435c037410267
parent92c1f72c548e6a5e793ef19a0b04910992115b6c
The accumulator tail recursion transform claims to work for any associative
operation, but the way it's implemented requires the operation to also be
commutative.  So add a check for commutativity (and tweak the corresponding
comments).  This makes no difference in practice since every associative
LLVM instruction is also commutative!  Here's an example to show the need
for commutativity: the accum_recursion.ll testcase calculates the factorial
function.  Before the transformation the result of a call is
  ((((1*1)*2)*3)...)*x
while afterwards it is
  (((1*x)*(x-1))...*2)*1
which clearly requires both associativity and commutativity of * to be equal
to the original.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108056 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Transforms/Scalar/TailRecursionElimination.cpp