Page MenuHomePhabricator

[TRE] Allow accumulator elimination when base case returns non-constant
ClosedPublic

Authored by laytonio on May 29 2020, 2:51 PM.

Details

Summary

Remove the requirement, that when performing accumulator elimination, all other cases must return the same dynamic constant. We can do this by initializing the accumulator with the identity value of the accumulation operation, and inserting an additional operation before any return.

Diff Detail

Event Timeline

laytonio created this revision.May 29 2020, 2:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 29 2020, 2:51 PM

What happens if there are multiple tail calls in a function using different accumulators? Something like the following:

int f(int a) {
  if (!a) return 0;
  if (a & 1) { return f(a-1)+1; }
  return f(a-1)*2;
}
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
797

I don't see any tests involving an accumulator and a select?

laytonio updated this revision to Diff 267770.Jun 1 2020, 5:47 PM

Add test case for multiple return values while accumulating.

laytonio marked an inline comment as done.Jun 1 2020, 5:47 PM
laytonio added a comment.EditedJun 1 2020, 6:08 PM

What happens if there are multiple tail calls in a function using different accumulators?

Currently on trunk, and after this patch, we only eliminate the first accumulating call we find and ignore any potential others. I think in the future it would be pretty easy to allow multiple accumulators of the same operation (eg. mul mul). In cases like the one you posted with different accumulator operations (eg. mul add), it is a lot more tricky (and I'm not sure possible) because the operations happen in reverse order.

Currently on trunk, and after this patch, we only eliminate the first accumulating call we find and ignore any potential others.

Well, on trunk, we fail out of tail recursion elimination completely, I think. But yes, makes sense.

I'd like to see a testcase for this.

In cases like the one you posted with different accumulator operations (eg. mul add), it is a lot more tricky (and I'm not sure possible) because of the operations happen in reverse order.

In general, with multiple arbitrary accumulator operations, it's impossible, yes: you can't reassociate the operations.

gcc does actually manage to do tail call elimination on my testcase. Roughly, you can distribute the multiplication over the addition. It doesn't seem very important, though.

laytonio updated this revision to Diff 268004.Jun 2 2020, 3:38 PM

I added your example as a test case. It is worth noting that even at -O1 clang hoists and merges the recursive calls and then branches to the correct accumulator, which would prevent either from getting removed. Also, the multiply by 2 gets converted to a shift, which would also prevent that path from getting removed. I'm going to take a look at creating another patch after this to convert shifts back to multiplies if it would enable an elimination.

efriedma accepted this revision.Jun 2 2020, 4:18 PM

I'm mostly concerned that we know what the limitations are, and that they apply correctly. There will always be some unimplemented transforms.

LGTM. I'll merge this for you

This revision is now accepted and ready to land.Jun 2 2020, 4:18 PM
lattner resigned from this revision.Jun 3 2020, 11:48 AM
This revision was automatically updated to reflect the committed changes.