Add Common Subexpression Elimination

jvican commented 8 years ago

More information in the commit messages and source code.

jvican commented 8 years ago

Review by @DarkDimius.

jvican commented 8 years ago

I've added a final version of the transformation that works transparently for more test cases. Before, my optimization wasn't able to apply the optimization in concrete cases and the logic was rough. As a result, a lot of cases were not handled.

Another important note is that now the optimization interacts with itself, and it's able to reuse already applied optimizations of idempotent sub trees. See test5.

I'd like to know if I should add a proper test infrastructure, right now i'm executing the test files by hand.

For more information about my changes, see the commit message:

This final version is able to detect common subexpression in rhs that are impure but contain idempotent trees. It also makes it work more transparently, and removes some bad assumptions and rough edges of the previous implementation.
Add more complex test cases to show functionality.
Change basic algorithm and make it more performant.
Significantly simplify the way the algorithm works (in the logical level).

DarkDimius commented 8 years ago

I'd like to know if I should add a proper test infrastructure, right now i'm executing the test files by hand.

We would work on rebuilding test infrastructure after rebasing over latest HK-types in Dotty.

allanrenucci commented 8 years ago

I have some tests you might want to reuse: https://github.com/allanrenucci/dotty/blob/idempotent-call-elimination/tests/run/idempotentcalls.scala

jvican commented 8 years ago

Thanks, I’m basically doing my own test suite exactly like yours, and it’s almost finished (although mine is more compact and short). I’ll have a look before shipping this to make sure all of your tests pass as well :wink:.

On 19 Jul 2016, at 05:54, Allan Renucci notifications@github.com wrote:

I have some tests you might want to reuse: https://github.com/allanrenucci/dotty/blob/idempotent-call-elimination/tests/run/idempotentcalls.scala https://github.com/allanrenucci/dotty/blob/idempotent-call-elimination/tests/run/idempotentcalls.scala — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/dotty-linker/dotty/pull/7#issuecomment-233523660, or mute the thread https://github.com/notifications/unsubscribe-auth/ACWU_lW7wIrovGmwBrt1SyonavidFYTGks5qXEp3gaJpZM4JL8iF.

jvican commented 8 years ago

This PR is completely outdated, I'm closing it. The new optimization is implemented in the branch cse-rebase.

jvican commented 8 years ago

https://github.com/dotty-linker/dotty/tree/cse-rebase

dotty-linker / dotty

Add Common Subexpression Elimination #7